Skip to content

Winner Of 2018 Knuth Prize Is:

August 16, 2018

A great choice

Cropped from 2016 KTH grant news source

Johan Håstad is the winner of the 2018 Donald E. Knuth Prize. We were going to keep you in suspense, but one of our “blog invariants” is to lead with the name(s) of those who are featured. He is very well deserving. And he has proved many wonderful theorems.

Today the entire GLL editorial staff would like to thank the committee for their great selection.

They were Allan Borodin, Alan Frieze, Avrim Blum, Shafi Goldwasser, Noam Nisan, and Shanghua Teng (chair). It must be hard to select a Knuth Prize winner, because there are so many strong candidates. So many. This year’s choice is an excellent one.

The Knuth Prize is “for outstanding contributions to the foundations of computer science.” The description used to mention that educational contributions such as textbooks and students could be considered as part of the impact. Usually one thinks of “education” as being for aspiring students or for the public outside of us researchers. But it strikes us that Johan has been pre-eminent for educating many currently within the field on what to pursue.

En-passant, we are glad to announce that Harvey Friedman has today posted a full draft paper, “Tangible Mathematical Incompleteness of ZFC,” which we previewed. We will be giving it further coverage with his continued expository assistance.

Being Best Possible

We draw our feeling on Johan’s role from the first two paragraphs about his “transformative techniques” in the long-form Knuth Prize citation. It first describes his famous 1986 “Switching Lemma” for lower bounds on the parity function. The first super-polynomial lower bounds on constant-depth Boolean circuits (of unbounded fan-in) had been shown in 1981 by Merrick Furst, James Saxe, and Mike Sipser. Andy Yao in 1985 obtained exponential size lower bounds that were strong enough to give oracles separating the polynomial hierarchy from polynomial space. But Johan sharpened the exponent using what has remained the best technique—even this 2018 extension tells us so.

His lemma concerns how a random assignment to many of the variables of a DNF causes it to become much simpler. See here for a modern explanation of the details. His original proof was a great achievement through its handling of the probabilistic method. The details were quite delicate because of the need to control certain technical issues. In any probabilistic proof one must be careful not to destroy independence, since keeping certain events independent is vital to make such proofs work. Johan’s original proof worked hard at this. More recent proofs have been able to skirt some of the vicissitudes, but they all prove the following pretty result:

Theorem 1 Any Boolean circuit of depth {k+1} for parity requires size at least

\displaystyle  2^{hn^{1/k}}

for some positive constant {h}.

The citation’s next paragraph describes Johan’s relation to the PCP Theorem. Now he is absent from that Wikipedia page and from a popular illustrated history. But he refined it to plutonium. This did not come suddenly with the 1996 paper, “Clique is hard to approximate within {n^{1-\epsilon}}” and its Gödel Prize-winning 1997 successor, “Some Optimal Inapproximability Results” mentioned in the citation. I (Ken adding to what Dick wrote) recollect associating ‘Håstad’ to the importance of “free bits” earlier in the 1990s and the influence of his FOCS 1993 paper, “The Shrinkage Exponent is 2.” This memory may include a conflation of the influence on Håstad of Ran Raz’s STOC 1995 paper on the parallel repetition theorem. In any event, the power of finding best-possible results shines through in the citation:

As complexity-theoretical breakthroughs, Håstad constructed almost optimal PCPs, where optimality holds with respect to parameters such as amortized free-bit complexity and total number of queries. He then established optimal “approximation resistance” of various constraint satisfaction problems—namely that one cannot do better in terms of worst-case performance ratio than the basic input-oblivious algorithm that simply picks a random assignment to the variables. These PCPs led to optimal inapproximability results for MaxClique, MaxLin2, and Max3SAT as well as to the best known hardness results for approximating other optimization problems such as MaxCut. His proofs introduced a treasure trove of ideas—in particular the Fourier analytic techniques—that has influenced nearly all subsequent work in hardness of approximation.

The citation’s third paragraph notes his role in proving the polynomial-time equivalence of one-way functions and pseudorandom generators. The history is that Russell Impagliazzo, Leonid Levin, and Mike Luby proved this first for nonuniform circuits—I remember a seminar talk by Russ at Cornell in late 1986 or 1987 when this was still in process. Then Johan for STOC 1990 saw how to push it to work in the uniform case.

Open Problems

What more is known about the constant {h} in the lower bounds for parity, as {k} grows? We find {h \geq 0.143781} (all {k}) here, and a simple upper bound asymptotic to {1} is easy to see as done here.

Johan recently pushed the lower bounds on parity in a different direction, improving the maximum {\epsilon} such that circuits of depth {k} and size {S} can achieve agreement {\frac{1}{2} + \epsilon} with the parity function. What further usefulness in complexity theory might pushing this have? In any event we all thank him for his beautiful work and congratulate him on winning this year’s Knuth Prize.

[some word changes]


Desperately Seeking Integers

August 6, 2018

A few twists on Turing’s proof of undecidability of predicate calculus

By permission of Rich Longmore,
artist, blog source

Alan Turing presaged Stephen Cook’s proof of {\mathsf{NP}}-completeness of {\mathsf{SAT}.} Turing reduced the halting problem for his machines to the decision problem of the first-order predicate calculus, thus showing (alongside Alonzo Church) that the latter is undecidable. Cook imitated Turing’s reduction at the level of propositional calculus and with a nondeterministic machine.

Today we present a version of Turing’s proof and show how it answers a side issue raised in our previous post.
Read more…

A Quest For Simple Hard Statements

July 28, 2018

Made-to-order statements that are not so simple

Harvey Friedman is a long-standing friend who is a world expert on proofs and the power of various logics. This part of mathematics is tightly connected to complexity theory. This first mention of his work on this blog was a problem about the rationals that says nothing of “logic” or “proofs.”

Today Ken and I would like to introduce some of Harvey’s work in progress. Update 8/16/18: Harvey has posted a full draft paper, “Tangible Mathematical Incompleteness of ZFC.”
Read more…

Group Theory Is Tough

July 18, 2018

Some musings on group theory

Isaacs honorary conference source

Martin Isaacs is a group theorist emeritus from the University of Wisconsin, Madison. I just picked up a copy of his 2008 book, Finite Group Theory. Simple title; great book.

Today I want to make a few short comments about group theory.

I always hated group theory. Well not really hated it. But I have never been able to get decent intuition about groups.
Read more…

You Cannot Do That

July 11, 2018

How hard is it to prove certain theorems?

Maruti Ram Murty is a famous number theorist at Queen’s University in Kingston, Canada. He is a prolific author of books. His webpage has thumbnails of over a dozen. He has an Erdős number of 1 from two papers—very impressive.

Today Ken and I want to talk about a not-so-recent result of his that is also a “lower bound” type result.
Read more…

Local Hams in La Jolla

July 2, 2018

A workshop on quantum computing at UCSD

Cropped from workshop poster

Dorit Aharonov, David Gosset, and Thomas Vidick did standup for three-and-a-half days in La Jolla earlier this year. They are not listed among the many distinguished actors who have performed at the La Jolla Playhouse on the UCSD campus. Nor were they observed by any of the Hollywood talent-search agencies in town, at least not that we know. But they were applauded by numerous computer science and physics students attending the the March 19–22 UCSD “Spring School on Quantum Computation” which they led.

Today we report on the meeting and discuss an important problem springing from condensed matter physics: the Local Hamiltonian (LH) problem.
Read more…

Muffins and Integers

June 21, 2018

A novel cake-cutting puzzle reveals curiosities about numbers

Alan Frank introduced the “Muffins Problem” nine years ago. Erich Friedman and Veit Elser found some early general results. Now Bill Gasarch along with John Dickerson of the University of Maryland have led a team of undergraduates and high-schoolers (Guangqi Cui, Naveen Durvasula, Erik Metz, Jacob Prinz, Naveen Raman, Daniel Smolyak, and Sung Hyun Yoo) in writing two new papers that develop a full theory.

Today we discuss the problem and how it plays a new game with integers.
Read more…