monotone circuits

5:08 AM

Thank you vzn for setting up this chat room. I appreciate it very much. I'm going to post explanations frequently. Please feel free to ask any questions.

Let me test posting a figure

vzn

5:40 AM

welcome to the club!

JF!

user13097

docs.google.com/document/d/…

thanks. here is my explanation on l-extension as well as posting test

vzn

we had an interloper. GK has an interesting blog with lots of interesting papers to think about, incl on circuits & monotone circuits etc.

fyi latex doesnt work in here, it does on the main site, oh well. something to ask the chat feature team for.

JF thx for joining & your time.

re figures/pics, if the url is to the image, it will display as an image.

not sure how it sizes them though.

vzn

6:04 AM

eg:

(pentium 4)

vzn

3:53 PM

re extension, thx for that clarification, just had to brush up on notation. there sure are a lot of variants of existential quantification!

Quantification

Quantification has several distinct senses. In mathematics and empirical science, it is the act of counting and measuring that maps human sense observations and experiences into members of some set of numbers. Quantification in this sense is fundamental to the scientific method. In logic, quantification is the binding of a variable ranging over a domain of discourse. The variable thereby becomes bound by an operator called a quantifier. Academic discussion of quantification refers more often to this meaning of the term than the preceding one. In grammar, a quantifier is a type of deter...

vzn

4:03 PM

& the example was defn helpful.

so, there is quite a bit to talk about, 60p worth! am going to try to work thru the proof to some degree. but hope to keep this informal also & chat about related stuff too.

(the google link worked for me elsewhere, although at another location, the proxy web server seems to mess up fetching (all) google docs. argh!)

google docs are a good idea for this though.

Jun

Can you please tell me how you show figures?

vzn

click help below and note "oneboxing". if you have a url to an image alone (not a web page) that should work.

Jun

probably google drive is easier. I can write math fonts in text, I can just paste figure from evernote

vzn

note that here is how stackexchange chat rooms work: if there is inactivity for 14 days, the room is frozen. otherwise, it stays open. so, it is not hard to keep it open. even a single person posting intermittently can keep it open. am intending to keep this room open for as extended time as possible.

also, once frozen, archives are generally kept, if/after at least a relatively small threshold of messages has been exceeded in the room.

Jun

that's no problem. i like to chat. let me know your questions. or i can add extra explanation

vzn

4:15 PM

cool =)

Jun

Also, let me know if you have suggestion for improving the notation Ext(U, l) = {t \in {[n \choose l]} ; \exists s \in U, s \subset t}

vzn

sometimes, we might chat live, but other times, the asynchronous/intermittent nature will be helpful to take "study breaks" etc.

Jun

okay.

this is my work time too but I can chat concurrently.

vzn

ok! lets neither of us get in trouble =)

Jun

Are marks clear for you?

vzn

4:18 PM

so far I find no errors in your notation, at an early stage. let me formulate a sensible question on marks. it will take a little time to do that.

of course feel free to invite others to the room who have an interest.

Jun

let me know. marks and double marks plays roles in theorem 3.4

yes

vzn

now, one general issue with the proof.

which will relate to its acceptance by the "community".

Jun

means "cs theory" or "combinatorics"?

it's "cs theory" since it is the computer science problem

vzn

you mean this stackexchange site?

cstheory= computer science theory.

Jun

sorry i didn't get your question "relate to its acceptance by the community"

vzn

4:22 PM

oh yes, acceptance by TCS community.

that reminds me, I have to post some links.

have you ever heard of deolalikar? was hoping to stir up a similar response.

Jun

yes

vzn

to me its a bit shabby that your proof is near 1/2 yr old with very little attn by the community.

so did some small work to publicize it.

in cyberspace.

Jun

i looked at his paper. it's a whole different approach

vzn

was surprised at the resistance/lack of turnout.

yes deolalikar is basically in hibernation at the moment, so to speak.

I mean lack of turnout on your proof. its completely a different response than deolalikar. his proof attempt basically went "viral".

I was trying to deconstruct why his did and yours didnt/hasnt so far.

Jun

guess mine is through the hamming space, a whole new approach

vzn

4:26 PM

it turns out an email circulated with stephen cook saying that he thought the deolalikar proof looked somewhat credible/serious. that seemed to be part of the spark.

to me, cook was interested in the approach of descriptive complexity & therefore had some enthusiasm for the proof.

it shows a proof can get some traction if [what I call halfway facetiously] an "alpha male" of the field takes an interest in it.

the hamming space is in some ways a new approach. yep.

cook has worked many yrs in descriptive complexity.

anyway Ive taken quite a few steps to publicize your proof and attempt to engage the community, esp the serious TCS community. they are aware of your proof, but are not "biting" so far.

I will list the steps.

1) referred to you on my last blog post, and linked to your blog.

Jun

thanks.

vzn

2) I put a post on hackernews. in fact I believe that may have been where the deolalikar proof may have got some early notice. did get some sizeable response there. & suspect you got a lot of hits on your web page from that.

news.ycombinator.com/item?id=4901849

that site has some pretty good dialogue on the subj. most people dont know much about TCS but there are some hard-core types there who talked about advanced stuff like P/poly, natural proofs, etc. I put in some degree of advocacy and defense of your proof there.

got an amazing 600 hits to my own blog from that single post, and I didnt even have a ref to my site. what someone had done was do a google search, find my blog post referencing your proof, and then post a response saying roughly "this guy takes it seriously". and that msg led to huge spike in traffic in my own blog (which was rather negligible prior to that).

Jun

didn't know there are many hits to the blog.....

vzn

3) had to fight a little on polymath with michael nielsen (owner/founder), but he finally relented. I got a page there and a link from the main page to your proof.

yeah dude check your stats panel! have you seen it at all? you're using wordpress (like me). it has very good statistics including on the referrer logs. you are likely to see a huge spike around the time I posted the hacker news link.

Jun

it's been my first time to use any blog

vzn

4:35 PM

re natural proofs, I point out on hackernews thread that Chow has a great paper challenging it as a barrier. let me dig up those two links shortly.

also rj lipton has an excellent blog post challenging the natural proofs as a barrier.

anyway here is the polymath wiki page. note you can edit it! (if you signup). anyone can.

michaelnielsen.org/polymath1/…

Jun

okay. Like i discussed in the email. I really think sec 5.3 is not a natural proof.

vzn

take a look at your hits sometime, Id be curious about your traffic.

Jun

i will

vzn

re natural proofs-- it will take awhile to figure out if the proof overcomes or succumbs.

I share chow's/liptons skepticism of natural proofs as an insurmountable barrier (ie feel that it is surmountable)

with creativity!

Jun

i'll read Razborov's proof. need to do it concurrently with my regular research job

it's absolutely necessary. think it's the most crucial step

vzn

4:39 PM

now, the community wants you to explain apriori how the approach overcomes natural proofs, but to some degree, thats a wild goose chase.

if the proof is correct, people will spend years dissecting how it overcame the barrier.

Jun

yeah.

vzn

anyway, personally, early on, think your basic approach can overcome natural proofs.

Jun

will read and write it up. let me work on vehicular networking job now.

vzn

sure.

4) publicized your proof on the "theory-cafe" chat room here on this site, which has been around since inception of cstheory se (stackexchange), which now somewhat surprisingly is frozen. a few ppl may have found it that way.

5) wrote to several "alpha males". now of course stasys jukna heard about your proof from you awhile back, that is how I heard about it, while we were chatting in an adjacent chat room about one of stasys' problems.

but I wrote Razborov and Allender asking about your proof.

6) submitted an anonymous post on slashdot, but it didnt make the cut.

it appears to me that Lipton may be alluding vaguely to your proof in a recent blog, where he complains that new claims should try to be more conservative to be taken seriously.

now, youve also been added recently to the woeginger list of P vs NP claims.

win.tue.nl/~gwoegi/P-versus-NP.htm

(dont know how woeginger found you. should have tipped him off myself.) I have been emailing woeginger asking him to add my own blog post outline, but he has not responded at all. maybe my problem is that I dont claim a proof. :p

Jun

4:56 PM

I emailed Stephen Cook asking for opinion. Probably he let the website manager know.

vzn

when did you email cook? what website mgr are you referring to?

unfortunately, cook seems to have never worked (much?) in circuits.

"not his thing"

Jun

i emailed him sometime in July I think. I know he's not in circuit complexity but thought he knows all kinds of resources

vzn

resources like, contacts?

Jun

he's the founder of this problem.

vzn

interestingly, some of his students hang out on tcs.se (abbrev for cstheory stackexchange)

yes of course I know that. what do you mean by resources.

anyway after all that neither you nor Ive managed to create a deolalikar-like "buzz"/viral launch. alas! but maybe that is for the better. who knows... it shows how capricious the community is or can be.

vzn

5:17 PM

here is some of chows writing on natural proofs for the record.

this is a nice short AMS overview but that alludes to his own research:

ams.org/notices/201111/rtx111101586p.pdf

a nice quote from the paper: "Nevertheless, it is my personal opinion that the
optimistic approach is the right one; that is, the
Razborov–Rudich result should be regarded as a
hint, and not a barrier, to separating complexity
classes. The only real barrier is our lack of
imagination."

see, had already done quite a bit of research on the natural proofs barrier in my own line of thinking... so have some counterarguments at my fingertips... even recently wrote a blog post covering it before finding your proof.

Jun

thanks. this is a good overview

vzn

=)

heres his journal article.

math.mit.edu/~tchow/almost.pdf

now, one aspect of your proof is its been done very much independently, you havent collaborated with anyone at all, it cites not very many other papers.

it looks like almost 10yr of independent research and the intermediate results do not seem to have been published.

so that means, if all correct, the community has to "catch up" which is a very formidable proposition.

formidable but surmountable.

I know of some research that is probably very "close" to yours, but its not cited.

but, what I have in mind is cited that much in the circuit literature either.

Ive sketched it out in my blog post. namely slice functions.

Jun

5:41 PM

The shift method considers all the blocked edge sets z of size n^{11/6} in the non-monotone case

vzn

another very funky aspect of circuit theory is that in a sense it may even have been somewhat abandoned by one of its "alpha male" founders, namely razborov.

Jun

This z has a property to contain no n^{1/5}-clique.

vzn

after he came up with bounds on the approximation method, and natural proofs, it appears he's not worked so much in the field of circuits.

Jun

It is not polynomially computable.

vzn

yes, I have to get into the shift method at some pt.

Jun

5:43 PM

According to Timothy Chow's paper, a natural proof needs to deal with property {\cal P} that is efficiently computable

vzn

if it is not polynomial computable or has some high complexity, that may be sufficient to "disarm" the natural proofs barrier.

Jun

Steps 1-2 to 1-4 of BlockedEdges enumerate all z without n^{1/5}-cliques.

vzn

yes, natural proofs seems to define a property in terms of complexity w.r.t a truth table. that seems to be slightly different than complexity w.r.t circuits. have thought that natural proofs concepts need to be reformulated in terms of "operations that work on circuits" instead of truth tables.

Jun

I think this is the reason why it is not a natural proof.

vzn

I would say (as above), maybe dont worry too much about natural proofs.

oh yes let me dig up this lipton blog post on the subj.

again for the record

Jun

5:45 PM

yeah. I really think this proof is not natural

vzn

I think I may have come up with a similar function that operates on CNF/DNF ← →circuits to decompose or construct the circuit, and it has sufficient or "large" complexity to "exceed" the natural proofs barrier.

Jun

Then BlockedEdges chooses z such that the current term t intersected with z at minimum number of nodes. (This is picky: lemma 4.8 and p.43 of thenotes

vzn

liptons blog on "who's afraid of natural proofs":

rjlipton.wordpress.com/2009/03/25/whos-afraid-of-natural-proofs

anyway, cant get to the advanced areas of the proof yet, but dont see any warning flags so far.

just wanted to share some stuff with you & get it on the page for future ref.

am gonna link to this page from the polymath page for future ref.

Jun

yeah. it's a good reason why regular inductive approach is difficult to show a big hardness, but proof can be easily beyond the framework

vzn

the proof is close to "running a complicated algorithm" in ones head, which is very difficult, but exactly what one would expect in a P vs NP proof, and characteristic of other proofs in the field (eg approximation method)....

Jun

5:51 PM

it's been super difficult to find this fixed point approach from the shift method though

vzn

"the pioneer is the one with arrows in his back" wink

vzn

6:07 PM

ps frankenstein was not natural either! :p

vzn

6:25 PM

have always thought, even before your proof, the community is too fixated on natural proofs. its a manifestation of negativism and despair about circuit lower bounds being so hard or "possibly impossible" after an initial wave of enthusiasm in the 1980s.

ps fyi razborov won another new prize!

processalgebra.blogspot.com/2013/01/…

youd think the AMS could put up a simple web page somewhere to announce it, but no! whatever

p 12 of this doc

ams.org/profession/prizebooklet-2013.pdf

vzn

6:59 PM

ah! ok, just figured out a cool trick to link to that page.

ams.org/profession/prizebooklet-2013.pdf#page=14

congratulations sasha =)

Jun

10:04 PM

You've been really helpful!

vzn

thx u2 =)

vzn

10:20 PM

here is one simple question:

what is "Congressus Numernatium"?

Jun

10:39 PM

it's a journal attached to Southeastern International Conference on Combinatorics, Graph Theory, and Computing. math.fau.edu/cgtc/cgtc42/I was there

I was there around 2004 from indiana state univ.

i just started this research, and posted some related papers there

vzn

10:54 PM

does it have reviewer(s)? eg on your papers?

Jun

no. just submitted the three papers.

vzn

ok. any feedback by anyone on those papers?

Jun

i got one feedback from Prof. Anstee at British Columbia about the extension paper posted in the blog

vzn

like an email? in the past?

Jun

he was there in the conference and in my presentaition

vzn

11:01 PM

so you presented & he gave you live feedback?

Jun

yes. he said it's good

vzn

great.. any more detail than that?

do you remember his 1st name?

university of british columbia?

Jun

no. he's an extremal set theorest. we just communicated through mail after it

yes british columbia

vzn

email or postal mail?

Jun

email

vzn

11:05 PM

he'd be a good contact to invite here....

do you have his old email? are you saying you dont remember it too well or that he didnt say much?

Jun

it was long time ago though. i doubt he remembersme

vzn

richard anstee?

its probably worth emailing him again dont you think?

Jun

okay. i will

vzn

this guy?

math.ubc.ca/~anstee

Jun

that's him

vzn

11:08 PM

cool

is any of his research related?

Jun

he's in extremal sets

vzn

yeah.

have you read any of his papers

Jun

i was going to. i didn't because i left indiana state

vzn

ok

heres another angle then. looking at your old papers, its hard to see the motivation of how they apply to P vs NP. but it appears you wrote the papers to built "tools" & results for attacking P vs NP. true?

Jun

yeah. i didn't mention P-NP in the papers.

vzn

11:14 PM

so it appears you had some outline in your head for attacking P vs NP maybe that motivated the papers but isnt mentioned specifically in them?

Jun

i think the old extension paper and the hamming distance papers are good in their topic

vzn

yeah but they seem to exist in isolation. the math may all be correct but the motivation is hard to understand.

Jun

it's difficult to justify the material in the hamming space to link to P-NP

I knew there is something but it's hard to write it absolutely right

First i thought if i find minimum hamming distance between two families of m-sets, then the monotone circuit complexity is done

vzn

Id be curious what anstee said, paraphrased, if you have the old email. understand it was long ago

Jun

wrote up the logic sequence many times, but it was short for the circuit complexity

he just said it's good

then found l-extension is closely linked to cliques

there is shadow (l-set (l <m) contained in some m set in U)

there is cover (ball) on which there is an open problem called isometric problems on m-sets

they are in handbook on combinatorics

but there is no extension defined there

vzn

11:20 PM

Ive been reading circuit theory a long time and it doesnt seem to be connected to the topics of the papers....

I dont recall much mention of circuits in the papers... just skimmed them.... am gonna look a little more now

Jun

you have a = a_1 \wedge a_2, and each a_i has generated l-cliques. You want to find which cliques are generated at a

it takes a theory

vzn

when did you think the isoperimetric problem for m-sets is related to P-NP & circuits?

Jun

The isometric problem is almost the same as finding the minimum hamming distance between two family of m-sets

vzn

am going to just list out the papers here for notes

Jun

by this a=a_1 \wedge a_2 observation, i though minimum hamming distance between the generated cliques at both a_i solves the clique complexity

the hamming distance paper is also posted in the blog

but minimum hamming distance is a bit short.

then i found l-extension is it

vzn

11:30 PM

it looks like the pdf of your paper prevents "save" and also copy-and-paste

Jun

which paper?

vzn

your main paper.

its probably a setting in your pdf generation.

copy protected.

Jun

probably refresh browser / restart pc to try again?

vzn

did you use latex? think its a setting

Jun

yes i do

hamming distance paper?

P-NP paper?

vzn

11:33 PM

no main paper "computing cliques is intractable"

how did you 1st hear of the isoperimetric set problem?

Jun

noga alon said so

vzn

no kidding

where

Jun

it was also in the handbook of combinatorics too

vzn

[funky I just closed/restarted firefox & it fixed the copy/paste issue. geez]

noga alon said what about isoperimetric sets? in one of his papers?

Jun

it's long time ago. one of my colleagues at ind state recommended me to contact him. talked through a couple of mail

vzn

11:38 PM

did you tell him you wanted to work on P vs NP?

Jun

i don't remember the conversation. probably i mentioned i'm trying to develop a theory for circuit complexity

vzn

do you think he's mentioned isoperimetric set problem in any of his papers?

have you read any of his papers?

Jun

i know him because the monotone circuit bound is Alon-Boppana

i talked to Boppana a bit too

vzn

yeah but havent heard of any of their papers referring to isoperimetric set problem ["ISP"]

Jun

i think it's open because the handbook said so if i remember correctly

vzn

11:42 PM

ISP is open? do you think you've resolved it?

Jun

the hamming distance paper gives you asymptotic bound. in a sense, it poses a partial result

vzn

yes trying to trace the lineage of ideas. it will be helpful.

Jun

ISP 's distance can be constant, close to m. I showed if the sparsity is not too large, it's o(m), actually O(m exp(log-2 log m))

the posted paper only shows O(m / log m)

vzn

the papers of your own you cite in your main paper do not match the titles of the other papers on your site.

are any the same?

Jun

i will check and correct

vzn

11:45 PM

for ref, you cite yourself in main paper in following refs

Jun

ok. let me eat dinner

vzn

[3] J. Fukuyama, "On the Extension of an m-Set Family", Congressus Numernatium,
Vol. 173, pp. 35-41, 2005.

[5] J. Fukuyama, "On the Topology of The Hamming Distance between Set Systems",
Congressus Numernatium, Vol. 161, pp. 41-63, 2003.

[6] J. Fukuyama, "Some New Facts about the Hamming Space", Congressus Numernatium,
Vol. 168, pp. 21-31, 2004.

2 papers on your site:

The Hamming Distance between Two Uniform Set
Systems

On the Extension of an m-set Family

Transcript for