Skip to content

Papers for the end of the semester talks

November 14, 2012

Below are papers for the end of the semester talks. It offers both classical as well as cutting edge results. The list will grow with time. I suggest you’ll read the abstracts, choose a paper and let me know if you want it so I will reserve it for you. Recall that the talks are in individuals, are on the board (not presentations) and should take 50-90 minutes. Most importantly – they should be great!

Circuit Lower Bounds

An Explicit Lower Bound of 5n – o(n) for Boolean Circuits by Kazuo Iwama, Oded Lachish, Hiroki Morizumi and Ran RazReserved by Daniel Reichman.

Circuit Lower Bounds for Merlin-Arthur Classes by Rahul SanthanamReserved by Inbal Livni.

On the Correlation of Parity and Small-Depth Circuits (and references therein) by Johan Hastad.

Fixed-Polynomial Size Circuit Bounds by Lance Fortnow, Rahul Santhanam and Ryan Williams

The Monotone Circuit Complexity of Boolean Functions by Noga Alon and Ravi B. Boppana  / Alexander A. Razborov.

Lower Bounds for Matrix Product, in Bounded Depth Circuits with Arbitrary Gates by Ran Raz and Amir Shpilka.

Lower Bounds for Matrix Product by Amir ShpilkaReserved by Asaf Ziv.

Elusive Functions and Lower Bounds for Arithmetic Circuits by Ran Raz.

Lower Bounds on Arithmetic Circuits via Partial Derivatives by Noam Nisan and Avi WigdersonReserved by Ron Rothblum.

A Lower Bound on the Mod 6 Degree of the OR Function by Gabor Tardos and David A. Mix BarringtonReserved by Igor Shinkar.

Hardness Amplification within NP by Ryan O’DonnellReserved by Elazar Goldenberg.


Natural Proofs (see also Chapter 23 in Arora-Barak book) by Alexander A. Razborov and Steven Rudich.

Algebrization: A New Barrier in Complexity Theory by Scott Aaronson and Avi WigdersonReserved by Shlomo Jozeph.

Limits on Alternation-Trading Proofs for Time-Space Lower Bound by Samuel Buss and Ryan Williams.

Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators by Andrew Drucker.

Natural Proofs versus Derandomization by Ryan WilliamsReserved by Avishay Tal.

Hardness vs. Randomness / Pseudorandom Generators / Derandomization

Hardness vs. Randomness by Noam Nisan and Avi Wigderson. Reserved by Yuval Madar.

Pseudorandomness from Shrinkage by Russell Impagliazzo, Raghu Meka and David ZuckermanReserved by Ilan Komargodski.

Better Pseudorandom Generators from Milder Pseudorandom Restrictions by Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan and Salil VadhanReserved by Tal Wagner.

A Derandomized Switching Lemma and an Improved Derandomization of AC0 by Luca Trevisan and TongKe Xue.

BPSPACE(S) ⊆ DSPACE(S^{3/2}) by Michael Saks and Shiyu ZhouReserved by Dean Doron.

Undirected Connectivity in Log-Space by Omer ReingoldReserved by Yuval Tanny.

Pseudorandom Generators for CC_0[p] and the Fourier Spectrum of Low-Degree Polynomials over Finite Fields by Shachar Lovett, Partha Mukhopadhyay and Amir Shpilka.

Poly-Logarithmic Independence Fools AC0 Circuits by Mark BravermanReserved by Eylon Yogev.

Graph NonIsomorphism has Subexponential Size Proofs unless the Polynomial-Time Hierarchy Collapses by Adam R. Klivans and Dieter van MelkebeekReserved by Sagie Benaim.

Pseudo-random Generators for All Hardnesses by Christopher UmansReserved by Bharat Ram Rangarajan.

Randomness vs. Time: De-Randomization Under a Uniform Assumption by Russell Impagliazzo and Avi WigdersonReserved by Uri Sherman.

Easiness Assumptions and Hardness Tests: Trading Time for Zero Error by Valentine KabanetsReserved by Rani Izsak

Randomness in Linear Space by Noam Nisan and David Zuckerman. Reserved by Or Lotan.

On Approximate Majority and Probabilistic Time by Emanuele Viola

Other Neat (and Related) Results in Complexity (some of which we used without a proof)

IP = PSPACE (see also Theorem 8.19 in Arora-Barak book) by Adi Shamir / Carsten Lund, Lance Fortnow, Howard Karloff and Noam Nisan. (it is instructive to check out Or Meir’s proof as well). Reserved by Shani Nitzan.

Non-Deterministic Exponential Time has Two-Prover Interactive Protocols (that is, NEXP=MIP – the genesis of the PCP Theorem) by Laszlo Babai, Lance Fortnow and Carsten Lund. Reserved by Anat Ganor.

Bounded-Width Polynomial-Size Branching Programs Recognize Exactly Those Languages in NC1 (aka Barrington’s Theorem) by David A. BarrringtonReserved by Dima Kogan.

Hierarchy Theorems for Probabilistic Polynomial Time by Lance Fortnow and Rahul Santhanam.

The Random Oracle Hypothesis is False by Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Hastad, Desh Ranjan and Pankaj Rohatgi. Reserved by Tom Gur.

PP is as hard as the Polynomial-Time Hierarchy  by Seinosuke Toda (for a proof, see also chapter 17  in Arora-Barak book). Reserved by Noa Ben-Zvi.

The Complexity of Computing the Permanent  by Leslie Valiant (for a proof, see also chapter 17 in Arora-Barak book). Reserved by Ami Mor.

From → Uncategorized

Leave a Comment

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

%d bloggers like this: