Columbia Theory Reading Group, Fall 2004

Abstracts for the talks are given below. See the main page for schedule and location information.

Tuesday September 14:
NP-Complete Problems and Physical Reality
Scott Aaronson

Can NP-complete problems be solved efficiently using the resources of the physical universe? I'll survey approaches including soap bubbles, folding proteins, DNA, analog computing, relativistic time dilation, quantum computing (including the quantum adiabatic algorithm), quantum advice, hidden-variable theories, "subquantum" computing, nonlinear quantum mechanics, TQFT's, time travel, quantum gravity, and various self-selection and anthropic principles. I'll argue that none of these approaches are likely to succeed. I'll then advocate the hardness of NP-complete problems as a physical axiom akin to the Second Law of Thermodynamics.

Thursday October 7:
On learning random decision trees and DNF formulas
Rocco Servedio The problem of average-case learning for decision trees is as follows: a decision tree T (over Boolean features x1,...,xn) is chosen at random from some natural distribution over decision trees. The learning algorithm is given access to uniform random examples which are labeled according to T. The job of the learning algorithm is to efficiently construct a hypothesis function f which closely agrees with the unknown randomly chosen tree T.

Decision trees are an expressive representation for Boolean functions which have proven hard to learn in worst-case learning models. An even more challenging problem is that of learning an unknown DNF (Disjunctive Normal Form formula, i.e. an AND of ORs of Boolean variables) or CNF in the worst case.

In this work we give the first efficient algorithm for the average-case versions of these learning problems. Our algorithm for decision trees runs in polynomial time for random trees of logarithmic depth. Our algorithm for DNF and CNF formulas runs in polynomial time for random formulas with a subquadratic number of AND gates.

The talk will be self-contained and assumes no prior background in computational learning theory.

This is joint work with Jeffrey Jackson.

Thursday October 21:
Using Nondeterminism to Amplify Hardness
Alex Healy The goal of hardness amplification is to take a function f : {0,1}^n --> {0,1} that is mildly average-case hard (i.e., every "small" circuit fails to compute f on at least a 1/poly(n) fraction of inputs), and produce a new function f' that is very hard on average (i.e., every "small" circuit fails to compute f' on nearly half of its inputs).

In this work we study hardness amplification within NP -- this problem was first studied by O'Donnell (STOC 2002). He showed how to take a mildly average-case hard function f in NP, and produce a function f', also in NP, such that every "small" circuit fails to compute f' on roughly a (1/2 - 1/n) fraction of inputs. O'Donnell also showed that constructions of a certain general form cannot amplify beyond hardness (1/2 - 1/n).

In this work we prove hardness amplification up to (1/2 - 1/2^{\sqrt{n}}) within NP. That is, starting from a mild average-case hard f in NP, we produce f' in NP such that every "small" circuit fails to compute f' on a (1/2 - 1/2^{\sqrt{n}}) fraction of inputs.

To bypass the barrier shown in O'Donnell's work, we employ two new techniques. First, we show how to derandomize O'Donnell's construction using a certain "pseudorandom generator". Second, we show how to use nondeterminism in the hardness amplification -- this is in contrast to previous hardness amplifications which are deterministic.

Joint work with Salil Vadhan and Emanuele Viola.

Thursday October 28:
"On the (Im)possibility of Obfuscating Programs" by Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan and Yang. presented by Andrew Wan An obfuscator O is a 'compiler' that takes as input a program(or circuit) P and produces a new program O(P) that has the same functionality as P yet is "unintelligible" in some sense. Obfuscators would have a wide variety of practical and theoretic applications, including software protection, public-key encryption, and the removal of random oracles.

In this work the authors show that the existence of a general obfuscator is impossible. They also show that the results extend to approximate functionality obfuscators and to very simple complexity classes(TC_0). Additionally they rule out potential applications of obfuscators by constructing unobfuscatable signature schemes, encryption schemes, and pseudorandom function families.

Andrew will present the proof of the main result and survey the extensions. If there is time, he will also discuss "Positive Results and Techniques for Obfuscation"(Lynn, Prabhakaran, Sahai).

Monday November 8:
Local Fault-tolerant Quantum Computation
Krysta M. Svore Any realizable quantum computer will likely use error correction and fault-tolerant gate implementations to perform a computation. It has been shown that if the failure probability of any given component is below some critical 'threshold' value, then arbitrarily long reliable quantum computation is possible. Previously, the incorporation of error correction and fault-tolerant methods in the computation has only been analyzed in a setting where a multi-qubit gate can be applied to any qubits, no matter the spatial distance between them. In reality, a quantum technology may require that qubits be made 'local', that is be spatially adjacent, to undergo a multi-qubit gate.

We analyze and study the effects of locality on the fault-tolerance threshold for quantum computation. We analytically estimate how the threshold will depend on a scale parameter r which estimates the scale-up in the size of the circuit due to encoding. We carry out a detailed semi-numerical threshold analysis for concatenated coding using the 7-qubit CSS code in the local and `nonlocal' setting. First, we find that the threshold in the local model for the [[7,1,3]] code has a 1/r dependence, which is in correspondence with our analytical estimate. Second, the threshold, beyond the 1/r dependence, does not depend too strongly on the noise levels for transporting qubits. Beyond these results, we find that it is important to look at more than one level of concatenation in order to estimate the threshold and that it may be beneficial in certain places, like in the transportation of qubits, to do error correction only infrequently.

This is joint work with Barbara Terhal (IBM) and David DiVincenzo (IBM). The paper has been posted to the arXiv: quant=ph/0410047

Thursday December 9:
An optimal algorithm for packet scheduling with agreeable deadlines
Fei Li An important issue in IP-based QoS networks is the effective management of packets at the router level. Specifically, if the arriving packets cannot all be stored in a buffer, or if the packets have deadlines by which they must be delivered, the router needs to identify the packets that should be dropped. We consider a model which can be thought of as an on-line scheduling problem on a single machine: packets arrive at a network switch and are stored in a buffer of size B. Each packet has a positive weight and a deadline, with the weight representing the value of transmitting the packet by its deadline. At each integer time step, exactly one packet can be transmitted, and the objective is to maximize the total weight of the transmitted packets. If for any two packets i and j, r_i < r_j implies d_i <= d_j, then we say they have agreeable deadlines.

Our main result is an on-line algorithm with competitive ratio phi = 1.618 for instances with agreeable deadlines. Both the algorithm and the analysis are strikingly simple. Note that this competitive ratio is the best achievable by a deterministic algorithm.

This is joint work with Prof. Jay Sethuraman and Prof. Cliff Stein, both in IEOR Department of Columbia University.

Thursday December 16:
A New Look at the Second Moment Method
Dimitris Achlioptas It has been known since the late 80s that the chromatic number of a random graph is concentrated on 2 values. That is, for every real number d>0, there exists an integer k_d such that the chromatic number of a random graph with average degree d, i.e. G(n,p=d/n), is either k_d, or k_d+1 almost surely. Unfortunately, the proof of this fact gives no information about the value of k_d itself, which since remained a mystery.

We determine k_d for all d>0, proving that it is the smallest integer k such that d < 2k log k.

The proof requires taking a new look at one of the most basic tools in probability and combinatorics, the second moment method. Specifically, we show that for a large class of random constraint satisfaction problems (including random graph coloring, LDPC codes, random k-SAT) the second moment method reduces to understanding "entropy-energy" tradeoffs, controlled by the problem's constraint density. Critical values of this density correspond to points where the organization of the space of solutions of the problem undergoes dramatic change. We will show that identifying such points: (i) yields the location of "thresholds" such as the one above for graph coloring, and (ii) provides rigorous insight on why algorithms often have a hard time solving random CSPs close to such thresholds.

Based on joint works with Assaf Naor and Yuval Peres.

Back to Fall 2004 Theory Seminar main page