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

5:40 AM
welcome to the club!
JF!

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

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.

6:04 AM
eg:
(pentium 4)

10 hours later…
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 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...

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.

Can you please tell me how you show figures?

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

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

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.

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

4:15 PM
cool =)

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}

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

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

ok! lets neither of us get in trouble =)

Are marks clear for you?

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.

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

now, one general issue with the proof.
which will relate to its acceptance by the "community".

means "cs theory" or "combinatorics"?
it's "cs theory" since it is the computer science problem

you mean this stackexchange site?
cstheory= computer science theory.

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

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.

yes

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.

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

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.

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

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.

thanks.

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

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

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.

it's been my first time to use any blog

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.

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

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

i will

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!

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

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.

yeah.

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

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

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

4:56 PM
I emailed Stephen Cook asking for opinion. Probably he let the website manager know.

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"

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

resources like, contacts?

he's the founder of this problem.

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.

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

thanks. this is a good overview

=)
heres his journal article.
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.

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

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.

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

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.

It is not polynomially computable.

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

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

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

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

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.

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

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

5:45 PM
yeah. I really think this proof is not natural

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.

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

liptons blog on "who's 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.

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

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

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

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

6:07 PM
ps frankenstein was not natural either! :p

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!
youd think the AMS could put up a simple web page somewhere to announce it, but no! whatever
p 12 of this doc

6:59 PM
ah! ok, just figured out a cool trick to link to that page.
congratulations sasha =)

3 hours later…
10:04 PM
You've been really helpful!

thx u2 =)

10:20 PM
here is one simple question:
what is "Congressus Numernatium"?

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

10:54 PM
does it have reviewer(s)? eg on your papers?

no. just submitted the three papers.

ok. any feedback by anyone on those papers?

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

like an email? in the past?

he was there in the conference and in my presentaition

11:01 PM
so you presented & he gave you live feedback?

yes. he said it's good

great.. any more detail than that?
do you remember his 1st name?
university of british columbia?

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

email or postal mail?

email

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?

it was long time ago though. i doubt he remembersme

richard anstee?
its probably worth emailing him again dont you think?

okay. i will

this guy?

that's him

11:08 PM
cool
is any of his research related?

he's in extremal sets

yeah.
have you read any of his papers

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

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?

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

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?

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

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

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

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

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

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

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

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

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

am going to just list out the papers here for notes

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

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

which paper?

your main paper.
its probably a setting in your pdf generation.
copy protected.

probably refresh browser / restart pc to try again?

did you use latex? think its a setting

yes i do
hamming distance paper?
P-NP paper?

11:33 PM
no main paper "computing cliques is intractable"
how did you 1st hear of the isoperimetric set problem?

noga alon said so

no kidding
where

it was also in the handbook of combinatorics too

[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?

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

11:38 PM
did you tell him you wanted to work on P vs NP?

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

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

i know him because the monotone circuit bound is Alon-Boppana
i talked to Boppana a bit too

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

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

11:42 PM
ISP is open? do you think you've resolved it?

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

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

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)

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?

i will check and correct

11:45 PM
for ref, you cite yourself in main paper in following refs

ok. let me eat dinner

[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