Find an Error But Possible to Fix

Back to home page

During the verification with Google Docs, I found an error in Sec 5. I overlooked that f(σ) depends on z in the non-monotone case.

I think the error can be fixed with an improvement of Phase II of the extension generator theorem. I’m working on it now.

Not a Natural Proof

Back to home page

I moved to Penn State as a postdoctoral fellow. Using weekends, I regularly update Google docs for extra explanation. This is meant to be another proof verification too. So far I’ve confirmed no major errors in Sections 1-4.

One common objection to a proof of big hardness through circuit complexity is so-called natural proof. Related links are found on the web: natural proof paper, wikipedia article, summary. Natural proof is a notion invented by Razborov and Rudich.

The paper says that a natural argument against a major hardness would create a Boolean circuit B that breaks a pseudo random number generator. Suppose that there is a proof P that a polynomial-sized Boolean circuit A cannot compute a problem in the target complexity class.  If P is natural, it is constructive, i.e., it designs a property C nodes in A should satisfy, checks it inductively from the leaves, and at the root of A, it draws a contradiction due to the confirmed property C. This type of argument itself creates a polynomial-sized circuit B; it’s discussed along the node structure of A.

By the largeness of natural P, the property C computed by B has a statistical significance, i.e., C’s occurrence probability is different from that in the pseudo random case. The algorithm B can be used to break a pseudo random number generator in polynomial time. Thus such P is unlikely to exist.

The proofs presented in Sections 5 and 6 in the paper here are not natural. The method in the monotone case (Sec. 4) is used as a tool box. It creates a relation between i) input: a negative tail (edge pattern outside target l-cliques), and ii) output: a shift (a conjunction of edges/non-edges in the DNF at the root of A). Enumerating all such pairs (input, output), the proof in Sec 5 concludes that there is an output with no contradiction in addition to no l-cliques contained.

The shift argument finds a fixed point of another similar relation at the root of A only. It is based on counting, creating no B as above. The natural proof paper also points out in the 2nd paragraph on page 6 that a counting-based discussion could be non-natural.

The precise condition the shift method checks is the following: there exists an edge set z,  a) of specified size, b) whose removal annihilates small cliques, and c) such that there is an element t in the DNF of the considered node, c)-1 whose positive literal set is disjoint with z,  and c)-2 whose negative literal set is contained in z.

This condition is not inductively maintained in the arguments in Sec. 5 and 6. The construction of t for given z is inductive, but is not aware of Condition c-2). It is for a monotone case allowing t to contain contradictions. A relevant edge set z is chosen at the root of A statistically in the framework of the Hamming space.

Hence a circuit B to break a random number generator is not created.

Back to home page

Yet to Find a Major Flaw

Back to home page

I’m recently active in stack exchange. ( I’ve decided to refine the paper according to the discussions there.  The definition of sparsity will be more generalized.

The sticky post on the top collects all the related links. Especially, the google docs include extra explanations.

I’ll keep updating them on weekly basis.

I also gathered my old Hamming distance papers in the sticky post. Their motivation was actually this research: Let’s say a node in a Boolean circuit is an AND gate a=a1 ∧ a. An l-clique c is generated at a if the edges of c implies a. Inductively we have two sets of l-cliques generated at a1 and a. It takes a theory to figure out which cliques are generated at a. I first thought minimum Hamming distance could tell something important about it. It was short for the clique complexity. I moved to the l-extension after doing hard research.

Back to home page

Links to PDFs and Google Docs

Login: Guest

Password: Guest624

Latest Paper Draft (About 1.4MByte)

Links to the first version

Paper Verson 1.11 ,  Explanatory Notes Version 1.11 ,  Overview of the Shift Method (1.086MByte)

Google Docs for extra explanations to the 1st version

Sections 2 and 3

l-Extension,  Counting Marks,  Double Marks and Lemma 2.5Extension Generator Theorem 1,  Definition of Extension GeneratorEGT2  EGT3 ,  EGT4 , Split y of [n],  Relation to Sunflower .

Section 4

DNF and Terms I,  DNF and Terms II,   Preprocess,   Quadruples σ, 

BlockedEdges I,   BlockedEdges IIBlockedEdges III, 

LocalShiftLemma by Lemma,

Edge Direction ProblemRegular σ Only.

Section 5

Clique-Tail Pairs,  Fixed Point of (z, z’)First Two StepsSpace-Proportional Splits Step 3

Links to Hamming Space papers

l-extension Ext(U, l) becomes a majority when m is small and U is not too sparse  (Congressus Numerantium, 173(2005), 33–41)

Hamming Distance between Two Not Too Sparse m-Set Families is O( m / exp(-ln2 ln m) ), (Full version of the paper posted on 8/26/12. It improves the bound from O( m / ln m ). )

The sparsity of l-shadow of U is small as l gets smaller than m (Congressus Numerantium, 168(2004), 21–31. The definition of Ext(U, l) is slightly different in this old paper. It’s due to my try-and-errors.)

Some basic claims related to the Hamming space  (Congressus Numerantium, 161(2003), 41–63. )

Verifying the Proof

Back to home page

I’ve been debugging the proof since I posted the previous version in this blog on 7/1. I tried hard to attack the proof from the opposite side. I found only minor bugs so far, and now start believing it.

I refined the paper and notes accordingly:  i) overview sections 4.3 for the monotone case, and 5.2 for the NP-NC construction newly added, ii) some technical proofs in Section 2 are moved to appendices, iii) minor error corrections, and iv) missing proof steps filled in.

Please download the latest pdf files  from the link below. I’m adding the 3rd file to provide short overall explanation of the shift method.

Paper Verson 1.11 (1.357MByte)

Explanatory Notes Version 1.11 (4.77MByte)

Overview of the Shift Method (1.086MByte)

Login: Guest

Password: Guest624

(Further small refinement on 9/15/12.)

The claims on the Hamming space in Sections 2 and 3 make the foundation of the shift method. The theory is developed to handle circuit complexity, especially of the clique problem. It has flavors in different areas:

1. Geometry: We want to find how the generated cliques intersect with each other at a node of circuit. (This is one general difficulty of treating circuit complexity.) It is about the topological properties of families of sets whose metric is the Hamming distance. It helps if we consider balls and spheres about an element.

2. Probability: Probabilistic arguments in combinatorics are mainly based on counting, because a considered probability space is discrete. In the Hamming space, sparsity of a family plays a similar role: it is about the ratio of #hits to the total number of elements. We focus on sparsity in relation to discrete topological properties of the Hamming space. It simplifies arguments.

3. Analysis: Theorem 2.1 adds some analytic flavor. We do asymptotic sparsity analysis.

4. Algebra: The operator of the domain is disjoint set union. We introduce the notion of a set generating another based on it. A family of sets generated by more than one generators is similar to ideal in the ring theory. On the other hand, disjoint set union doesn’t allow the closure property well, so it’s not easy to construct the theory in a complete algebraic system. However, it is very helpful to find a generator that generates almost every element in a subspace — it’s the extension generator theorem (Theorem 3.4). It can tell you that an element exists in your target subspace.

5. Extremal Set Theory in Combinatorics: It is important to know how elements in the Hamming space are related, especially intersected, to handle extremal sets. Theorem 3.4 has a strong link to Erdös and Rado’s sunflower lemma. In the previous post, I wrote that extension generators are a generalization of sunflower. To be more precise, Theorem 3.4 with Lemma 2.7 immediately implies the existence of a q-sunflower in most cases covered by the sunflower lemma. I explained it in the paragraph right after Proposition 3.7 in the paper.The theorem claims a stronger statement in such a way that if you extend m-sets into l-sets, almost all the cases of q disjoint l-sets with a small generator  contain a q-sunflower.

The mathematical structure of the Hamming space is intriguing. Please take a look at my past findings. Let U be a family of m-sets.

a) Its l-extension Ext(U, l) becomes a majority when m is small and U is not too sparse (please click): The main theorem means that if we remove k edges from an n-clique, almost all l-cliques are gone when lk is asymptotically larger than n2. For example, if k=n5/3, a majority of √n-cliques don’t exist  no matther which k edges are eliminated.

b) The Hamming Distance between Two m-Set Families (please click): If the sparsity of U is  O( m1-ε )  (ε: small constant), and we have a similar family U’, their Hamming distance is asymptotically smaller than m. The bound O(m / log m) is shown in the paper. There is a way to improve it into O(m / exp( log log  m) ).

Back to home page