Communities and Collections
Posts
Post has shared content
Public
Norbert Blum's claimed proof that P=/=NP appears to be fatally flawed.
For those who have not been following the discussions on this topic, here is a rough summary of the current state of affairs as I understand them (those last four words being an important qualification).
(i) Blum's strategy is to show that a certain technique, related to but not quite the same as, Razborov's method of approximations for obtaining lower bounds on the monotone circuit complexity of monotone functions (this means you're allowed AND gates and OR gates but not NOT gates) has the following interesting property: if you can use it to obtain a superpolynomial lower bound for the monotone circuit complexity of a monotone function, then that automatically implies a superpolynomial bound for the general circuit complexity.
(ii) The method related to Razborov's method can be used to show that the monotone circuit complexity of any monotone function that outputs 1 for all cliques of size k and 0 for all complete (k1)partite graphs is superpolynomial.
(iii) Tardos showed that there exists such a function with polynomial circuit complexity.
Facts (ii) and (iii) demonstrate that Blum's strategy cannot work.
This problem seems to have been pointed out first by Gustav Nordh in the discussion at cstheory stackexchange and noticed independently (and pretty well immediately after he looked at the paper) by Razborov himself. And it is not a wise person who bets against Razborov.
For those who have not been following the discussions on this topic, here is a rough summary of the current state of affairs as I understand them (those last four words being an important qualification).
(i) Blum's strategy is to show that a certain technique, related to but not quite the same as, Razborov's method of approximations for obtaining lower bounds on the monotone circuit complexity of monotone functions (this means you're allowed AND gates and OR gates but not NOT gates) has the following interesting property: if you can use it to obtain a superpolynomial lower bound for the monotone circuit complexity of a monotone function, then that automatically implies a superpolynomial bound for the general circuit complexity.
(ii) The method related to Razborov's method can be used to show that the monotone circuit complexity of any monotone function that outputs 1 for all cliques of size k and 0 for all complete (k1)partite graphs is superpolynomial.
(iii) Tardos showed that there exists such a function with polynomial circuit complexity.
Facts (ii) and (iii) demonstrate that Blum's strategy cannot work.
This problem seems to have been pointed out first by Gustav Nordh in the discussion at cstheory stackexchange and noticed independently (and pretty well immediately after he looked at the paper) by Razborov himself. And it is not a wise person who bets against Razborov.
Add a comment...
Also trying to verify, but the error "Connection to Redis failed after 1 failures." doesn't sound so inspiring.
Post has shared content
We are devastated to share that our dear teammate Joe Philley passed away yesterday. Joe was the backbone of the Ingress community and a friend to all. Through his work he connected with thousands of Ingress Agents from all walks of life and brought smiles to many faces.
We’ve been in touch with Joe’s family and we’ll share additional details on memorial services as we receive them. Our thoughts and deepest condolences go out to Joe's family. We will miss you, Agent Delta102.
#RIPJoe
We’ve been in touch with Joe’s family and we’ll share additional details on memorial services as we receive them. Our thoughts and deepest condolences go out to Joe's family. We will miss you, Agent Delta102.
#RIPJoe
Add a comment...
Post has shared content
PLEASE SHARE WIDELY TO THOSE IT MAY CONCERN
would anyone be willing to participate in an experimental study where you would treat your mufg for, say, four weeks according to a preset plan imposed on you (e.g. 50 L8 resonators in one week, 30 jarvis in the next and so on), report the current number of items every, say, 12 hours on a simple online form, and otherwise not touch the mufg? it would be quite restrictive  essentially you give the power how your capsule is used over to a third party and execute their wishes to the letter  and you could not really use the capsule at your own discrection and fluctuating ideas. but a study of this sort could give some robust and reliable numbers to get a reliable and initial estimates to answer questions like:
* do different capsules have different interest rates and if so, which?
* do different capsules have different interest intervals, and if so, which?
* do items of different rarity multiply differently?
* is there a fixed or rather variable interest rate?
* does it matter if the capsule contains mixed items or is it better to only load one type of item?
* does it impede replication if i look into the capsule often or does it not matter?
also such an experimental study may serve as a precedent for future studies about ingress items (including subsequent studies on the mufg that can answer additional questions and test very specific hypotheses) and make it easier in the future to hack item regularities.
i have thought about setting up something like this, but have so far hesitated, because i didn't know whether it is worth the effort if not many people would agree to such a capsule regimen. i however still believe it would be useful. one main obstacle to data analysis of mufg events so far is that, people display a huge variation in what they put in, for how long they let it sit, etc... the analysis of data like this, however requires huge numbers of observations, very, very precise and reliable data and, most importantly, certain distributions of different capsule use parameters. but an experimental study, where some things are tightly controlled and planned out, may give quality answers with a smaller sample of mufg capsule behavior observations. so: how many people would be up for a study of this kind? please answer the poll, and indicate if you would be in general willing to participate in such a study. and leave your comments in the ... wel...er... comments section.
would anyone be willing to participate in an experimental study where you would treat your mufg for, say, four weeks according to a preset plan imposed on you (e.g. 50 L8 resonators in one week, 30 jarvis in the next and so on), report the current number of items every, say, 12 hours on a simple online form, and otherwise not touch the mufg? it would be quite restrictive  essentially you give the power how your capsule is used over to a third party and execute their wishes to the letter  and you could not really use the capsule at your own discrection and fluctuating ideas. but a study of this sort could give some robust and reliable numbers to get a reliable and initial estimates to answer questions like:
* do different capsules have different interest rates and if so, which?
* do different capsules have different interest intervals, and if so, which?
* do items of different rarity multiply differently?
* is there a fixed or rather variable interest rate?
* does it matter if the capsule contains mixed items or is it better to only load one type of item?
* does it impede replication if i look into the capsule often or does it not matter?
also such an experimental study may serve as a precedent for future studies about ingress items (including subsequent studies on the mufg that can answer additional questions and test very specific hypotheses) and make it easier in the future to hack item regularities.
i have thought about setting up something like this, but have so far hesitated, because i didn't know whether it is worth the effort if not many people would agree to such a capsule regimen. i however still believe it would be useful. one main obstacle to data analysis of mufg events so far is that, people display a huge variation in what they put in, for how long they let it sit, etc... the analysis of data like this, however requires huge numbers of observations, very, very precise and reliable data and, most importantly, certain distributions of different capsule use parameters. but an experimental study, where some things are tightly controlled and planned out, may give quality answers with a smaller sample of mufg capsule behavior observations. so: how many people would be up for a study of this kind? please answer the poll, and indicate if you would be in general willing to participate in such a study. and leave your comments in the ... wel...er... comments section.

votes visible to Public
73%
I would participate in such a study.
27%
I would NOT participate in such a study.
Add a comment...
Post has attachment
And that's how software is contracted — an insightful analysis.
Add a comment...
Post has attachment
+Norman Ramsey Could the SIGPLAN LaTeX class live on Github? We could then share, say, doubleblinding setup in a fork (re: https://www.facebook.com/henglein/posts/1086705224679874?comment_id=1087473867936343&offset=50&total_comments=110&comment_tracking=%7B%22tn%22%3A%22R9%22%7D). We'd have had license text one year ago.
Add a comment...
Post has shared content
WHO OWNS YOUR RESEARCH?
What should be the role of associations like the ACM? Are they publishers who market science? Or should they strive to make research results available to all free of charge? Scientific publishing is about to undergo radical changes. Take this poll: http://goo.gl/vlCtn2 Make your voice heard!
What should be the role of associations like the ACM? Are they publishers who market science? Or should they strive to make research results available to all free of charge? Scientific publishing is about to undergo radical changes. Take this poll: http://goo.gl/vlCtn2 Make your voice heard!
Post has attachment
Communications between English and Germans. I wonder where I would fit, and where the average Italians would.
Add a comment...
Post has shared content
Tom Ball, Ras Bodik, +Greg Morrisett, and I are organizing a new kind of programming languages conference. We already have several excellent conferences, but they are focused on incremental bits of novelty. We want to create a new kind of venue that complements these: to present and discuss bigpicture questions and longrunning programs; to view progress along the long arc of a research effort. The conference is May 36, 2015 in lovely Asilomar (on the Pacific Coast), CA, USA.
If this sounds interesting, please: don't just +1 it, reshare it. Why? To keep costs down and retain ownership of the conference with the community, we are independent, not affiliated with any organizations. That means you are the only PR channel we have. So please do us a favor. Thanks.
If this sounds interesting, please: don't just +1 it, reshare it. Why? To keep costs down and retain ownership of the conference with the community, we are independent, not affiliated with any organizations. That means you are the only PR channel we have. So please do us a favor. Thanks.
Add a comment...
Post has shared content
SIGPLAN members and PLDI authors, please take a minute to fill this form asking your feedback about changes in the publication model for PLDI:
http://goo.gl/forms/mUcFVWq5Gd
http://goo.gl/forms/mUcFVWq5Gd
Add a comment...
Wait while more posts are being loaded