A guest post from Dieter van Melkebeek This week, about 50 computer scientists gather at Schloss Dagstuhl for a seminar on "Complexity of Boolean Functions."...
214
Lance Fortnow
fortnow
Apr 2, 2004 9:28 pm
Another Guest Post from Dieter van Melkebeek Thursday morning, Shuki Bruck gave the first talk at the workshop that dealt with actual Boolean circuits. He...
215
Lance Fortnow
fortnow
Apr 5, 2004 1:10 pm
Another Guest Post from Dieter van Melkebeek Thursday morning, Shuki Bruck gave the first talk at the workshop that dealt with actual Boolean circuits. He...
216
Lance Fortnow
fortnow
Apr 5, 2004 1:10 pm
The Blum speed-up theorem states that there exists a computable language L such that if L is in time t(n) then L is in time log(t(n)). The log function can be...
217
Lance Fortnow
fortnow
Apr 7, 2004 2:04 am
A friend of mine from college became a science writer for various newspapers and magazines. Once he told me about his two biggest complaints about scientists. ...
218
Lance Fortnow
fortnow
Apr 11, 2004 4:48 pm
A friend of mine from college became a science writer for various newspapers and magazines. Once he told me about his two biggest complaints about scientists. ...
219
Lance Fortnow
fortnow
Apr 11, 2004 4:48 pm
The University of Chicago Bookstore has asked for textbook requests for the fall quarter by the middle of next month instead of during the summer as in past...
220
Lance Fortnow
fortnow
Apr 13, 2004 3:29 pm
The University of Chicago Bookstore has asked for textbook requests for the fall quarter by the middle of next month instead of during the summer as in past...
221
Lance Fortnow
fortnow
Apr 13, 2004 3:29 pm
March Edition Primality is a problem hanging onto a cliff above P with its grip continuing to loosen each day. - Paraphrased from a talk given by Juris...
222
Lance Fortnow
fortnow
Apr 13, 2004 11:29 pm
March Edition Primality is a problem hanging onto a cliff above P with its grip continuing to loosen each day. - Paraphrased from a talk given by Juris...
223
Lance Fortnow
fortnow
Apr 19, 2004 1:42 pm
Many years ago, an Israeli graduate student made the rounds and gave talks at several US universities. When he arrived in Chicago, he asked me if Americans...
224
Lance Fortnow
fortnow
Apr 21, 2004 1:54 pm
Help me solve this problem, write the paper with me, get an Erds number of 3 and it won't cost you a cent . We can have #P functions hard for the...
225
Lance Fortnow
fortnow
Apr 21, 2004 1:54 pm
Many years ago, an Israeli graduate student made the rounds and gave talks at several US universities. When he arrived in Chicago, he asked me if Americans...
226
Lance Fortnow
fortnow
Apr 22, 2004 3:41 pm
Help me solve this problem, write the paper with me, get an Erds number of 3 and it won't cost you a cent . We can have #P functions hard for the...
227
Lance Fortnow
fortnow
Apr 22, 2004 3:42 pm
Alan Kay will receive the 2004 Turing award . It can't always be a theorist. Registration is open for the 2004 Conference on Computational Complexity . The...
228
Lance Fortnow
fortnow
Apr 23, 2004 7:55 pm
From Bill Gasarch: There are some more novelty songs about theory (aside from THE LONGEST PATH ) from the Washington CSE Band . The best one is THEORY GIRL . ...
229
Lance Fortnow
fortnow
Apr 25, 2004 12:11 pm
From the PODC mailing list via Harry Buhrman. Usually the winners are kept secret until the ICALP or STOC conference but the PODC mailing list has already...
230
Lance Fortnow
fortnow
Apr 25, 2004 12:11 pm
From Bill Gasarch: There are some more novelty songs about theory (aside from THE LONGEST PATH ) from the Washington CSE Band . The best one is THEORY GIRL . ...
231
Lance Fortnow
fortnow
Apr 26, 2004 2:31 pm
The Unofficial Guide to Walt Disney World 2004 gives a lesson on complexity by describing the optimal tour of the Magic Kingdom as a traveling salesman...
232
Lance Fortnow
fortnow
Apr 28, 2004 1:56 pm
A reader asks why Gafni and Borowski did not publish their paper in a journal and become eligible for the Gdel Prize . I wish this was an isolated incident but...
233
Lance Fortnow
fortnow
Apr 29, 2004 3:00 pm
A reader asks why Gafni and Borowski did not publish their paper in a journal and become eligible for the Gdel Prize . I wish this was an isolated incident but...
234
Lance Fortnow
fortnow
Apr 29, 2004 3:00 pm
[A report from weblog correspondent Bill Gasarch] On Wednesday April 28 there was a SYMPOSIUM HONORING DR. RICHARD M. KARP at Drexel University in...
235
Lance Fortnow
fortnow
May 4, 2004 12:24 am
[A report from weblog correspondent Bill Gasarch] On Wednesday April 28 there was a SYMPOSIUM HONORING DR. RICHARD M. KARP at Drexel University in...
236
Lance Fortnow
fortnow
May 4, 2004 12:24 am
Some required reading if you haven't seen it yet, a New York Times article on how America has lost some of its scientific leadership role over the rest of the...
237
Lance Fortnow
fortnow
May 4, 2004 11:03 am
Some required reading if you haven't seen it yet, a New York Times article on how America has lost some of its scientific leadership role over the rest of the...
238
Lance Fortnow
fortnow
May 7, 2004 2:11 pm
I'm moving my web hosting service--if you can read this you are accessing the new host. I will wait a day or two to post again until the changeover is...
239
Lance Fortnow
fortnow
May 7, 2004 2:14 pm
A readers asked about the complexity of games like Go and Chess. David Eppstein has a nice site giving a short description and references to a number of...
240
Lance Fortnow
fortnow
May 8, 2004 12:13 pm
The Journal of the ACM has started asking for page charges. Author's institutions or corporations are requested to honor a page charge of $60.00 per printed...
241
Lance Fortnow
fortnow
May 8, 2004 12:13 pm
A readers asked about the complexity of games like Go and Chess. David Eppstein has a nice site giving a short description and references to a number of...
242
Lance Fortnow
fortnow
May 8, 2004 12:13 pm
The Journal of the ACM has started asking for page charges. Author's institutions or corporations are requested to honor a page charge of $60.00 per printed...
