Yet to Find a Major Flaw

Back to home page

I’m recently active in stack exchange. (http://cstheory.stackexchange.com/) 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

Advertisements

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. )