Adding Dollar Signs

Chris Umans is the program chair of the upcoming Computational Complexity Conference, and has put together a terrific-looking program. He was aided by the rest of his program committee: Iftach Haitner, Troy Lee, Dana Moshkovitz, Jakob Nordström, Ryan O’Donnell, Ben Reichardt, Madhu Sudan, Amnon Ta-Shma, Jacobo Torán, and Emanuele Viola. We owe them for their hard work. Thanks.

Today I want to do something that we rarely do at GLL: report instantly on papers that have just been accepted at a conference.

I looked just now at the 29 papers accepted to CCC 2013. They all look intriguing, but I selected just a few for quick comments. Mostly I added the $’s that were missing so the abstracts would compile in LaTeX. I apologize to all whose abstracts are not included—see the full list of all papers here for the abstracts. Or see this Wordle for a “summary” of all the papers:

I also want to say that I surmise—with no inside knowledge—that lots of really cool papers were not accepted. I have been there myself, many times, so I know that some papers were unable to be accepted, yet have interesting results. My advice is hang in there and try again. I have reported before that the Nobel award winning paper on the polymerase chain reaction (PCR) technique for DNA sequencing by Kary Mullis was rejected by the journals Science and Nature before being published.

The Papers

Here are the papers, with additional comments on some. We will no doubt discuss some of these in the near future in further detail.

The Correct Exponent for the Gotsman-Linial Conjecture
Daniel Kane

On Rigid Matrices and U-Polynomials
Noga Alon, Gil Cohen I have thought too many hours about rigid matrices. This is another case of “almost all of them have the property, but good luck proving an explicit one does.” Very important problem.

Formulas are exponentially stronger than monotone circuits in non-commutative setting
Pavel Hrubes, Amir Yehudayoff

Just a Pebble Game
Siu Man Chan

Quantum XOR Games
Oded Regev, Thomas Vidick

Strong LTCs with inverse polylogarithmic rate and soundness
Michael Viderman Abstract: An error-correcting code is called -strong locally testable code (LTC) if there exists a randomized algorithm (tester) that makes at most queries to the input word. This algorithm accepts all codewords with probability 1 and rejects all non-codewords with probability at least , where denotes the relative Hamming distance between the word and the code . The parameter is called the query complexity and the parameter is called soundness. A well-known open question in the area of LTCs asks whether exist strong LTCs with constant query complexity, constant soundness and inverse polylogarithmic rate. In this paper, we construct strong LTCs with query complexity 3, inverse poly-logarithmic soundness and inverse poly-logarithmic rate.

Two-message quantum interactive proofs and the quantum separability problem
Patrick Hayden, Kevin Milner, Mark Wilde

How Low Can Approximate Degree and Quantum Query Complexity be for Total Boolean Functions?
Andris Ambainis, Ronald de Wolf

Approaching the chasm at depth four
Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Shared Randomness and Quantum Communication in the Multi-Party Model
Dmitry Gavinsky, Tsuyoshi Ito, Guoming Wang

On the Power of Non-Adaptive Learning Graphs
Aleksandrs Belovs, Ansis Rosmanis

Collapse of the Hierarchy of Constant-Depth Exact Quantum Circuits
Yasuhiro Takahashi, Seiichiro Tani

We study the quantum complexity class of quantum operations implementable exactly by constant-depth polynomial-size quantum circuits with unbounded fan-out gates. Our main result is that the quantum OR operation is in , which is an affirmative answer to the question of Høyer and Spalek…Lastly, we show that, if the quantum Fourier transform modulo a prime is in , there exists a polynomial-time exact classical algorithm for a discrete logarithm problem using a oracle. This implies that, under a plausible assumption, there exists a classically hard problem that is solvable exactly by a circuit with gates for the quantum Fourier transform.

A Derandomized Switching Lemma and an Improved Derandomization of
Luca Trevisan, TongKe Xue

Random Arithmetic Formulas can be Reconstructed Efficiently
Ankit Gupta, Neeraj Kayal, Youming Qiao

Optimal Inapproximability for Scheduling Problems via Structural Hardness for Hypergraph Vertex Cover
Sushant Sachdeva, Rishi Saket

Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle
Albert Atserias, Moritz Müller, Sergi Oliva

Superlinear lower bounds for multipass graph processing
Venkatesan Guruswami, Krzysztof Onak

On the Parameterized and Approximation Hardness of Metric Dimension
Sepp Hartung, André Nichterlein

Covering CSP’s
Irit Dinur, Gillat Kol

The distinguishability of product distributions by read-once branching programs
John Steinberger

An Space Algorithm for Directed Planar Reachability with Polynomial Running Time
Tatsuya Imai, Kotaro Nakagawa, Aduri Pavan, N. V. Vinodchandran, Osamu Watanabe

Short lists with short programs in short time
Bruno Bauwens, Anton Makhlin, Nikolay Vereshchagin, Marius Zimand What a great title: the word “short” is used three times.

Abstract: Given a machine , a -short program for is a string such that and the length of is bounded by (the length of a shortest program for ). We show that for any universal machine, it is possible to compute in polynomial time on input a list of polynomial size guaranteed to contain an -short program for . We also show that there exist computable functions that map every to a list of size containing an -short program for and this is essentially optimal because we prove that such a list must have size . Finally we show that for some machines, computable lists containing a shortest program must have length .

Constructing hard functions from learning algorithms
Adam Klivans, Pravesh Kothari, Igor Oliveira I have thought about this type of work over the years and look forward to reading the full paper.

Abstract: Fortnow and Klivans proved the following relationship between efficient learning algorithms and circuit lower bounds: if a class of boolean circuits contained in of Boolean is exactly learnable with membership and equivalence queries in polynomial-time, then is not contained in (the class was subsequently improved to by Hitchcock and Harkins). In this paper, we improve on these results. Our proofs regarding exact and mistake-bounded learning are simple and self-contained, yield explicit hard functions, and show how to use mistake-bounded learners to “diagonalize”over families of polynomial-size circuits. Our consequences for PAC learning lead to new proofs of Karp-Lipton-style collapse results, and the lower bounds from SQ learning make use of recent work relating combinatorial discrepancy to the existence of hard-on-average functions.

Approximating Boolean functions with depth-2 circuits
Eric Blais, Li-Yang Tan This approximation result seems surprising to me.

Abstract: We study the complexity of approximating Boolean functions with DNFs and other depth-2 circuits, exploring two main directions: universal bounds on the approximability of all Boolean functions, and the approximability of the parity function. In the first direction, our main positive results are the first non-trivial universal upper bounds on approximability by DNFs:

Every Boolean function can be approximated by a DNF of size .

Every Boolean function can be approximated by a DNF of width , where …

Towards a Reverse Newman’s Theorem in Interactive Information Complexity
Joshua Brody, Harry Buhrman, Michal Koucky, Bruno Loff, Florian Speelman, Nikolay Vereshchagin

LS+ Lower Bounds from Pairwise Independence
Madhur Tulsiani, Pratik Worah

On Medium-Uniformity and Circuit Lower Bounds
Rahul Santhanam, Ryan Williams Abstract: We explore relationships between circuit complexity, the complexity of generating circuits, and algorithms for analyzing circuits. Informally, a circuit class is “medium uniform” if it can be generated by an algorithmic process that is somewhat complex (stronger than ) but not infeasible. We prove several new unconditional lower bounds against medium uniform circuit classes, including:

… For all there is a language that does not have -size circuits constructible in polynomial time…

Composition limits and separating examples for some Boolean function complexity measures
Justin Gilmer, Michael Saks, Srikanth Srinivasan

On the Lattice Smoothing Parameter Problem
Kai-Min Chung, Daniel Dadush, Feng-Hao Liu, Chris Peikert

Matrix Constructions

Ken adds a few remarks about de-randomizing matrix constructions. Say a matrix is a “reduct” of a matrix if whenever , . That is, is obtained from by zeroing out some entries. Now define a matrix with positive entries to be “normal” if all of its reducts have the property

Since has nonnegative entries, of course a zero permanent implies a zero determinant, but the question is the converse. If we have just one matrix that is normal, then we have an especially simple way of telling whether any -by- bipartite graph has a perfect matching: multiply the adjacency matrix of entry-wise by to get a reduct, and take its determinant. That a random matrix is normal is the basis for a famous randomized- algorithm for perfect matching. But we don’t know how to efficiently construct even one normal matrix for each —if we did then perfect matching would be in which is still open.

Ken really wishes to draw attention to the following meta-question:

Is there a relationship between the construction problem for rigid matrices and the problem for normal matrices? Does one “reduce” to the other? Have reduction relationships been mapped out between these and other construction problems involving expanders or designs or codes or similar combinatorial objects?

Open Problems

Take a look at the accepted papers. Which are your favorites? What is known about Ken’s question?