I just saw in “Shtetl Optimized” that the Linial-Nisan conjecture regarding AC^0 circuits have been proved by Mark Braverman. Scott’s post describes the conjecture as well as related open problems in computational complexity. (Scott offers  $100 for a proof that Fourier Checking is not in AM, $200 for a proof that it’s not in PH.) After many years of no news the case of depth two circuits was proved by Louay Bazzi about a year ago and a simpler proof was found by Razborov. Here is a post on the depth two case from “In theory“. 

Bazzi             m2


L. Bazzi                     M. Braverman

 A bit more: There are further posts about this development in  Computational Complexity  (by Lance) and in In theory.

All three posts describe the results in some details, Luca discusses connection with random 3SAT problems and Scott mentions some natural connections with quantum computation. Scott also gives a link to his related FOCS tutorial on the “polynomial method”.

Here is the description of Braverman’s result taken from “computational complexity”.

“Braverman shows that no poly-logarithmically independent distribution can be distinguished from a truly random distribution by a polynomial-size constant-depth circuit.

A r-independent distribution over binary strings of length n means that for every set of r bits are uniformly distributed over the 2r possible values for those bits. We can create r-independent distributions using O(r log n) truly random bits.

Braverman shows that no depth-d size-m circuit of AND, OR and NOT gates can distinguish between a truly uniform distribution and any r-independent distribution with r = (log m)O(d2). ”


Here is a problem (perhaps silly) that comes to mind:  Is the conclusion of the Linial-Nisan conjecture (=Braverman’s result) holds for Monotone TC^0 circuits, namely to circuits with (monotone) threshold gates? (I may ask around.)   (As Luca pointed out, we can certainly cannot hope for the full statement of the theorem; I am not sure about a weak version.)

3 thoughts on “News

  1. Pingback: Bounded Independence, AC0, and Random 3SAT « in theory

  2. Pingback: A Little More on Boolean Functions and Bounded Depth Circuits « Combinatorics and more

  3. Pingback: The attention economy for scientific work « Algorithmic Game Theory

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s