TCS @ Princeton

Title: Algorithms for Strategic Agents

Speaker: Matt Weinberg, Massachusetts Institute of Technology

[Complete Video]

Abstract:

In traditional algorithm design, no incentives come into play: the input is given, and your algorithm must produce a correct output. How much harder is it to solve the same problem when the input is not given directly, but instead reported by strategic agents (who may choose to lie) whose incentives may not align with your own?

This talk will present a recent series of results on black-box reductions from mechanism to algorithm design. That is, we show how to solve optimization problems while properly incentivizing strategic agents using only black-box access to an algorithm for (a modified version of) the same optimization problem when the input is directly given. This talk will not assume any knowledge of economics or game theory.

Based on joint works with Yang Cai and Costis Daskalakis.

Title: The Surprise Examination Paradox and the Second Incompleteness Theorem

Speaker: Ran Raz, Weizmann Institute & IAS

[Video]

Few theorems in the history of mathematics have inspired mathematicians and philosophers as much as Godel’s first and second incompleteness theorems. The first incompleteness theorem states that for any rich enough consistent mathematical theory, there exists a statement that cannot be proved or disproved within the theory. The second incompleteness theorem states that for any rich enough consistent mathematical theory, the consistency of the theory itself cannot be proved (or disproved) within the theory.

We give a new proof for Godel's second incompleteness theorem, based on Kolmogorov complexity and an argument that resembles the surprise examination paradox.

We then go the other way around and suggest that the second incompleteness theorem gives a possible resolution of the surprise examination paradox. Roughly speaking, we argue that the flaw in the derivation of the paradox is that it contains a hidden assumption that one can prove the consistency of the mathematical theory in which the derivation is done; which is impossible by the second incompleteness theorem.

I will start with a short informal introduction to the known proofs for Godel's incompleteness theorems and their relations to the liar paradox, Kolmogorov complexity and Berry's paradox.

No knowledge in logic will be assumed.

Joint work with Shira Kritchman

 

Title: Privately Solving Allocation Problems

Speaker: Aaron Roth, University of Pennsylvania

[Complete Video]

Abstract: 

In this talk, we'll consider the problem of privately solving the classical allocation problem: informally, how to allocate items so that most people get what they want. Here, the data that we want to keep private is the valuation function of each person, which specifies how much they like each bundle of goods. This problem hasn't been studied before, and for good reason: its plainly impossible to solve under the constraint of differential privacy. The difficulty is that publishing what each person i receives in a high-welfare allocation might necessarily have to reveal a lot about the preferences of person i, which is what we are trying to keep private! What we show is that under a mild relaxation of differential privacy (in which we require that no adversary who learns the allocation of all people j != i -- but crucially not the allocation of person i -- should be able to learn much about the valuation function of player i) the allocation problem is solvable to high accuracy, in some generality. Our solution makes crucial use of Walrasian equilibrium prices, which we use as a low information way to privately coordinate a high welfare allocation.

This is joint work with Justin Hsu, Zhiyi Huang, Tim Roughgarden, and Steven Wu

Title: The layers model with applications. 

Speaker: Daniel Reichman, Weizmann Institute of Science

[Complete Video]

Abstract: 

Given an undirected graph G = (V,E) and an integer k, let T_k(G) denote  the random vertex induced subgraph of G generated by ordering V according to a random permutation and including in T_k(G) those vertices with at most k − 1 of their neighbors preceding them in this order. The distribution of subgraphs sampled in this manner is called the layers model with parameter k.

We describe applications of the layers model in studying l-degenerate subgraphs, the design of algorithms for the maximum independent set problem, and bootstrap percolation. 

In studying this model, we were motivated by the percolation-and-optimization framework, which will be discussed as well.

Time permitting we will also consider the infinite grid Z₂, for which we prove that T₄(Z₂) contains a unique infinite connected component with probability 1. 

Based on joint works with Uri Feige and Jonathan Hermon. 

 

Title: Fingerprinting Codes and the Price of Approximate Differential Privacy

Speaker: Jon Ullman, Harvard University

[Complete Video]

Abstract: 

 

Title: Polar Codes: Reliable Communication with Complexity Polynomial in the Gap to Shannon Capacity

Speaker: Venkat Guruswami, Carnegie Mellon University

[Complete Video]

Abstract: 

We prove that, for all binary-input symmetric memoryless channels, Arikan's celebrated polar codes enable reliable communication at rates within ε > 0 of the Shannon capacity with block length (delay), construction complexity, and decoding complexity all bounded by a polynomial in the gap to capacity, i.e., by poly(1/ε). Polar coding gives the first known explicit construction with rigorous proofs of all these properties.

We establish the capacity-achieving property of polar codes via a direct analysis of the underlying martingale of conditional entropies, without relying on the martingale convergence theorem. This step gives rough polarization (noise levels ~ ε for the "good channels"), which can then be adequately amplified by tracking the decay of the channel Bhattacharyya parameters.

Our effective bounds imply that polar codes can have block length (and consequently also encoding/decoding complexity) that is bounded by poly(1/ε). We also show that the generator matrix of such polar codes can be constructed in polynomial time by algorithmically computing an adequate approximation of the polarization process.

Joint work with Patrick Xia.

Title: Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order

Speaker: Michael Forbes, Massachusetts Institute of Technology

[Complete Video]

Abstract: 

It is an important open question whether we can derandomize small space computation, that is, whether RL equals L. One version of this question is to construct pseudorandom generators for read-once oblivious branching programs. There are well-known results in this area (due to Nisan, and Impagliazzo-Nisan-Wigderson), but they fail to achieve optimal seed-length. Further, it has been observed that these pseudorandom generators depend strongly on the "order" of the "reads" of the branching program. When this order is allowed to vary, only much weaker results are known.

In this work, we consider an "algebraic" version of this question. That is, we seek to fool read-once algebraic branching programs, regardless of the variable order. By rephrasing and improving the techniques of Agrawal-Saha-Saxena, we are able to construct hitting sets for multilinear polynomials in this unknown-order model that have polylogarithmic "seed-length". This constitutes the first quasipolynomial-time, deterministic, black-box polynomial identity testing (PIT) algorithm for this model.

Joint work with Ramprasad Saptharishi (MSR India) and Amir Shpilka (Technion).

Title: On the Structure of Boolean Functions with Small Spectral Norm

Speaker: Ben lee Volk, Technion

[Complete Video]

Abstract: 

In this talk we show several results regarding Boolean functions with small spectral norm (the spectral norm of f is the sum of the absolute value of its Fourier coefficients.) Specifically, we prove the following results for Boolean functions on n variables with spectral norm A.

1. There is a subspace V of co-dimension at most A² such that f|_V is constant.
   
2. f can be computed by a parity decision tree of size 2^A2n^2A. (a parity decision tree is a decision tree whose nodes are labeled with arbitrary linear functions.)
   
3. If in addition f has at most s nonzero Fourier coefficients, then f can be computed by a parity decision tree of depth A² · log s.
   
4. For a "small" A, f can be epsilon-approximated by a parity decision tree of depth O(log(1/ε)). Furthermore, this tree can be efficiently learned using membership queries.
   

All the results above also hold (with a slight change in parameters) to functions over (ℤ_p)ⁿ.

Based on joint work with Amir Shpilka and Avishay Tal

Title: Approximation Algorithms and New Models for Clustering and Learning

Speaker: Pranjal Awasthi, Princeton University

[Complete Video]

Abstract: 

In this talk I will first describe my work on the study of clustering problems, specifically the k-means and the k-median clustering objectives. To study these problems we take a different approach than the traditional worst case analysis models. We show that by looking at certain well motivated stable instances, one can design much better approximation algorithms for these problems. Our algorithms achieve arbitrarily good approximation factors on stable instances, something which is provably hard on worst case instances.

In the second part of the talk I will describe some recent work on the study of new theoretical models both for learning and clustering. I will motivate the need for these new models and will present open problems and directions for future work.

 

Title: Computational aspects of the Combinatorial Nullstellensatz method via a polynomial approach to matrix and hypermatrix algebra

Speaker: Edinah K. Gnang, Institute for Advanced Study

[Complete Video]

Abstract: 

In this talk we discuss a polynomial encoding which provides a unified framework for discussing the algebra and the spectral analysis of matrices and hypermatrices. In addition to describing some algorithms for performing orthogonalization and spectral analysis of hypermatrices, we discuss some computational aspects, more specifically the important role of symmetries in Alon's Combinatorial Nullstellensatz method for solving combinatorial problems.

 

Title: Routing on Disjoint Paths and Related Problems

Speaker: Alina Ene, Princeton University

[Complete Video]

Abstract: 

In this talk, we consider some fundamental maximum throughput routing problems in undirected and directed graphs. In this setting, we are given a capacitated undirected or directed graph. We are also given source-destination pairs of nodes (s₁, t₁), (s₂, t₂), …, (s_k, t_k). The goal is to select a largest subset of the pairs that are simultaneously routable subject to the capacities; a set of pairs is routable if there is a multicommodity flow for the pairs satisfying certain constraints that vary from problem to problem (e.g., integrality, unsplittability, edge or node capacities). Two well-studied optimization problems in this context are the Maximum Edge Disjoint Paths (MEDP) and its node-capacitated counterpart, the Maximum Node Disjoint Paths (MNDP) problem. In MEDP and MNDP, a set of pairs is routable if the pairs can be connected using edge-disjoint and node-disjoint paths, respectively.

MEDP and MNDP are both NP-hard and their approximability has attracted substantial attention over the years. Over the last decade, several breakthrough results on both upper bounds and lower bounds have led to a much better understanding of these problems. At a high level, one can summarize this progress as follows. MEDP and MNDP admit poly-logarithmic approximations in undirected graphs if one allows constant congestion, i.e., the routing violates the capacities by a constant factor. Moreover, these problems are hard to approximate within a poly-logarithmic factor in undirected graphs even if one allows constant congestion. In sharp contrast, both problems are hard to approximate to within a polynomial factor in directed graphs even if a constant congestion is allowed and the graph is acyclic. If we are not allowed any congestion, the best approximation known are polynomial and it is a long-standing open problem to improve these guarantees in undirected graphs.

In this talk, we give a brief overview of some of the challenges in routing on disjoint paths in both undirected and directed graphs, with a focus on open problems and directions for future research. In undirected graphs, we consider the setting in which we are not allowed any congestion, and we highlight some ongoing efforts to get improved approximations for restricted graph classes. In directed graphs, we consider the setting in which the demand pairs are symmetric and we are allowed congestion. The strong lower bounds that are known for routing in directed graphs rely on the asymmetry of the demands and we give some evidence that the symmetric setting is much more tractable than the asymmetric setting.

This talk is based on joint work with Julia Chuzhoy (TTI-C) and Chandra Chekuri (UIUC).

 

Title: Finite field restriction estimates

Speaker: Mark Lewko, Institute for Advanced Study

[Complete Video]

Abstract: 

The Kakeya and restriction conjectures are two central open problems in Euclidean Fourier analysis (with the second logically implying the first, and progress on the first typically implying progress on the second). Both of these have formulations over finite fields. In 2008 Dvir completely settled the finite field Kakeya conjecture, however neither this result nor the proof method have yet yielded any progress on the finite field restriction conjecture. In this talk I will describe some recent progress on the finite field restriction conjecture, improving the exponents of Mockenhaupt and Tao. The key new ingredient is the use of incidence / sum-product estimates.

[A longer talk on this topic will be given in the IAS CSDM seminar on September 24, 2013]

 

Title: Deeper Combinatorial Lower Bounds

Speaker: Siu Man Chan, Princeton University

[Complete Video]

Abstract: 

We will discuss some classical and recent results on space and parallel complexity, in particular the study of combinatorial lower bounds in restricted settings, and highlight some of their connections to boolean complexity, proof complexity, and algebraic complexity.

Title: Efficient Reasoning in PAC Semantics

Speaker: Brendan Juba, Harvard University

[Complete Video]

Abstract: 

Machine learning is often employed as one step in a larger application, serving to perform information extraction or data mining for example. The rules obtained by such learning are then used as inputs to a further analysis. As a consequence of the inputs to this analysis having been learned, however, its conclusions can only be theoretically guaranteed to satisfy the same standard as the inputs---that of "PAC Semantics" (Valiant, 2000). In this talk, we explore the benefits of taking the problems of learning and logical reasoning together, capturing a relatively general family of such applications. Briefly, the benefit is that we can simultaneously:

1. Handle incomplete information
   
2. Utilize rules that are a reasonable but imperfect fit for the data, and
   
3. Reach conclusions more efficiently than is achieved by known algorithms for reasoning from rules alone.
   

Precisely, we consider a problem of testing the validity of a "query" formula (hypothesis) against incomplete data. We present algorithms for soundly verifying such queries that succeed whenever there exist learnable rules that suffice to complete a simple proof of the query, matching what can be achieved by such a two-stage learning and reasoning process.

Title: Uniqueness of Tensor Decompositions with Applications to Polynomial Identifiability

Speaker: Aravindan Vijayaraghavan, Carnegie Mellon University

[Complete Video]

Abstract: 

We give a robust version of the celebrated result of Kruskal on the uniqueness of tensor decompositions: we prove that given a tensor whose decomposition satisfies a robust form of Kruskal's rank condition, it is possible to approximately recover the decomposition if the tensor is known up to a sufficiently small (inverse polynomial) error. Kruskal's theorem has found many applications in proving the identifiability of parameters for various latent variable models and mixture models such as Hidden Markov models, topic models etc. Our robust version immediately implies identifiability using only polynomially many samples in many of these settings. This polynomial identifiability is an essential first step towards efficient learning algorithms for these models.

Recently, algorithms based on tensor decompositions have been used to estimate the parameters of various hidden variable models efficiently in special cases as long as they satisfy certain "non-degeneracy" properties. Our methods give a way to go beyond this non-degeneracy barrier, and establish polynomial identifiability of the parameters under much milder conditions. Given the importance of Kruskal's theorem in the tensor literature, we expect that this robust version will have several applications beyond the settings we explore in this work.

Joint work with Aditya Bhaskara and Moses Charikar

Paper available here: http://arxiv.org/abs/1304.8087

Title: Polynomials and Multiplicities I

Speaker: Shubhangi Saraf, Rutgers University

[Part 1] [Part 2]

Abstract: 

This will be a tutorial about applications of polynomials and multiplicities to codes and extractors. I will talk about the list-decoding of Reed-Solomon codes, analyzing Kakeya sets, and about multiplicity codes.

 

Title: Polynomials and Multiplicities II

Speaker: Swastik Kopparty, Rutgers University

[Complete Video]

Abstract: 

This will be a continuation of the tutorial. I will give the Stepanov-Schmidt elementary proof of the Weil bound and a recent explicit construction (joint with Venkatesan Guruswami) of subspace designs.

Title: New Constructions of RIP Matrices with Fast Multiplication and Fewer Rows

Speaker: Jelani Nelson, IAS & Princeton

[Complete Video]

Abstract: 

Many off-the-shelf algorithms for compressed sensing, like linear programming, rely on the compressed sensing matrix satisfying a sufficient condition called the "Restricted Isometry Property" (RIP). These algorithms also run faster if the compressed sensing matrix supports fast matrix-vector multiplication---for example, if it consists of random rows of a DFT. However, showing that the Fourier ensemble has the RIP with an optimal number of measurements appears to be a very difficult problem. In this talk, I will present some progress: we show that a matrix whose rows are sparse linear combinations of Fourier measurements has the RIP with fewer rows than previous constructions. Our results give RIP matrices supporting fast multiplication with fewer rows than previously known, and also imply improved fast Johnson-Lindenstrauss transforms.

This is joint work with Eric Price (MIT) and Mary Wootters (UMich).

Title: Submodular Maximization

Speaker: Roy Schwartz, Microsoft Research

[Complete Video]

Abstract: 

The study of combinatorial problems with a submodular objective has attracted much attention in recent years, and is partly motivated by the fact that such problems arise in diverse settings such as combinatorial optimization, algorithmic game theory, economics, machine learning and social networks.

We present improved approximation guarantees for submodular maximization problems in the constrained and the unconstrained cases. In the constrained case we present a single unified algorithm that computes fractional solutions for the multilinear relaxation for both monotone and non-monotone objectives. This algorithm yields information-theoretic tight approximations for the Submodular-Welfare and Submodular-Max-SAT problems. Additionally, it also provides an improved (1/e)-approximation for maximizing a non-monotone submodular function over a matroid. For the unconstrained case we present a simple linear-time algorithm that achieves an information-theoretic tight approximation of 1/2.

Based on joint works with Niv Buchbinder, Moran Feldman and Joseph (Seffi) Naor.

Program:

Title: Analysis and Synthesis Methods in Compressed Sensing

Speaker: Deanna Needell, Claremont McKenna College

[Complete Video]

Abstract: In this talk we will discuss results for robust signal reconstruction from random observations via synthesis and analysis methods.  Synthesis methods attempt to identify the low-dimensional representation of the signal directly, whereas analysis type methods reconstruct in signal space. We also include provable near-optimal reconstruction guarantees for total-variation minimization using properties of the bivariate Haar transform.

Title: Finding Cliques in Large Random Graphs, Sparse PCA and Iterative Thresholding

Speaker: Andrea Montanari, Stanford

[Complete Video]

Abstract: Consider a n times n symmetric matrix A, whose entries are i.i.d. with a common law P_0, except for a small k times k submatrix whose entries are also i.i.d. but with a different law P_1. We consider the case in which P_1 and P_0 have different mean, and investigate the problem of identifying the 'anomalous' k by k submatrix. A special case of this question is the well studied problem of identifying a clique in an Erdos-Renyi random graph. A simple counting argument shows that such a submatrix can be uniquely identified via exhaustive enumeration provided k is larger than C*log(n), for a suitable constant C. Unfortunately, no practical algorithm is successful for k smaller than square root of n. Worse than this, the best available guarantees are for vanilla PCA which does not make use of the sparsity of the submatrix. I will describe an iterative thresholding algorithm that provably improves over simple PCA, and in particular finds cliques of size square root of n/e.

Title: Faster Algorithms for the Sparse Fourier Transform

Speaker: Piotr Indyk, MIT

[Slides (PDF)]

Abstract: The Fast Fourier Transform (FFT) is one of the most fundamental numerical algorithms. It computes the Discrete Fourier Transform (DFT) of an n-dimensional signal in O(n log n) time. The algorithm plays an important role in many areas. It is not known whether its running time can be improved. However, in many applications, most of the Fourier coefficients of a signal are "small" or equal to zero, i.e., the output of the transform is (approximately) sparse. In this case, it is known that one can compute the set of non-zero coefficients faster than in O(n log n) time.

Title: A Polynomial Time Algorithm for Lossy Population Recovery

Speaker: Ankur Moitra, IAS/CCI

[Complete Video]

Abstract: 

We give a polynomial time algorithm for the lossy population recovery problem. In this problem, the goal is to approximately learn an unknown distribution on binary strings of length n from lossy samples: for some parameter μ each coordinate of the sample is preserved with probability μ and otherwise is replaced by a '?'.

The running time and number of samples needed for our algorithm is polynomial in n and 1/ε for each fixed μ > 0. This improves on algorithm of Wigderson and Yehudayoff that runs in quasi-polynomial time for any μ > 0 and the polynomial time algorithm of Dvir et al which was shown to work for μ > 0.30 by Batman et al. In fact, our algorithm also works in the more general framework of Batman et al. in which there is no a priori bound on the size of the support of the distribution.

The algorithm we analyze is implicit in previous work; our main contribution is to analyze the algorithm by showing (via linear programming duality and connections to complex analysis) that a certain matrix associated with the problem has a robust local inverse even though its condition number is exponentially small. A corollary of our result is the first polynomial time algorithm for learning DNFs in the restriction access model of Dvir et al and hence this model joins the random walk model of Bshouty et al as the only examples of passive learning in which DNFs can be learned in polynomial time.

Joint work with Mike Saks

Title: Quantum Hamiltonian Complexity: Through the Computational Lens

Speaker: Umesh Vazirani, UC Berkeley

[Complete Video] (note: audio cuts out for roughly 7 minutes at around 00:39:30)

Abstract: 

Much as probabilistic thinking did starting in the early 80s, quantum computing is expanding the core questions of complexity theory in fundamental new directions. For example, here is a list of three basic questions about quantum mechanics that are at their heart questions about computational complexity:

1. Do `typical' quantum states that occur in Nature have succinct (polynomial) description?
   
2. Can quantum systems at room temperature exhibit exponential complexity?
   
3. Is the scientific method sufficiently powerful to comprehend general quantum systems?
   

Each of these issues is best studied through the computational lens as a question about computation. The resulting questions lie at the core of computational complexity theory. The first asks about the structure of solutions to the quantum analog of SAT. The second asks whether there is a quantum analog of the PCP theorem. And the third can be formulated as a question about interactive proof systems with quantum polynomial time provers. I will briefly outline these connections and the state of the art on these questions.

Title: Certifying Equality with Limited Interaction

Speaker: Amit Chakrabarti, Dartmouth College

[Complete Video]

Abstract: 

The EQUALITY problem -- where Alice and Bob must decide if their respective inputs are equal -- is usually one's first encounter with communication complexity. Its deterministic and randomized complexity were settled decades ago, but we find several new things to say by considering two subtle aspects. First, we study the expected communication cost (at a worst-case input) for a protocol that uses limited interaction. Second, we study the information cost of such protocols. We obtain asymptotically optimal rounds-versus-communication and rounds-versus-information tradeoffs for EQUALITY.

As an application of our information cost bounds, we obtain new, and asymptotically optimal, bounded-round randomized lower bounds for OR-EQUALITY and k-DISJOINTNESS (where input sets have size ≤ k).

Joint work with Joshua Brody (Aarhus) and Ranganath Kondapally (Dartmouth).

Title: Algorithmic Applications of the Noncommutative Grothendieck Inequality

Speaker: Assaf Naor, Courant Institute, New York University

[Part 1] [Part 2]

Abstract: 

In 1953 Grothendieck proved an inequality of immense importance to several areas of mathematics, as well as having interesting applications to combinatorial optimization. In the same paper Grothendieck also conjectured the validity of a "noncommutative" version of his inequality, a conjecture that was solved affirmatively by Pisier in 1978, yielding an important tool for the study of C* algebras. This talk is devoted to a description of algorithmic implications of the noncommutative Grothendieck inequality. The talk will be self-contained and does not assume any background other than basic linear algebra and probability. We will start with a quick description of the classical Grothendieck inequality, explain how it leads to its noncommutative counterpart, and present a proof of the inequality that is an interesting rounding algorithm for a certain semidefinite program. The efficiency of this algorithm yields several algorithmic applications that we will describe, including the first constant factor approximation algorithms for the orthogonal Procrustes problem and robust versions of principle component analysis (PCA).

Joint work with Oded Regev and Thomas Vidick.

 

Title: Grothendieck Inequalities in Quantum Games and a Proof of the Operator Space Grothendieck Inequality

Speaker: Oded Regev, Courant Institute, New York University

[Complete Video]

Abstract: 

One of the most striking consequences of quantum mechanics (dating back to Einstein et al.) is that two remote parties who share entanglement can exhibit correlations that are impossible without entanglement. I will describe the history of this problem and its connection (mainly due to Tsirelson) to Grothendieck's inequality. I will then describe our recent work on quantum XOR games and discuss their connection to the non-commutative Grothendieck inequality and to the very recent operator-space Grothendieck inequality.

We will then discuss our recent new proof of the operator-space Grothendieck inequality, which is based on intuitions coming from quantum information and computer science.

Based on two papers with Thomas Vidick.

Title: The Geometry of Approximate Differential Privacy

Speaker: Kunal Talwar, Microsoft Research, Silicon Valley

Video: [Part 1] [Part 2]

Abstract: 

In this talk, I will discuss trade-offs between accuracy and privacy in the context of linear queries over histograms. This is a rich class of queries that includes contingency tables and range queries, and has been a focus of a long line of work. For a set of d linear queries over a database x ∈ ℝ^N, we seek to find the differentially private mechanism that has the minimum mean squared error. I will first describe a O(log² d) approximation algorithm for this problem, for the case of (ε,δ)-differential privacy. The mechanism is simple, efficient and adds correlated Gaussian noise to the answers. We prove its approximation guarantee relative to the hereditary discrepancy lower bound of Muthukrishnan and Nikolov, using tools from convex geometry.

We will next consider this question in the case when the number of queries exceeds the number of individuals in the database, i.e. when d > n = |x|₁. It is known that better mechanisms exist in this setting. I will then describe an (ε,δ)-differentially private mechanism which is optimal up to a polylog(d,N) factor for any given query set A and any given upper bound n on |x|₁. This approximation is achieved by coupling the Gaussian noise addition approach with a linear regression step. We give an analogous result for the ε-differential privacy setting. We also improve on the mean squared error upper bound for answering counting queries on a database of size n by Blum, Ligett, and Roth, and match the lower bound implied by the work of Dinur and Nissim up to logarithmic factors.

The connection between hereditary discrepancy and the privacy mechanism also enables us to derive the first polylogarithmic approximation to the hereditary discrepancy of a matrix A.

This talk is based on joint work with Alex Nikolov and Li Zhang.

Title: Simple and Prior-Independent Auctions 

Speaker: Tim Roughgarden, Stanford University

[Complete Video]

Abstract: 

Auctions tailored to a specific prior distribution over inputs are often complex and depend on the details of the distribution. On the other hand, strong impossibility results hold under the worst-case input assumptions. We survey the compelling positive results that have been obtained in models that interpolate between the worst- and average-case approaches. Examples include simple, approximately optimal mechanisms, which are only parameterized by minimal properties of the distribution; and prior independent auctions, whose guarantees hold under the assumption that the agents' preferences are stochastic, but without knowledge of the underlying distributions of preferences. 

Joint work with Peerapong Dhangwatnotai, Jason Hartline, Inbal Talgam-Cohen and Qiqi Yan

Title: Subexponential lower bounds for randomized pivoting rules for the simplex algorithm

Speaker: Uri Zwick, Tel Aviv University

[Complete Video]

Abstract: 

The simplex algorithm is among the most widely used algorithms for solving linear programs in practice. Most deterministic pivoting rules are known, however, to require an exponential number of steps to solve some linear programs. No non-polynomial lower bounds were known, prior to this work, for randomized pivoting rules. We provide the first subexponential (i.e., of the form 2^Ω(nα), for some α>0) lower bounds for the two most natural, and most studied, randomized pivoting rules suggested to date.

The first randomized pivoting rule we consider is Random-Edge, which among all improving pivoting steps (or edges) from the current basic feasible solution (or vertex) chooses one uniformly at random. The second randomized pivoting rule we consider is Random-Facet, a more complicated randomized pivoting rule suggested by Kalai (1992) and Matoušek, Sharir and Welzl (1996).

Our lower bound for the Random-Facet pivoting rule essentially matches the subexponential upper bounds of Kalai and Matoušek et al. Lower bounds for Random-Edge and Random-Facet were known before only in abstract settings, and not for concrete linear programs.

Our lower bounds are obtained by utilizing connections between pivoting steps performed by simplex-based algorithms and improving switches performed by policy iteration algorithms for 1-player and 2-player games. We start by building 2-player parity games (PGs) on which suitable randomized policy iteration algorithms perform a subexponential number of iterations. We then transform these 2-player games into 1-player Markov Decision Processes (MDPs) which correspond almost immediately to concrete linear programs.

Joint work with Thomas Dueholm Hansen and Oliver Friedmann.

Title: Edge Disjoint Paths in Networks

Speaker: Sanjeev Khanna, University of Pennsylvania

[Complete Video] (audio starts at 00:01:45)

Abstract: 

A fundamental problem in combinatorial optimization is the edge-disjoint paths problem (EDP). We are given a collection of source-destination pairs in a network, and the goal is to maximize the number of pairs that can be connected by edge-disjoint paths. Even special cases of EDP correspond to non-trivial optimization problems, and the problem becomes NP-hard in highly restricted settings. A sequence of ideas developed over the past decade has led to great progress on understanding the approximability of EDP. We will survey some of this progress and highlight some outstanding remaining questions.

 

Title: Hardness of Edge-Disjoint Paths and Congestion Minimization

Speaker: Matthew Andrews, Bell Labs

[Complete Video]

Abstract: 

We consider the hardness of approximation of the edge-disjoint-paths and congestion minimization problems. It is known that for c < O(log log n / log log log n), it is hard to obtain an O( (log n)^((1-ε)/(c+1) ) approximation to edge-disjoint-paths, even if congestion c is allowed.The main technique used to prove this result is embedding an instance in a high-girth graph. This has the benefit of restricting the set of paths that the solution can use to a small set of “canonical paths”.

This talk will have 3 parts.

1. We will begin by showing how the high-girth technique can be used to create edge-disjoint-path instances with large integrality gaps.
   
2. We will provide an overview of how these integrality gaps can be converted into hardness-of-approximation results.
   
3. We will discuss the barriers to extending the hardness results further.
   

We will focus on congestion minimization since for that problem there is still an exponential gap between the best-known positive and negative results. The biggest issue with the high-girth technique is that hardness is directly tied to the length of the canonical path and in a true high-girth instance the length of the canonical paths cannot be larger than log n. We will discuss alternative techniques that relax the high-girth requirement and may allow us to increase the length of the canonical paths, thereby improving the eventual hardness result.

 

Title: Poly-Logarithmic Approximation for Edge-Disjoint-Paths with Congestion 2

Speaker: Shi Li, Princeton University

[Complete Video]

Abstract: 

Edge-Disjoint Paths (EDP) problem is one of the central and most extensively studied network routing problems. In the problem, we are given k source-sink pairs in a network and want to connect as many pairs as possible using edge-disjoint paths. In spite of its rich history, there is still a huge gap between the √(log n)-hardness of approximation and the √(n)-approximation ratio for the problem. In this talk, I will give an overview of my joint work with Chuzhoy, which gives a poly-logarithmic approximation for EDP by slightly relaxing the edge-disjointness constraint : we allow each edge in the network to be used twice (i.e, we allow congestion 2). This culminates a long line of research on the EDP with congestion problem. In the talk, I will highlight some of the techniques used in this line.

 

Title: Physarum Computations

Speaker: Kurt Mehlhorn, Max Planck Institute for Informatics

[Complete Video]

Abstract: 

Physarum is a slime mold. It was observed over the past 10 years that the mold is able to solve shortest path problems and to construct good Steiner networks (Nakagaki-Yamada-Toth,Tero-Takagi-etal). In a nutshell, the shortest path experiment is as follows: A maze is built and the mold is made to cover the entire maze. Food is then provided at two positions and and the evolution of the slime is observed. Over time, the slime retracts to the shortest path connecting the two food sources.

A video showing the wet-lab experiment can be found at http://www.youtube.com/watch?v=czk4xgdhdY4

A mathematical model of the slime's dynamic behavior was proposed in 2007 by Tero-Kobayashi-Nakagaki. Extensive computer simulations of the mathematical model confirm the experimental findings. For the edges on the shortest path, the diameter converges to a fixed value, and for the edges off the shortest path, the diameter converges to zero.

We review the wet-lab and computer experiments and provide a proof for these experimental findings. We also suggest avenues for further work.

The talk is based on joint work with Vincenzo Bonifaci (Rome) and Girish Varma (TIFR).

Title: Introduction to Information Complexity

Speaker: Mark Braverman, Princeton University

[Complete Video]

Abstract: 

In this talk I will discuss information complexity, with an emphasis on definition, basic properties, and open problems.

 

Title: Direct Products in Communication Complexity

Speaker: Omri Weinstein, Princeton University

[Complete Video]

Abstract: 

We give exponentially small upper bounds on the success probability for computing the direct product of any function over any distribution using a communication protocol. Let $suc(mu,f,C)$ denote the maximum success probability of a $2$-party communication protocol for computing $f(x,y)$ with $C$ bits of communication, when the inputs $(x,y)$ are drawn from the distribution $\mu$. Let $\mu^n$ be the product distribution on n inputs and $f^n$ denote the function that computes $n$ copies of $f$ on these inputs.

We prove that if $T log^1.5 T < Cn$ and $suc(mu,f,C)<0.9$, then $suc(mu^n,f^n,T)<exp(Omega(n))$. When $\mu$ is a product distribution, we prove a nearly optimal result: as long as $T log^2 T < Cn$, we must have $suc(mu^n,f^n,T)<exp(Omega(n))$.

Joint work with Mark Braverman, Anup Rao and Amir Yehudayoff

 

Title: Disjointness and the Clique Polytope

Speaker: Ankur Moitra, Institute for Advanced Study

[Complete Video]

Abstract: 

Abstract: How many bits of communication are needed to get $\epsilon$-advantage over random guessing for disjointness? Kalyanasundaram and Schnitger proved that a protocol that gets constant advantage requires $\Omega(n)$ bits of communication. This result in conjunction with amplification implies that any protocol that gets $\epsilon$-advantage requires $\Omega(\epsilon^2 n)$ bits of communication. Here we improve this bound to $\Omega(\epsilon n)$, which is optimal for any $\epsilon > 0$.

In fact, the disjointness problem has applications in proving unconditional lower bounds against any linear programs for the clique problem. In the second half of this talk, I will review these connections and use the ideas in our proof to give an unconditional lower bound that any linear program that achieves an $O(n^{1-\epsilon})$ approximation for clique has size $2^{\Omega(n^\epsilon)}$. This matches Hastad's celebrated hardness result for clique.

Joint work with Mark Braverman

 

Title: Certifying Polynomials for AC0[parity] Circuits, With Applications

Speaker: Swastik Kopparty, Rutgers University

[Complete Video]

Abstract: 

I will talk about the method of "certifying polynomials" for proving AC0[parity] circuit lower bounds.

We use this method to show that Approximate Majority cannot be computed by AC0[parity] circuits of size n^{1+o(1)}. This implies a separation between the power of AC0[parity] circuits of near-linear size and uniform AC0[parity] (and even AC0 ) circuits of polynomial size. This also implies a separation between randomized AC0[parity] circuits of linear size and deterministic AC0[parity] circuits of near-linear size.

Our proof using certifying polynomials extends the deterministic restrictions technique of Chaudhuri and Radhakrishnan, who showed that Approximate Majority cannot be computed by AC0 circuits of size n^{1+o(1)}. At the technical level, we show that for every AC0[parity] circuit C of near linear size, there is a low degree variety V over F_2 such that the restriction of C to V is constant.

We also prove other results exploring various aspects of the power of certifying polynomials. In the process, we show an essentially optimal lower bound of (log(s))^(Omega(d)) * log(1/epsilon) on the degree of epsilon-approximating polynomials for AC0[parity] circuits of size s and depth d.

Joint work with Srikanth Srinivasan.

Title: A Manipulability Dichotomy Theorem for Generalized Scoring Rules

Speaker: Lirong Xia, Harvard University

[Complete Video]

Abstract: 

Social choice studies ordinal preference aggregation with applications ranging from high-stakes political elections to low-stakes movie rating websites. One recurring concern is that of the robustness of a social choice (voting) rule to manipulation, bribery and other kinds of strategic behavior. A number of results have identified ways in which computational complexity can provide a new barrier to strategic behavior, but most of previous work focused on case-by-case analyses for specific social choice rules and specific types of strategic behavior. In this talk, I present a dichotomy theorem for the manipulability of a broad class of generalized scoring rules and a broad class of strategic behavior called vote operations. When the votes are i.i.d., then with high probability the number of vote operations that are needed to achieve the strategic individual's goal is 0, Θ(√n), Θ(n), or infinity. This theorem significantly strengthens previous results and implies that most social choice situations are more vulnerable to many types of strategic behavior than previously believed.

Title: Beating the Direct Sum in Communication Complexity

Speakers: Marco Molinaro (CMU) and Grigory Yaroslavtsev (Penn State)

[Complete Video]

Abstract: 

A direct sum theorem for two parties and a function f states that the communication cost of solving k copies of f simultaneously with error probability 1/3 is at least k * R_{1/3}(f), where R_{1/3}(f) is the communication required to solve a single copy of f with error probability 1/3. We improve this for a natural family of functions f, showing that the 1-way communication required to solve k copies of f simultaneously with error probability 1/3 is (k R_{1/k}(f)). Since R_{1/k}(f) may be as large as R_{1/3}(f) * log k, we asymptotically beat the standard direct sum bound for such functions, showing that the trivial upper bound of solving each of the k copies of f with probability 1 - O(1/k) and taking a union bound is optimal.



Our results imply optimal communication/space lower bounds for several sketching problems in a setting when the algorithm should be correct on a sequence of k queries.

 

Title: Old and New Approaches for Proving Lower Bounds for Arithmetic Circuits

Speaker: Ran Raz, Weizmann Institute of Science

[Part 1] [Part 2]

Abstract: 

I will describe several old and more recent approaches for proving lower bounds for the size of general arithmetic circuits and formulas.

 

Title: Lower Bounds for Arithmetic Circuits via Depth-4 Circuits

Speaker: Ankit Gupta, Princeton University

[Complete Video]

Abstract: 

Recently, Agrawal-Vinay and Koiran, gave a new direction towards proving super-polynomial size lower bounds for general arithmetic circuits via proving strong enough lower bounds for depth-4 circuits. I will discuss some old lower bounds and then describe a recent progress in this direction using the method of shifted-partial derivatives.

 

Title: Minimax Option Pricing Meets Black-Scholes in the Limit

Speaker: Jacob Abernethy, University of Pennsylvania

[Complete Video]

Abstract: 

Option contracts are a type of financial derivative that allow investors to hedge risk and speculate on the volatility of an asset's future price. In 1973, Black and Scholes proposed a valuation model that gives a "fair price" for an option under the assumption that the price fluctuates according to geometric Brownian motion (GBM). Black and Scholes provided a continuous-time trading strategy for an investor, known as a "replication strategy" or "hedging strategy", which allows the investor to buy and sell the asset in order to "replicate" the option's payoff.

But why require a strong stochastic assumption on the price fluctuations? In this talk we'll consider a new method for evaluating the price of options and other derivatives that does not rely on the GBM assumption. We will appeal to the no-regret setting, in which the asset's price path may be chosen by a (constrained) adversary. We show that the Black Scholes model is recovered even in the worse case.

Joint work with Rafael Frongillo and Andre Wibisono. A link to the paper: http://goo.gl/tFKRH.

 

Title: A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities

Speaker: Vijay Vazirani, Georgia Institute of Technology

[Complete Video]

Abstract: 

The simplest way to describe our result is by analogy with the Lemke-Hawson complementary pivot algorithm for 2-player Nash equilibrium. This path-following algorithm gives a direct proof of membership of the problem in the class PPAD, and is a practical algorithm despite PPAD-completeness of the problem. It also yields deep structural insights, such as oddness of the number of equilibria.

Our algorithm accomplishes the above for the problem of finding an equilibrium for an Arrow-Debreu market under separable, piecewise-linear concave utilities. Our key steps are deriving an LCP that captures the set of equilibria of the market, and solving it using Lemke's algorithm; the latter involves showing that the polyhedron associated with the LCP has no secondary rays.

Our result answers an open problem of Eaves from 1975 and a recent open problem of Vazirani and Yannakakis.

Based on the following joint paper with Jugal Garg, Ruta Mehta and Milind Sohini: http://www.cc.gatech.edu/~vazirani/SPLC.pdf

 

October 19, 2012

Title: A Complementary Pivot Algorithm for Market Equilibrium under Separable, Piecewise-Linear Concave Utilities

Speaker: Vijay Vazirani, Georgia Institute of Technology

[Complete Video]

Abstract: 

The simplest way to describe our result is by analogy with the Lemke-Hawson complementary pivot algorithm for 2-player Nash equilibrium. This path-following algorithm gives a direct proof of membership of the problem in the class PPAD, and is a practical algorithm despite PPAD-completeness of the problem. It also yields deep structural insights, such as oddness of the number of equilibria.

Our algorithm accomplishes the above for the problem of finding an equilibrium for an Arrow-Debreu market under separable, piecewise-linear concave utilities. Our key steps are deriving an LCP that captures the set of equilibria of the market, and solving it using Lemke's algorithm; the latter involves showing that the polyhedron associated with the LCP has no secondary rays.

Our result answers an open problem of Eaves from 1975 and a recent open problem of Vazirani and Yannakakis.

Based on the following joint paper with Jugal Garg, Ruta Mehta and Milind Sohini: http://www.cc.gatech.edu/~vazirani/SPLC.pdf

 

October 12, 2012

Title: Reconstructing Strings from Random Traces

Speaker: Sampath Kannan, University of Pennsylvania

[Complete Video]

Abstract: 

In a deletion channel each transmitted symbol is deleted independently with some probability p. We consider settings where no error correction is allowed and where the receiver does not know where the gaps in the transmitted string are. We ask what deletion probabilities can be tolerated for reconstruction with polynomially many retransmissions. We consider two variants of the problem - one where we want worst-case reconstruction and one where we want reconstruction with high probability and survey the best known bounds for these two variants.

 

September 28, 2012

Title: Beck's Three Permutations Conjecture: A Counterexample and Some Consequences

Speaker: Alantha Newman, Rutgers University

[No Video]

Abstract: 

Given three permutations on the integers 1 through n, consider the set system consisting of each interval in each of the three permutations.  In 1982, Beck conjectured that the discrepancy of this set system is O(1).  In other words, the conjecture says that each integer from 1 through n can be colored either red or blue so that the number of red and blue integers in each interval of each permutations differs only by a constant.  (The discrepancy of a set system based on two permutations is at most two.)

We will present a counterexample to this conjecture: for any positive integer n = 3^k, we construct three permutations whose corresponding set system has discrepancy Omega(log(n)).

Our work was inspired by an intriguing paper from SODA 2011 by Eisenbrand, Palvolgyi and Rothvoss, who show a surprising connection between the discrepancy of three permutations and the bin packing problem: They show that Beck's conjecture implies a constant worst-case bound on the additive integrality gap for the Gilmore-Gomory LP relaxation for bin packing in the special case when all items have sizes strictly between 1/4 and 1/2, also known as the three partition problem.  Our counterexample shows that this approach to bounding the additive integrality gap for bin packing will not work.  We can, however, prove an interesting implication of our construction in the reverse direction: there are instances of bin packing and corresponding optimal basic feasible solutions for the Gilmore-Gomory LP relaxation such that any packing that contains only patterns from the support of these solutions requires at least OPT + Omega(log(m)) bins, where m is the number of items.

Joint work with Ofer Neiman and Aleksandar Nikolov.

The October CCI monthly meeting will be Friday October 5^th in room 105.  We are excited to have Amir Shpilka and more new center postdocs talking about their recent research.   

10:00-11:00         PI meeting (room 401)

11:00-12:00         On Sunflowers and Matrix Multiplication -- Amir Shpilka [Video]

12:00-12:45         lunch

12:45-1:30           On Sunflowers and Matrix Multiplication -- Amir Shpilka (continued) [Video]

1:30-2:00             break

2:00-2:30             Mechanisms Leveraging Arbitrary Set-Theoretic Belief Hierarchies -- Jing Chen [Video]

2:30-3:00             Constant-depth Circuits with Smooth Probabilistic Gates -- Andy Drucker [Video]

3:00-3:30             Covering CSPs -- Gillat Kol [Video]

--------------------------------------------------------------------------

Title: On Sunflowers and Matrix Multiplication

--------------------------------------------------------------------------

Title: Mechanisms Leveraging Arbitrary Set-Theoretic Belief Hierarchies

--------------------------------------------------------------------------

Title: Constant-depth Circuits with Smooth Probabilistic Gates

--------------------------------------------------------------------------

Description: Many current approaches in machine learning are heuristic: we cannot prove good bounds on either their performance or their running time. This small workshop will focus on the project of designing algorithms and approaches whose performance can be analyzed rigorously. The goal is to look beyond settings where provable bounds already exist.

Participation by invitation only; please send email to Ankur Moitra (moitra) if you wish to participate. We intend this to be a small meeting with active participation from all attendees - both speakers and non-speakers. Students who would like to attend the workshop should send a paragraph describing their researchinterests and background, and the relevance of this workshop to them. The deadline for registration is Thursday, July 26th.

Dates: The workshop will go from 10am on August 1 to 4pm on August 2 and will be held at the computer science dept, Princeton University.

Program/Schedule: (abstracts)

Wednesday, August 1st:

9:30-10:00 Breakfast and coffee (provided)

10:00-11:00 Michael Collins "Provable ML Methods for Natural Language Processing" [Video]

11:00-12:00 Sanjeev Arora. "Is Machine Learning Easy? Three Vignettes" [Video]

12:00-1:30 Lunch (provided)

1:30-2:30 Sham Kakade " Scalable Spectral Methods for Learning Latent Variable Models" [Video]

2:30-3:30 Percy Liang "Learning Latent-Variable Models of Natural Language" [Video]

3:30-4:00 Coffee break

4:00-5:00 David Sontag "Probabilistic Inference as Statistical Recovery" [Video]

5:00-6:00 Yann LeCun "Deep Learning: The Theoretician's Nightmare or Paradise?" [Video]

6:30-9 Dinner (provided) and informal discussion session

Thursday, August 2nd:

9:30-10:00 Breakfast and coffee (provided)

10:00-11:00 John Lafferty "Dictionary Learning and Sparsified Covariance Matrices for Linear Estimation" [Video]

11:00-12:00 Rob Schapire "Explaining Adaboost" [Video]

12:00-1:30 Lunch (provided)

1:30-2:30  Nina Balcan "Incorporating Unlabeled Data and Interaction in the Learning Process" [Video]

2:30-3:00 Coffee break

3:00-4:00 Sasha Rakhlin "Online Learning: A Minimax Analysis and an Algorithmic Framework" [Video]

 

The May CCI monthly meeting will be Friday May 4^th in room 105.  We are excited to have Bobby Kleinberg and Shahar Dobzinski talking about algorithmic mechanism design.  

 

10:15-10:45         PI only meeting (room 410)

11:00-12:00         TUTORIAL: Basics of Algorithmic Mechanism Design – Bobby

12:00-1:15           Lunch break

1:15-2:45            The Evolution of Proving Inapproximability Results in Algorithmic Mechanism Design – Shahar

2:45-3:00             break

3:00-4:30             Recent Developments in Bayesian Mechanism Design -- Bobby

--------------------------------------------------------------------------

Title:  TUTORIAL: Basics of Algorithmic Mechanism Design

Speaker: Bobby Kleinberg

[Complete Video]

This introductory talk presents the high-level goals and challenges underlying research in algorithmic mechanism design.  It provides the foundations for the talks later in the day, by reviewing basic definitions (e.g. mechanism, solution concept, truthfulness, single-parameter vs. multi-parameter domains) and fundamental tools (e.g. the mechanisms of Vickrey-Clarke-Groves and Myerson).

--------------------------------------------------------------------------

Title: The Evolution of Proving Inapproximability Results in Algorithmic Mechanism Design

Speaker:  Shahar Dobzinski

[Complete Video]

One of the major goals of Algorithmic Mechanism Design is to determine the power of computationally efficient truthful mechanisms. In this talk we will focus on proving limits on the power of such mechanisms. We start by describing the Characterize-and-Optimize approach and its basic ingredients: characterizations of truthful mechanisms and proving impossibility results for polynomial time maximal in range algorithms.  Unfortunately in some important settings, such as combinatorial auctions, many attempts to utilize this approach have failed. To overcome this, an alternative Direct Hardness approach was recently introduced. In the last part of the talk we will discuss how and why this approach enables us to obtain inapproximability results for these settings.

--------------------------------------------------------------------------

Title:  Recent Developments in Bayesian Mechanism Design

Speaker: Bobby Kleinberg

[Complete Video]

In the three decades following Roger Myerson's celebrated paper on optimal auctions for single-parameter domains, progress on multi-parameter domains has been frustratingly slow.  By relaxing optimality to approximate optimality, theoretical computer scientists have recently made a great deal of progress on these problems.  The talk will survey some of these results and highlight the underlying techniques, giving emphasis to the surprisingly rich interplay between optimal mechanism design and optimal stopping theory.

 

April 27, 2012

Title: Multicommodity Flows and Cuts in Polymatroidal Networks 

Chandra Chekuri, UIUC

[Complete Video]

Abstract: 

The well-known maxflow-mincut theorem for single-commodity flows in directed networks is of fundamental importance in combinatorial optimization. Flow-cut equivalence does not hold in the multicommodity case. A substantial amount of research in the algorithms community has focused on understanding the gap between multicommodity flows and associated cuts. Poly-logarithmic gap results have been established in various settings via tools from network decomposition and metric embeddings. 

In this talk we describe work that obtains flow-cut gap results in *polymatroidal* networks. In these networks there are submodular capacity constraints on the edges incident to a node. Such networks were introduced by Lawler & Martel and Hassin in the single-commodity setting and are closely related to the submodular flow model of Edmonds and Giles. The well-known maxflow-mincut theorem for a single- commodity holds in polymatroidal networks, however, the multicommodity case has not been previously explored. Our work is primarily motivated by applications to information flow in wireless networks although the technical results we obtain are of independent interest as they generalize known results in standard networks including 

node-capacitated undirected networks. The results highlight the utility 

of line embeddings suggested by Matousek and Rabinovich. We use them to 

round the dual of the flow-relaxation rewritten with a convex objective function obtained from the Lovasz-extension of a submodular function. 

Joint work with Sreeram Kannan, Adnan Raja and Pramod Viswanath. 

Paper available at http://arxiv.org/abs/1110.6832

 

April 20, 2012

Nearly Complete Graphs Decomposable into Large Induced Matchings and their Applications

 

April 13, 2012

Hypercontractivity, Sum-of-Squares Proofs, and their Applications

[Complete Video]

David Steurer, Microsoft Research

We study the computational complexity of approximating the 2-to-q norm of

linear operators for q > 2, as well as connections of this question to

issues arising in quantum information theory and in the context of Khot's

Unique Games Conjecture (UGC). We show the following:

- A constant level of the Sum-of-Squares / Lasserre semidefinite

programming hierarchy certifies the unsatisfiability of Unique Games

instances based on the noisy cube or the short code. The previous best

upper bound on the level of these instances was exp((log n)^{Omega(1)})

(for the short code). This result also separates the Sum-of-Squares

hierarchy from weaker hierarchies that were known to require omega(1)

levels for these instances. A key ingredient of the result is that the

Sum-of-Squares hierarchy can certify bounds on the 2-to-4 norm of the

projector into low-degree polynomials over the Boolean cube.

- We characterize small-set expansion of graphs in terms of 2-to-q norms

of projectors into the span of their top eigenvectors. As a corollary,

achieving certain "good approximations" to the 2-to-q norm is at least

as hard as refuting Small-Set Expansion Hypothesis — a close relative

of the UGC. On the one hand, we show that such good approximations can

be obtained in time exp(n^{2/q}), generalizing the known subexponential-time

algorithm for Small-Set Expansion. On the other hand, we show that good

approximations for the 2-to-4 norm require quasipolynomial time assuming

that 3-SAT requires exponential time. The latter result builds on a

connection to the quantum separability problem.

March 30, 2012

Title: Approximating Graphic TSP by Matchings

Ola Svensson

[Complete Video]

Abstract:

We will discuss a framework for approximating the metric TSP based on

a novel use of matchings. Traditionally, matchings have been used to

add edges in order to make a given graph Eulerian, whereas our

approach also allows for the removal of certain edges leading to a

decreased cost.

We then overview the exciting and rapid development for TSP on

graphic metrics following this approach: our 1.461-approximation

algorithm, the better analysis by Mucha'11 yielding an approximation

guarantee of 1.44, and the recent development by Sevo & Vygen'12 who

gave a 1.4-approximation algorithm.

Finally, we point out some interesting open problems where our

techniques currently fall short from generalizing to more general

metrics.

This is based on joint work with Tobias Moemke.

 

March 16, 2012

Jelani Nelson

Title: Sparser Johnson-Lindenstrauss Transforms [Complete Video]

Abstract:

The Johnson-Lindenstrauss (JL) lemma (1984) states that any n points in d-dimensional Euclidean space can be embedded into k = O((log n)/eps2) dimensions so that all pairwise distances are preserved up to 1+/-eps. Furthermore, this embedding can be achieved via a linear mapping. The JL lemma is a useful tool for speeding up solutions to several high-dimensional problems: closest pair, nearest neighbor, diameter, minimum spanning tree, etc. It also speeds up some clustering and string processing algorithms, reduces the amount of storage required to store a dataset, and can be used to reduce memory required for numerical linear algebra problems such as linear regression and low rank approximation.

The original proofs of the JL lemma let the linear mapping be specified by a random dense k x d matrix (e.g. i.i.d. Gaussian entries). Thus, performing an embedding requires dense matrix-vector multiplication. We give a construction of linear mappings for JL in which only a subconstant fraction of the embedding matrix is non-zero, regardless of how eps and n are related, thus always speeding up the embedding time. Previous constructions only achieved sparse embedding matrices for 1/eps >> log n.

This is joint work with Daniel Kane (Stanford).

 

March 2, 2012

Brendan Lucier , Microsoft Research Cambridge

The Limits of Black-Box Mechanism Design

[Complete Video]

A single-parameter mechanism design problem is an optimization problem with a game-theoretic twist: the input values are held by rational agents, who may misrepresent the input for their own gain. To combat this manipulation one might ask for an algorithm that is incentive compatible, meaning that it is in the best interest of each agent to report its value truthfully. In general, however, the impact of the truthfulness requirement on the approximation factors achievable by polynomial-time algorithms for single-parameter problems is unknown.

We consider the problem of converting an arbitrary approximation algorithm for a single-parameter optimization problem into a computationally efficient truthful mechanism. We ask for reductions that are "black-box", meaning that they require only oracle access to the given algorithm and in particular do not require explicit knowledge of the problem constraints.

We show that such a black-box transformation is possible for social welfare problems in the Bayesian setting, where the inputs are drawn from commonly-known distributions. In the non-Bayesian setting, however, we show that no such general black-box reduction exists, even for single-parameter problems. Specifically, a black-box reduction for the social welfare objective is not possible if the resulting mechanism is required to be truthful in expectation and to preserve the worst-case approximation ratio of the algorithm to within a subpolynomial factor. Further, for other objectives such as makespan, no black-box reduction is possible even if we only require Bayesian truthfulness and an average-case performance guarantee.

Joint work with Shuchi Chawla and Nicole Immorlica

 

February 24, 2012

Ravi Kannan, Microsoft Research

Title: k-MEANS REVISITED

[Complete Video]

Ravi Kannan, MSR

In many applications, fairly fast clustering algorithms seem to yield the desired solution. Theoretically, two types of assumptions lead to provably fast algorithms for clustering: (i) stochastic (mixture) models of data and (ii) uniqueness of optimal solution even under perturbations of data. We show that under an assumption weaker than either of these, Lloyd's (k-means) algorithm converges to the correct solution. We apply the result to the planted clique problem.

Joint work with Amit Kumar.

 

February 17, 2012

Andrew Drucker (MIT)

Title:   On the Hardness of Compressing an AND of SAT Instances

[Complete Video]

Andrew Drucker, MIT

Abstract:

Given an instance of a decision problem that is too hard to solve outright, we may aim for the more limited goal of compressing that instance into a smaller, equivalent one.

As one example, suppose we're given a collection of m^100 Boolean formulas {F_i} on disjoint variable-sets, each formula of length m; we'd like to know if at least one is satisfiable. Can we efficiently construct a new formula G of length, say, m^3, such that G is satisfiability-equivalent to the OR of the F_i's? This seems unlikely, but doesn't appear to contradict the hardness of SAT.

Bodlaender et al. (ICALP 2008) showed that the intractability of this "OR-compression" task would have important consequences in the study of "fixed-parameter-tractable" problems. They showed something similar for the corresponding "AND-compression" task, with a different set of consequences in this case. Motivated by this, Fortnow and Santhanam (STOC 2008) showed that efficient OR-compression is not possible unless NP is in coNP/poly, an unlikely consequence. But the case of AND-compression remained mysterious.

We show that efficient AND-compression would also imply that NP is in coNP/poly. To prove this result (and some extensions), we interpret any compression scheme as a communication channel, and exploit its bottleneck: we give a new method to "disguise" information being fed into a compressive mapping

 

February 10, 2012

Afonso Bandeira, Princeton Department of Mathematics 

Title: A Cheeger Inequality for $SO(3)$ Synchronization

[Complete Video]

Afonso Bandeira

joint work with Amit Singer (Princeton) and Daniel Spielman (Yale)

Abstract: The $SO(3)$ synchronization problem consists of estimating a set of unknown rotations $O_i$ from noisy measurements of a subset of the pairwise relative rotations $O_iO_j^{-1}$. We show an $SO(3)$ Cheeger inequality that relates a measure of how well it is possible to solve the $SO(3)$ synchronization with the spectra of an operator, the graph Connection Laplacian. We also show how this inequality provides a worst case performance guarantee for a spectral method, that we propose, to solve $SO(3)$ Synchronization.

 

 

The April CCI monthly meeting will be April 6th. Please note the unusual place (the Carl A. Fields center is two buildings south of the Princeton University Computer Science building along Olden St. Map) and time for the PC meeting.

To start off the day, Mark Braverman will tell us about Julia Sets and related computational complexity questions.  Zeev will then tell us about how to evade subspaces and varieties.

Schedule, titles and abstracts below:

——————————————-

Schedule:

11:00-12:00pm Mark Braverman– Computability and Complexity of Julia Sets (at Fields Center)

12:00pm-1:30pm Lunch (at Field Center)

12:45pm-1:30pm  PI meeting (in CS building 302)

1:30-3:00pm Zeev "How to evade subspaces and varieties" (in Large Auditorium)

-----------------------------------------

Mark Braverman

Computability and Complexity of Julia Sets

[Complete Video]

Abstract:   Studying dynamical systems is key to understanding a wide range of phenomena ranging from planetary movement to climate patterns to market dynamics. Various computational and numerical tools have been developed to address specific questions about dynamical systems, such as predicting the weather or planning the trajectory of a satellite.

However, the theory of computation behind these problems appears to be very difficult to develop. In fact, little is known about computability of even the most natural problems arising from dynamical systems.

In this talk I will survey the recent study of the computational properties of dynamical systems that arise from iterating quadratic polynomials on the complex plane. These give rise to the amazing variety of fractals known as Julia sets, and are closely connected to the Mandelbrot set. Julia sets are perhaps the most drawn objects in Mathematics due to their fascinating fractal structure. The theory behind them is even more fascinating, and the dynamical systems generating them are in many ways archetypal. I will present both positive and negative results on the computability and computational complexity of Julia sets.

If time permits, I will also talk a little bit about the interference between noise and non-computability in dynamical systems.

-------------------------------

Zeev Dvir

How to evade subspaces and varieties

[Complete Video]

Abstract:

I will describe an explicit construction of a large set in F^n, where F is a finite field, that has small intersection with any subspace (or more generally, algebraic variety) of fixed dimension. Such sets have applications to the construction of list-decodable codes and give the first explicit capacity achieving codes with constant list-size.

The proof uses some new methods from Algebraic Geometry and, in the talk, I will try to give some of the background needed.

The talk will be based on two joint works with Lovett and with  Kollar+Lovett.

 

The March CCI monthly meeting will be March 9th in CS 105—the small auditorium.  Please note the unusual time (the second Friday due to spring break), place, and the change in schedule due to speaker illness.

To start off the day, Avi will continue to tell us about Restriction Access.  Following lunch Rajsekar will tell us about testers for approximate permanent oracles, and then Nikhil will tell us about covariance estimation.

Schedule, titles and abstracts below:

——————————————-

Schedule:

10:30am-11:00am PC meeting (in CS 401)

11:00-12:00pm Avi Wigderson--Population Recovery: New Algorithms through Partial IDs [Complete Video]

 

12:00pm-1:20pm Lunch

1:20-2:00pm Rajsekar Manokaran--Testing an average-case oracle that approximates the permanent of gaussian random matrices. [Complete Video]

 

2:10-3:00pm Nikhil--Covariance Estimation for Distributions with 2+\epsilon Moments [Complete Video]

 

——————————————-

Avi Wigderson

Population Recovery: New Algorithms through Partial IDs

Abstract:

I a previous CCI lecture I explained how a new model for non-black-box learning (developed with Dvir, Rao and Yehudayoff, called Restriction Access") gives rise to an algorithmic problem of recovering a population from lossy samples.

In this (self contained) lecture I will define again the Population Recovery Problem and some extensions of it, and then discuss new algorithms for this problem. Key to these algorithms is a new data structure for an arbitrary set of vectors over any alphabet, which assigns to each vector a small subset which only partially separates it from the rest. Certain parameters of the "dependency graph" which arises from these partial IDs control the efficiency and error tolerance of the new algorithms. We further give an efficient algorithm to find such partial IDs with near-optimal parameters. The combination implies reconstructing an unknown population from lossy and/or noisy samples.

Achieving optimal parameters remains an interesting open problem.

Joint work with Amir Yehudayoff.

_______________________________

Rajsekar Manokaran

Title: Testing an average-case oracle that approximates the permanent of gaussian random matrices.

Abstract: In this talk, I will describe a tester for oracles that approximate the permanent (of most) matrices generated by picking each entry independently from a standard normal distribution.  The tester accepts oracles with at most a $c n!$ additive mean-squared-error (from the true value of the permanent) with high probability; while rejecting oracles incurring more than a $poly(n) c n!$ additive mean squared error with high probability (for any $c$ less than a fixed $1/poly(n)$).  Here, $n$ is the dimension of the matrices the oracle works with.

The complexity of approximating the permanent of these matrices has recently been related to the complexity of simulating a quantum computer.  I will describe this connection briefly, to motivate the need for the tester we have designed.  Time permitting, I will describe possible venues to address this larger question.

This is based on a work with Sanjeev Arora, Arnab Bhattacharya and Sushant Sachdeva.

_____________________

Nikhil Srivastava

Covariance Estimation for Distributions with 2+\epsilon Moments 

We study the following basic question: given a vector-valued random variable X in R^n, how many i.i.d. samples X_1,\ldots, X_q are required so that the empirical covariance matrix (1/q)\sum_{i\le q} X_iX_i^T approximates the actual covariance matrix E XX^T? A remarkably general result of M. Rudelson shows that when ||X||\le O(\sqrt{n}) almost surely, then q=O(nlogn/\epsilon^2) samples suffice to obtain an \epsilon-approximation in the spectral norm. This result and the more general Alhswede-Winter matrix Chernoff bound have had numerous applications in convex geometry, numerical linear algebra, and computer science. 

Rudelson's bound is known to be tight in this generality, but can be improved to O(n/\epsilon^2) in the case of Gaussian and log-concave X (for instance, X distributed uniformly on a convex body). We provide an elementary proof that O(n) samples suffice under a more general assumption -- bounded 2+\delta moments of all marginals -- which extends the class of distributions for which the O(logn) oversampling is not required.

Joint work with Roman Vershynin.

 

http://arxiv.org/abs/1106.2775

 

 

 

The February CCI monthly meeting will be February 3rd in room 402 at the CS dept. The main part of the day will be devoted to discussing and hearing about new advances in homomorphic encryption.  We are excited that Vinod Vaikuntanathan will be presenting. Following this, Avi will continue to tell us about Restriction Access.   Schedule, titles and abstracts below.:

Schedule:

10:30am-11:00am PC meeting

11:00-12:00pm Vinod Vaikuntanathan, Computing Blindfolded: New Developments in Fully Homomorphic Encryption

12:00pm-1:20pm Lunch

1:20-2:20pm Vinod Vaikuntanathan, continues   [Complete Video]

2:30-3:30 Avi Wigderson will tell us more about Restriction Access.

——————————————-

Abstracts:

Vinod Vaikuntanathan

Title: Computing Blindfolded: New Developments in Fully Homomorphic Encryption

Abstract:

A fully homomorphic encryption scheme enables computation of arbitrary functions on encrypted data.  Fully homomorphic encryption has long been regarded as cryptography’s prized “holy grail” – extremely useful yet rather elusive. The last three years have witnessed numerous constructions of fully homomorphic encryption involving novel mathematical techniques, and a number of exciting applications. We will survey these developments and provide a glimpse of the exciting research directions that lie ahead.

 

_______________________________

Avi Wigderson: Restriction Access

Avi will delight us with more insights from his work on Restriction Access.

 

Abstract from December meeting:

We introduce a notion of non-black-box access to computational devices (such as circuits, formulas, decision trees, and so forth) that we call restriction access. Restrictions are partial assignments to input variables. Each restriction simpli fies the device, and yields a new device for the restricted function on the unassigned variables. On one extreme, full restrictions (assigning all variables) correspond to evaluating the device on a complete input, yielding the result of the computation on that input, which is the same as standard black-box access. On the other extreme, empty restrictions (assigning no variables) yield a full description of the original device. We explore the grey-scale of possibilities in the middle. Different variants of restriction access, in which the values to restricted variables, as well as the subset of free (unassigned) variables, are generated deterministically or randomly, in friendly or adversarial fashions may naturally suit a variety of situations in computational learning, computational biology, automated proofs, cryptography and complexity theory.

Focusing on learning theory, we show that restriction access provides a setting in which one can obtain positive results for problems that have resisted attack in the black-box access model.

We introduce a PAC-learning version of restriction access, and show that one can efficiently learn both decision trees and DNF formulas in this model. These two classes are not known to be learnable in the PAC model with black-box access.

Our DNF learning algorithm is obtained by a reduction to a general learning problem we call population recovery, in which random samples from an unknown distribution become available only after a random part of each was erased. More specifically, assume that every member of an unknown population is described by a vector of values (to some xed set of attributes). The algorithm has access to random samples, each of which is a random member of the population, whose values are given only for a random subset of the attributes!

Analyzing our efficient algorithm to fully recover the unknown population calls for understanding another basic problem of independent interest: "robust local inversion" of matrices. The population recovery algorithm and construction of robust local inverses for some families of matrices are the main technical contributions of the paper.

Joint work with Zeev Dvir, Anup Rao, and Amir Yehudayoff

 

 

The December CCI monthly meeting will be December 2nd in room 402 at the CS dept.  The day will be  devoted to discussing and hearing about new alternative approaches to "learning".

Schedule:

10am-10:30am  PC meeting

10:30-10:50am  Sanjeev Arora: Is Machine Learning Easy?

10:50am-11:30 am Aravindan Vijayaraghavan: Approximation Algorithms for Semi-random Partitioning problems [video]

11:30am-12:10 pm Rong Ge: Computing a Nonnegative Matrix Factorization -- Provably [video]

12:10pm-1:25pm  Lunch

1:25pm-1:45pm Grant Schoenebeck:  Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach [video]

1:45pm -  Avi Wigderson: Restriction Access [video]

-------------------------------------------

Abstracts:

 

Sanjeev Arora: Is Machine Learning Easy?

I'll briefly talk about the roadblock in computational learning theory --namely, that most interesting learning problems are hard---and some vague thoughts about how one may circumvent it, using some of the day's talks as examples.

-------------------------------------------

Aravindan Vijayaraghavan:  Approximation Algorithms for Semi-random Partitioning problems.

We propose and study a new semi-random model for graph partitioning problems.We believe that it captures many properties of real--world instances. The model is more flexible than the semi-random model of Feige and Kilian and planted random model ofBui, Chaudhuri, Leighton and Sipser.

We develop a general framework for solving semi-random instances and apply it to several problems of interest.We present constant factor bi-criteria approximation algorithms for semi-random instances of the Balanced Cut, Multicut, Min Uncut and Small-Set Expansion problems. We also show how toalmost recover the optimal solution if the instance satisfies an additional expanding condition. Our algorithmswork in a wider range of parameters than algorithms for previously studied random and semi-random models.

Joint work with Konstantin Makarychev and Yury Makarychev

--------------------

Rong Ge:  Computing a Nonnegative Matrix Factorization -- Provably

In the Nonnegative Matrix Factorization (NMF) problem we are given an $n \times m$ nonnegative matrix $M$ and an integer $r > 0$. Our goal is to express $M$ as $A W$ where $A$ and $W$ are nonnegative matrices of size $n \times r$ and $r \times m$ respectively. In some applications, it makes sense to ask instead for the product $AW$ to approximate $M$ -- i.e. (approximately) minimize $\norm{M - AW}_F$ where $\norm{}_F$ denotes the Frobenius norm; we refer to this as Approximate NMF. This problem has a rich history spanning quantum mechanics, probability theory, data analysis, polyhedral combinatorics, communication complexity, demography, chemometrics, etc. In the past decade NMF has become enormously popular in machine learning, where $A$ and $W$ are computed using a variety of local search heuristics. Vavasis proved that this problem is NP-complete. We initiate a study of when this problem is solvable in polynomial time:

1. We give a polynomial-time algorithm for exact and approximate NMF for every constant $r$. Indeed NMF is most interesting in applications precisely when $r$ is small.

2. We complement this with a hardness result, that if exact NMF can be solved in time $(nm)^{o(r)}$, 3-SAT has a sub-exponential time algorithm. This rules out substantial improvements to the above algorithm.

3. We give an algorithm that runs in time polynomial in $n$, $m$ and $r$ under the separablity condition identified by Donoho and Stodden in 2003. The algorithm may be practical since it is simple and noise tolerant (under benign assumptions). Separability is believed to hold in many practical settings.

To the best of our knowledge, this last result is the first example of a polynomial-time algorithm that provably works under a non-trivial condition on the input and we believe that this will be an interesting and important direction for future work

Joint work with Sanjeev Arora, Ravi Kannan, and Ankur Moitra.

---------------------------------

Grant Schoenebeck Finding Overlapping Communities in Social Networks: Toward a Rigorous Approach

A community in a social network is usually understood to be a group of nodes more densely connected with each other than with the rest of the network. This is an important concept in most domains where networks arise: social, technological, biological, etc. For many years algorithms for finding communites implicitly assumed communities are nonoverlapping (leading to use of clustering-based approaches) but there is increasing interest in finding overlapping communities. A barrier to finding communities  is that the solution concept is often defined in terms of an NP-complete problem such as Clique or Hierarchical Clustering.

This paper seeks to initiate a rigorous approach  to the problem of finding overlapping communities, where ``rigorous'' means that we clearly state the following: (a) the object sought by our algorithm (b) the assumptions about the underlying network (c) the (worst-case) running time.

Our assumptions about the network lie between worst-case and average-case. An average-case analysis would require a precise probabilistic model of the network, on which there is currently no consensus. However, some plausible assumptions about network parameters can be gleaned from a long body of work in the sociology community spanning five decades focusing on the study of individual communities and {\em ego-centric networks} (in graph theoretic terms, this is the subgraph induced on a node's neighborhood).  Thus our assumptions are somewhat ``local'' in nature. Nevertheless   they suffice to permit a rigorous analysis of running time of algorithms that recover global structure.

Our algorithms use random sampling similar to that in property testing and algorithms for dense graphs. We note however that our networks are not necessarily dense graphs, not even in local neighborhoods.

Our algorithms explore a local-global relationship between ego-centric and socio-centric networks that we hope will provide a fruitful framework for future work both in computer science and sociology.

Joint work with Sanjeev Arora, Rong Ge, and Sushant Sachdeva.

------------------------

Avi Wigderson:  Restriction Access

We introduce a notion of non-black-box access to computational devices (such as circuits, formulas, decision trees, and so forth) that we call restriction access. Restrictions are partial assignments to input variables. Each restriction simpli fies the device, and yields a new device for the restricted function on the unassigned variables. On one extreme, full restrictions (assigning all variables) correspond to evaluating the device on a complete input, yielding the result of the computation on that input, which is the same as standard black-box access. On the other extreme, empty restrictions (assigning no variables) yield a full description of the original device. We explore the grey-scale of possibilities in the middle. Different variants of restriction access, in which the values to restricted variables, as well as the subset of free (unassigned) variables, are generated deterministically or randomly, in friendly or adversarial fashions may naturally suit a variety of situations in computational learning, computational biology, automated proofs, cryptography and complexity theory.

Focusing on learning theory, we show that restriction access provides a setting in which one can obtain positive results for problems that have resisted attack in the black-box access model.

We introduce a PAC-learning version of restriction access, and show that one can efficiently learn both decision trees and DNF formulas in this model. These two classes are not known to be learnable in the PAC model with black-box access.

Our DNF learning algorithm is obtained by a reduction to a general learning problem we call population recovery, in which random samples from an unknown distribution become available only after a random part of each was erased. More speci fically, assume that every member of an unknown population is described by a vector of values (to some xed set of attributes). The algorithm has access to random samples, each of which is a random member of the population, whose values are given only for a random subset of the attributes!

Analyzing our efficient algorithm to fully recover the unknown population calls for understanding another basic problem of independent interest: "robust local inversion" of matrices. The population recovery algorithm and construction of robust local inverses for some families of matrices are the main technical contributions of the paper.

Joint work with Zeev Dvir, Anup Rao, and Amir Yehudayoff

The October CCI monthly meeting will be October 7th in room 402 at the CS dept. Mark Braverman and Michael Saks will tell us about Information Theory and its relationship with Theoretical Computer Science including some exciting recent results that point toward promising avenues for future work.

See schedule, titles and abstracts below

————————

10:30 – 11:00: PI only meeting

11:15 – 12:00: Michael Saks: Information theoretic methods for complexity lower bounds Part I

12:00 – 12:30: Lunch

12:30 – 1:15: Michael Saks, Part II.

1:20 – 2:05: Mark Braverman: Information complexity, compression and direct sum theorems

2:15 – 3:00: Mark Braverman continues

————————

Michael Saks : Information theoretic methods for complexity lower bounds.

Computation can be viewed as a process of collecting, moving and transforming data. Information theory can be used to focus on the ``collecting'' and ``moving'' part to prove lower bounds, by providing a measure of the amount of information that must be collected/moved to solve a given problem and comparing it to the rate at which a computation can do the collecting/moving.

This talk (in two parts) will focus on two computational models where information theory has been applied to proving lower bounds, and where there is potential for further applications.

One area is ``dynamic data structures'' where we wish to maintain a data set in a way that allows certain types of updates to the data set and queries to the data set. Of interest is the tradeoff between the time to do an update and the time to do a query. We focus on the cell-probe model, which is the most powerful model studied for representing data structures. Trade-off lower bounds are known for many data structure problems either updates or queries require time at least logarithmic in the data set size. A major challenge is to prove trade-off lower bounds that are superlogarithmic, or even n^{epsilon} for some data structure problem.

The second area is communication complexity, where information theoretic methods have been used to prove various lower bounds for two-party communication. I'll review some of these methods with an eye to the major challenge of developing methods to prove lower bounds for multi-party communication in the so-called ``number-on-forehead'' model.

-----------

Mark Braverman: Information complexity, compression and direct sum theorems

[Video (Part 1)] [Video (Part 2) [no sound]]

Compressing interactive computation can be viewed as a natural generalization of Shannon's noisy coding theorem. I will discuss what we know about interactive compression, and why such results are equivalent to direct sum theorems in two-party communication complexity.

More generally, I will show that information cost I(f) can be defined as a natural fundamental property of a functionality f, and discuss some properties of I(f).

I will conclude with a list of open problems and directions.

The first CCI monthly meeting for this year will be on September 16 in room 402 at the CS dept. See schedule/abstracts below:

————————

10:30 – PI only meeting

12:00 – Lunch

12:15 –  Ankur Moitra: Disentangling Gaussians

13:15 – Break

13:30 – Eden Chlamac: Bounding 2-Spanner Degrees by Finding Dense Subgraphs

————————

Ankur Moitra: Disentangling Gaussians

[Complete Video]

Abstract:  Given data drawn from a mixture of multivariate Gaussians, a basic problem is to accurately estimate the mixture parameters. We provide a polynomial-time algorithm for this problem for any fixed number (k) of Gaussians in n dimensions (even if they overlap), with provably minimal assumptions on the Gaussians and polynomial data requirements.

In statistical terms, our estimator converges at an inverse polynomial rate, and no such estimator (even exponential time) was known for this problem (even in one dimension, restricted to two Gaussians). Our algorithm reduces the n-dimensional problem to the one dimensional problem, where the method of moments is applied. Additionally, in order to prove correctness for our univariate learning algorithm, we develop a novel explanation for why the method of moments (due to Pearson in 1894) works based on connections to algebraic geometry.

This is joint work with Adam Tauman Kalai and Gregory Valiant.

————

Eden Chlamtac: Bounding 2-Spanner Degrees by Finding Dense Subgraphs

[Complete Video]

Abstract:  A spanner (of a graph) with stretch s (an s-spanner) is a subset of edges of the graph for which the shortest path metric is preserved up to a factor s. Spanners have a number of applications ranging from parallel and distributed computing to property testing. We focus on the Lowest-Degree 2-Spanner (LD2S) problem, where we wish to find a 2-spanner of a graph with unit edge lengths, while minimizing the maximum degree in the spanner. This problem was previously studied by Kortsarz and Peleg [SODA'94; Siam J. Comp.'98], who gave a \tilde{O}(Delta^{1/4}) approximation, where Delta is the maximum degree in the original graph. We improve on this by giving a

\tilde{O}(Delta^c) approximation, where c = 3-2\sqrt{2} = 0.17...

Our algorithm relies on decomposing a linear programming (LP) relaxation for LD2S into several LP relaxations for the Smallest m-Edge Subgraph (SmES) problem, which we round independently (also giving a \tilde{O}(n^c) approximation for SmES in the process). A novel and (in the context of spanners) crucial aspect of our SmES algorithm is a "faithful rounding" of an LP hierarchy, in which we produce a distribution on subgraphs where both vertices and edges are chosen (to be in the subgraph) with probabilities proportional to the corresponding LP variables. This relatively strong condition on vertices and edges (which correspond to singleton LP variables) is achieved despite the fact that the rounding relies on information from the higher-moment variables in the LP hierarchy solution.

Based on joint work with Michael Dinitz and Robert Krauthgamer.

 

The aim of this multidisciplinary workshop is to bring together various communities who work on counting, inference, and optimization problems related to graphs. These communities include

Schedule, Supplementary Material, Slides, and Papers.

 

Organizing committee:

- Jin-Yi Cai (U. Wisconsin-Madison)

- Michael Chertkov (Los Alamos National Lab)

- G. David Forney, Jr. (MIT)

- Pascal O. Vontobel (HP Labs Palo Alto)

- Martin J. Wainwright (UC Berkeley).

 

Lodging: If you plan to come to the workshop and need a hotel room, we suggest that you reserve a room at the Nassau Inn as soon as possible. Their phone number is 1-800-862-7728 and you should ask for group number 15671 or `CIOG' to get the special workshop rate (135$ + Tax for single or double occupancy rooms). The deadline for booking a room using the special rate is Sep 30. DO NOT BOOK YOUR ROOM ONLINE! THE SPECIAL RATE IS ONLY AVAILABLE WHEN MAKING A RESERVATION BY PHONE.

 

 

Contact:

Questions regarding the scientific program should be directed to counting11.workshop@gmail.com .

For questions regarding local arrangements contact local.counting11@gmail.com

 

The next meeting of the Center of Computational Intractability will be held on Friday, April 1. See below Schedule and abstracts.

Location: Room 402

Schedule:

10:30 : PI meeting

11:00 : David Blei - "Variational inference for approximating probability distributions"  

12:00 : Lunch

13:30 : Assaf Naor - "The Grothendieck constant is strictly smaller than Krivine’s bound"

14:30 : Shachar Lovett - "Weighted families of k-wise independent permutations" 

---

-----

Assaf Naor - "The Grothendieck constant is strictly smaller than Krivine’s bound"

[Complete Video] (no sound)

Abstract: We prove that the Grothendieck constant is strictly smaller

than the 1977 upper bound of Krivine, which was believed to be sharp.

Specifically,  $K_G<\frac{\pi}{2\log\left(1+\sqrt{2}\right)}$, where

$K_G$ is the Grothendieck constant.

Joint work with M. Braverman, K. Makarychev, Y. Makarychev.

----

Shachar Lovett  : "Weighted families of k-wise independent permutations"

[Complete Video] (no sound)

Abstract:A family of permutations in S_n is k-wise independent if a uniform

permutation chosen from this family maps any distinct k elements to

any distinct k elements equally likely. Efficient constructions of

k-wise independent permutations are known for k=2 and k=3, but are

unknown for k>=4. In fact, it is known that there are no non-trivial

subgroups of S_n which are k-wise independent for k>=4 and n>=25.

Faced with this adversity, research has turned towards constructing

almost k-wise independent families, where small errors are allowed.

Such families were constructed by Kaplan, Naor and Reingold; and can

also be obtained from Kassabov's explicit set of generators of S_n

which forms an expander.

In this work we consider a different model: distributions with small

support which are perfectly k-wise independent. That is, we allow

elements to have non-uniform weights. We first show that a random set

of size n^{O(k)} supports a k-wise independent distribution w.h.p, and

that this distribution can be found efficiently. We then derandomize

the construction, giving explicit such sets, and hence an efficient

deterministic algorithm to find k-wise independent distributions with

support size n^{O(k)}.

Joint work with Noga Alon.

------------------

[Video::Russell] [Video::Mike]

[Video]

Schedule:

10:00 - 10:30 : PI only meeting

10:30 - 11:00 : Rajiv Gandhi - A proposed summer program for high schoolers.

11:00 - 13:00 :  Russell Impagliazzo - Formalizing and proving lower

bounds for algorithmic paradigms [Video]

(Lunch at 12:00)

*Break*

14:30 - 15:30 : Ofer Neiman -  Lower Bounds for Dimension Reduction in L_1 [Video]

-----------------------------

Russell Impagliazzo - Formalizing and proving lower bounds for

algorithmic paradigms

To prove $P \neq NP$, we have to show that search problems

are intractible for {\em any} algorithm.

However, even the {\em first} algorithm people thought of for

solving constraint satisfaction problems, the Davis-Putnam

procedure and its variants, is far from understood.  In

addition to its use in a complete search, Davis-Putnam and

variations can be used as a heuristic, pruning unpromising

subsearches to concentrate on those most likely to lead

to solutions.  In particular, Paturi, Pudlak,and Zane, later

improved in joint work with Saks, get the best time for

rigorously analyzed $k$-SAT algorithms through such a search.

Although

proof complexity shows, via resolution lower bounds, that

all versions of Davis-Putnam require exponential time on

unsatisfiable  instances, this gives little insight into its

use on satisfiable instances, such as when used as a search

heuristic.

We survey a line of work begun by Borodin, Nielsen and Rackoff

which aims to formalize paradigms of algorithms, such as

greedy algorithm, back-tracking, dynammic programming

and divide-and-conquer.

We will demonstrate how such formalizations, in addition to

giving a formal meaning to commonly used algorithm paradigms,

can be used to prove limitations on the ``obvious'' methods

for search and optimization.  These lower bounds can be on

time or approximation ratio, or give a trade-off between the

two.  The talk will stress the many open problems remaining

in this fledging area, and is meant to be an invitation to

encourage more work of this kind.

All of the talk is based on joint work with Sashka Davis, and much

of it is also joint with Josh Buresh-Oppenheim.  Some of it is

based on joint work with Misha Alekhnovich, Al Borodin, Jeff Edmonds,

Avner Magen, and Toni Pitassi.

-------------------------------

Ofer Neiman -  Lower Bounds for Dimension Reduction in L_1

Abstract: Given X, an n-point subset of L_1, the question we consider

is the dimension required for embedding X into L_1 with some small

distortion. Brinkman and Charikar showed one needs at least

n^{\Omega(1/D^2)} dimensions for distortion D, and roughly

n^{1/2-O(\eps)} for 1+\eps distortion.

In this work we show that for every \eps>0 there is a subset of L_1

that requires dimension n^{1-O(1/log(1/\eps))} for any 1+\eps

distortion embedding to L_1.

Joint work with Alex Andoni, Moses Charikar and Huy Nguyen

--------------

Dec 10, 2010

Zero-sum games with adversarial leakage

Noga Alon (Tel Aviv University and IAS)

Abstract: We introduce the study of adversarial leakage of information in games, and study its effect on general zero-sum games with binary payoffs.

Joint work Yuval Emek, Michal Feldman, and Moshe Tennenholtz

 

Nov 19, 2010

Highway Dimension: From Practice to Theory and Back

Andrew V. Goldberg (Microsoft Research - Silicon Valley)

Computing driving directions has motivated many shortest path heuristics that answer queries on continental-scale networks, with tens of millions of intersections, in real time. The underlying algorithms are intuitive, but until recently there was no theoretical explanation of their performance. We review some of these algorithms and give the first theoretical analysis for them on a non-trivial class of networks.

For our analysis, we introduce the notion of highway dimension. The analysis works for networks with low highway dimension and gives a unified explanation of algorithms' good performance. Our analysis explores an unexpected relationship to VC-dimension and learning theory and applies the latter to graph algorithm design.

We also propose a new algorithm that achieves a better theoretical time bound and is in the spirit of labeling algorithms for approximate shortest paths from the distributed computing literature. Our experiments show that an implementation of this algorithm is extremely fast in practice, validating the theoretical prediction.

Joint work with Ittai Abraham, Amos Fiat, and Renato Werneck

 

Nov 12, 2010

Truth, Envy and Profit

Jason Hartline (Northwestern University)

Abstract: We consider (profit maximizing) mechanism design in general settings that include, e.g., position auctions (for selling advertisements on Internet search engines) and single-minded combinatorial auctions. We analyze optimal envy-free pricing in these settings and give economic justification for using optimal envy-free revenue as a benchmark for prior-free mechanism design and analysis. In addition to its economic justification, the envy-free revenue has a very simple structure and a strong connection to incentive compatibility (a.k.a., truthfulness) constraints in mechanism design.

As a first example of the connection between envy-free pricing and incentive compatible mechanism design, because the structures of optimal pricings and optimal mechanisms are similar, we give a mechanism design reduction from structurally rich environments including position auctions (and environments with a matroid structure) to multi-unit auction environments (i.e., auctioning $k$ identical units to $n$ unit-demand agents). For instance, via this reduction we are able to extend all prior-free digital good auctions to position auctions with a factor of two of loss in the approximation factor.

As a second example we extend a variant of the random sampling auction to get constant approximations for general downward closed (i.e., if we can serve a given set of agents, we can serve any subset) settings.

This talk will not assume any background in mechanism design. Joint work with Qiqi Yan.

 

Oct 29, 2010

The Power of Simple Tabulation Hashing

Mihai Patrascu (AT&T Labs)

Abstract: Randomized algorithms promise to achieve simplicity and efficiency simultaneously. Unfortunately, this promise has typically not been realized when the algorithms need a hash function. The following are easy statements about truly random hashing, but we do not have any realistic hash function with O(1) evaluation time that achieves them:

* when distribution n balls into n bins, the maximum load is O(lg n / lglg n) whp.

* if balls are placed in the least loaded of 2 bins, the expected maximum load is O(lglg n).

* a cuckoo hashing table can be constructed with probability 1-O(1/n). (In other words, a load of 1 can be achieved if elements can be moved among two choices.)

* if n keys are hashed to [0,1], any one of them is the minimum with probability 1/n.

We show that simple tabulation achieves these properties (or a good approximation). This hash function takes a few lines of code, and is roughly as fast as one multiplication on current architectures. Though simple tabulation has been known for decades, it was thought to have weak mathematical properties, since it is only 3-independent. Our analysis suggests a significant limitation in the k-independence paradigm of [Carter, Wegman].

 

October 15, 2010 (Double Header)

Improved bounds for geometric permutations

Natan Rubin (Tel Aviv University)

Abstract: We show that the number of geometric permutations of an arbitrary collection of $latex n$ pairwise disjoint convex sets in $latex R^d$, for $latex d\geq 3$, is $latex O(n^{2d-3}\log n)$, improving Wenger's 20 years old bound of $latex O(n^{2d-2})$.

Joint work with Haim Kaplan and Micha Sharir.

[Video]

 

October 15, 2010 (Double Header)

Approximating Sparsest Cut in Graphs of Bounded Treewidth

Eden Chlamtac (University of Toronto)

Abstract: We examine the Sparsest Cut problem. This is a fundamental NP-hard problem which is intimately related to several graph parameters, such as edge-expansion, minimum balanced cut and conductance, and has surprising connections to the theory of Metric Embeddings.

We consider this problem on graphs of bounded treewidth. This is a well-studied class of graphs, and many problems that are generally NP-hard can be solved efficiently on these graphs; for example, uniform-demand Sparsest Cut, where every pair of vertices has unit demand.

We give a constant-factor approximation algorithm for Sparsest Cut with general demands in bounded treewidth graphs. Our algorithm relies crucially on the Sherali-Adams hierarchy of LP relaxations.

This talk is based on joint work with Robert Krauthgamer and Prasad Raghavendra.

[Video]

 

 

 

See below the schedule for the center meeting on Friday Oct 1.

Note: The talk by Swastik Kopparty will *not* be the same as his talk at the IAS on the same paper (attending both is OK).

---

10-10:30   : PI only meeting

10:30-12:15: Rocco Servedio : "Boolean threshold functions:  the untold story" [Video]

12:15-2pm : Lunch, and free interaction time

2:00 - 3:00 : Short informal talks by center postdocs - Shachar Lovett [Video] and Grant Schoenebeck [Video]

3:00 - 4:00 : Swastik Kopparty: "High rate codes with sublinear time decoding" [Video]

---

Rocco Servedio :  Boolean threshold functions:  the untold story

The goal of this talk is to provide background and context for the upcoming October 21-22 workshop on "Analysis and Geometry of Boolean Threshold Functions."  The talk will survey a range of results -- some old, some new -- on linear threshold functions and polynomial threshold functions, to complement the results that will be presented at the workshop.

A recurring theme of the talk will be that establishing bounds on various natural parameters of polynomial threshold functions (degree, average sensitivity, etc.) yields efficient algorithms for a range of well-studied problems in computational learning theory.

Swastik Kopparty: High-rate codes with sublinear-time decoding

Locally decodable codes are error-correcting codes that admit

efficient decoding algorithms; any bit of the original message can be

recovered by looking at only a small number of locations of a

corrupted codeword. The tradeoff between the rate of a code and the

locality/efficiency of its decoding algorithms has been well studied,

and it has widely been suspected that nontrivial locality must come at

the price of low rate. A particular setting of potential interest in

practice is codes of constant rate. For such codes, decoding

algorithms with locality O(k^{epsilon}) were known only for codes of

rate epsilon^{Omega(1/epsilon)}, where k is the length of the message.

Furthermore, for codes of rate 1/2, no nontrivial locality has been

achieved.

In this talk, I will describe a new family of locally decodable codes

that have very efficient local decoding algorithms, and at the same

time have rate approaching 1. We show that for every alpha > 0 and

epsilon > 0, for infinitely many k, there exists a code C which

encodes messages of length k with rate 1-alpha, and is locally

decodable from a constant fraction of errors using O(k^{epsilon})

queries and time.

These codes, which we call multiplicity codes, are based on evaluating

multivariate polynomials and their derivatives. Multiplicity codes

extend traditional multivariate polynomial based codes; they inherit

the local-decodability of these codes, and at the same time achieve

better tradeoffs and flexibility in the rate and minimum distance.

Joint work with Shubhangi Saraf and Sergey Yekhanin

June 13 - 17, 2011

Organizing committee:  Sanjeev Arora (Princeton), Moses Charikar (Princeton), Sanjeev Khanna (U. Penn), Mohammad Taghi Hajiaghayi (U. Maryland and AT&T Labs), Vijay Vazirani (Georgia Tech), Lisa Zhang (Bell Labs)

 

Lodging: If you plan to come to the workshop and need a hotel room, we suggest that you reserve a room at the Nassau Inn as soon as possible. Their phone number is 1-800-862-7728  and you should ask for group number 14760 or `Approximation algorithms group' to get the special workshop rate (135$ + Tax for single or double occupancy rooms). The deadline for booking a room using the special rate is May 11.  DO NOT BOOK YOUR ROOM ONLINE! THE SPECIAL RATE IS ONLY AVAILABLE WHEN MAKING A RESERVATION BY PHONE.

 

 

Dorms: We have a very limited number of dorm rooms at a rate of 49.50$ a person per night (single, air-conditioned rooms with semi-private bath). If you are interested in this option please send an email to local.approx11@gmail.com including your name, the dates of your stay, and your gender (for room assignments). Please use 'Dorm request' as the subject line of your email.

[UPDATE:] There are no more dorm rooms available for the workshop.

 

 

Contact:

Questions regarding the scientific program should be directed to approx.workshop@gmail.com .

For questions regarding local arrangements contact local.approx11@gmail.com

Confirmed speakers:

 

 

May 28, 2010

Edge-Disjoint Paths via Raecke Decompositions

Matthew Andrews (Bell Labs)

Abstract. The Edge-Disjoint Paths (EDP) problem is one of the original NP-hard problems. We are given a set of source-destination pairs in a graph and we wish to connect as many of them as possible using edge-disjoint paths.

The Edge-Disjoint Paths with Congestion (EDPwC) problem is a relaxation in which we want to route approximately as many demands as in the optimum solution to EDP but we allow ourselves a small amount of congestion on each edge.

In this talk we shall give a brief history of these problems and describe a new algorithm for EDPwC based on the notion of a Raecke decomposition.  This algorithm gives a polylog(n) approximation for the number of routed demands as long as we allow poly(log log n) congestion on each edge.

Play video

 

Apr 30, 2010

Subexponential Algorithms for Unique Games and Related Problems

David Steurer (Princeton University)

Abstract. We give a subexponential time approximation algorithm for the Unique Games problem: Given a Unique Games instance with alphabet size k such that a 1-epspilon^6 fraction of the constraints can be satisfied, our algorithm finds in time exp(k*n^epsilon) an assignment that satisfies a 1-epsilon fraction of the constraints.

We also obtain subexponential algorithms with similar approximation guarantees for Small-Set Expansion and Multi Cut. For Max Cut, Sparsest Cut and Vertex Cover, our techniques lead to subexponential algorithms with improved approximation guarantees on subclasses of instances.

Khot's Unique Games Conjecture (UGC) states that it is NP-hard to achieve approximation guarantees such as ours for Unique Games. While our result stops short of refuting the UGC, it does suggest that Unique Games is significantly easier than NP-hard problems such as Max 3-SAT, Label Cover and more, that are believed not to have subexponential algorithms achieving a non-trivial approximation ratio.

The main component in our algorithms is a new kind of graph decomposition that may have other applications: We show that by changing an epsilon fraction of its edges, any regular graph on n vertices can be broken into disjoint parts such that the stochastic adjacency matrix of each part has at most n^epsilon eigenvalues larger than 1-epsilon^6.

Joint work with Sanjeev Arora and Boaz Barak.

 

Apr 23, 2010

Fast Approximation of Multicommodity Flow Problems via Dynamic Graph Algorithms

Aleksander Madry (MIT)

Abstract. We present faster (1-eps)-approximation schemes for various versions of the multicommodity flow problem. In particular, if eps is moderately small and the size of every number used in the input instance is polynomially bounded, the running times of our algorithms match -- up to poly-logarithmic factors and some provably optimal terms -- the Omega(mn) flow-decomposition barrier for single-commodity flow.

Our approach is based on combining the existing Lagrangian-relaxation algorithms for these problems with ideas from dynamic graph algorithms.

 

Apr 16, 2010

Differentiation in metric spaces and the geometry of graphs

James Lee (University of Washington)

Abstract. A number of generalizations of classical differentiation theory have arisen in geometry and analysis in order to handle spaces that lack some of the special structure of Euclidean space (e.g. infinite dimensional Banach spaces, or non-abelian groups, or even discrete metric spaces).

I will discuss a rather elementary, yet powerful approach called "coarse differentiation" which originally arose in work of Eskin, Fisher, and Whyte in geometric group theory. Then I will present a simple recursive construction which takes a base graph G, and produces a much larger graph that contains copies of G "at every scale."

By instantiating the construction with G being, respectively, a 4-cycle, an expander graph, the hypercube, and a discrete version of the sphere, we show how to answer four somewhat unrelated questions that arose previously in

metric embeddings.

Play video

 

Mar 26, 2010

Public-key Encryption Schemes with Auxiliary Input

Vinod Vaikuntanathan (IBM T.J. Watson)

Abstract. We construct public-key cryptosystems that remain secure even when the adversary is given any computationally uninvertible function of the secret key as auxiliary input (even one that may reveal the secret key information-theoretically). Our schemes are based on the decisional Diffie-Hellman and Learning with Errors problems.

Our technical contributions include:

• a novel extension of the Goldreich-Levin theorem to provide a hard-core (pseudorandom) value over large fields, and


• a proof that the learning with errors assumption holds even in the presence of auxiliary information about the secrets.

Joint work with Yevgeniy Dodis, Shafi Goldwasser, Yael Kalai and Chris Peikert.

Play video

Below is the video for the talk on Thursday, March 25, 2010.

Play video (Dept Colloquium)

 

Mar 5, 2010

PTAS for planar Steiner forest

Mohammad Hossein Bateni (Princeton University)

Abstract. We describe a thorough complexity study of Steiner forest in bounded treewidth graphs, planar graphs, and bounded genus graphs. We give the first polynomial-time approximation scheme for the Steiner forest problem on planar graphs and, more generally, on graphs of bounded genus. The crux of the process is a clustering procedure called prize-collecting clustering that breaks down the input instance into separate subinstances which are easier to handle. We also give a polynomial-time approximation scheme for Steiner forest on graphs of bounded treewidth, a problem that is NP-hard even on graphs of treewidth 3, and show that Steiner forest can be solved in polynomial time for series-parallel graphs (graphs of treewidth at most two) by a combination of dynamic programming and minimum cut computations.

This is joint work with MohammadTaghi Hajiaghayi and Daniel Marx.

Play video

  

Feb 26, 2010

The Intersection of Two Halfspaces Has Maximum Threshold Degree

Alexander Sherstov (Microsoft Research)

Abstract. The threshold degree of a Boolean function f : {0,1}^n -> {-1,+1} is the least degree of a real polynomial p with f(x) = sgn p(x). We prove that the intersection of two halfspaces on {0,1}^n has threshold degree Omega(n), which matches the trivial upper bound and solves an open problem due to Klivans (2002). The best previous lower bound was Omega(log n/log log n). Our result shows that the intersection of two halfspaces on {0,1}^n (a central unresolved challenge in computational learning theory) only admits a trivial 2^{Theta(n)}-time learning algorithm based on sign-representation by polynomials, unlike the advances achieved in PAC learning DNF formulas and read-once Boolean formulas.

Play video

 

 

Feb 12, 2010

Simpler, Better Balanced Search Trees

Siddhartha Sen (Princeton University)

Abstract. Balanced search trees are ubiquitous in computer science, appearing in database systems, the Linux task scheduler, and many other applications. In this talk, I will present new balanced search trees that are simpler

and more efficient than existing trees, showing that the design space of this classical data structure is far from being exhausted.

We begin with the rank-balanced tree, a simple relaxation of AVL trees that takes $O(1)$ amortized time to rebalance after insertions and deletions. Rank-balanced trees perform fewer rotations than red-black trees and achieve better height bounds. Using a novel analysis that relies on an exponential potential function, we show that rebalancing modifies nodes exponentially infrequently in their heights.

Building on these techniques, we show that balanced search trees remain efficient even if deletion is done without any rebalancing. These results justify the practice of many B-tree-based database systems. In the case

of binary trees, the underlying data structure must be modified to obtain such a result, leading to the relaxed AVL (ravl) tree. Ravl trees have height logarithmic in the number of insertions, and rebalancing modifies nodes exponentially infrequently in their heights. However, this seems to require $\Omega(\log\log n)$ bits of balance information at each of the $n$ nodes. Both rank-balanced trees and ravl trees show great promise in practice and are currently being taught to undergraduates.

Play video

 

 

Feb 19, 2010

How to boost the accuracy without changing the distribution

Vitaly Feldman, IBM Research at Almaden

Abstract. We consider the problem of boosting the accuracy of weak learning algorithms (Schapire 1990).

Known algorithms for this problem execute the weak learner on the same target function but over different distributions on the domain. Application of such boosting algorithms requires a distribution-independent weak learning algorithm. We demonstrate that it is also possible to boost the accuracy of a learning algorithm by

executing it on different target functions but without changing the distribution over the domain.

We then use our boosting algorithm to characterize the complexity of strong learning in the Statistical Query framework of Kearns (1993) and to learning in the agnostic model. When applied to the weak agnostic parity learning algorithm of Goldreich and Levin (1989) our boosting algorithm yields a simple PAC learning algorithm for DNF and an agnostic learning algorithm for decision trees over the uniform distribution using membership queries. These results substantially simplify Jackson's famous DNF learning algorithm (1994) and the recent result of Gopalan et al. (2008).

The talk is based on:

A Complete Characterization of Statistical Query Learning with Applications to Evolvability (FOCS 2009) and Distribution-Specific Agnostic Boosting (ICS 2010)

Play video

 

 

Jan 29, 2010

Tight bound for Gap Hamming Distance

Oded Regev, Tel-Aviv University

Abstract. We consider the Gap Hamming Distance problem in communication complexity. Here, Alice receives an $n$-bit string $x$, and Bob receives an $n$-bit string $y$. They are promised that the Hamming distance between x and y is either at least $n/2+\sqrt{n}$ or at most $n/2-\sqrt{n}$, and their goal is to decide which is the case.

We show a tight lower bound of \Omega(n) on the randomized communication complexity of the problem. The bound is based on a new geometric statement regarding correlations in Gaussian space, related to a result of C. Borell from 1985.

Based on joint work with Amit Chakrabarti.

Play video

 

January 25, 2010 (Monday)

An Improved Competitive Algorithm for Reordering Buffer Management

Noa Elgrabli, Technion

Abstract. In the reordering buffer management problem, a stream of colored items arrives at a service station equipped with a buffer that has a limited storage capacity of $k$ items. The buffer is used to permute the input stream (in a limited way) in order to

minimize the context switching cost, which is incurred whenever there is a color change between consecutive items served. In our work we design and analyze an on-line reordering buffer management algorithm with improved $O\left(\frac{\log k}{\log\log k}\right)$ competitive ratio for non-uniform costs. This improves on the best previous result (even for uniform costs) of Englert and Westermann (ICALP 2005) giving $O(\log k)$ competitive ratio, which was also the best (off-line) polynomial time approximation guarantee for this problem. Our analysis is based on an intricate dual fitting argument using a linear programming relaxation for the problem.

Joint work with Yuval Rabani

 

Jan 22, 2010

A nonlinear approach to dimension reduction

Robert Krauthgamer, Weizmann Institute

Abstract. The celebrated Johnson-Lindenstrauss lemma says that every n points in Euclidean space can be represented with O(log n) dimensions with only a minor distortion of pairwise distances. It has been conjectured that a much-improved dimension reduction representation is achievable for many interesting data sets, by bounding the target dimension in terms of the intrinsic dimensions of the data, e.g. by replacing the log(n) term with the doubling dimension. This question appears to be quite challenging, requiring new (nonlinear) embedding techniques.

We make progress towards resolving this question by presenting two dimension reduction theorems with similar flavor to the conjecture. For some intended applications, these results can serve as an alternative to the conjectured embedding.

Joint work with Lee-Ad Gottlieb.

Play video

 

Jan 15, 2010

Approximating the Asymmetric Traveling Salesman Problem

Michel Goemans, MIT

Abstract. The traveling salesman problem (TSP) --- the problem of finding the shortest tour through a set of cities --- is the prototypical combinatorial optimization problem. It comes in two flavors, the symmetric (STSP) and asymmetric (ATSP) versions; the latter corresponds to the setting in which the cost of traveling from A to B might differ from the cost from B to A. Whether one can efficiently find solutions in the asymmetric case that are within a constant factor of optimal has proved to be elusive despite considerable efforts, while the same question in the symmetric case has been settled for decades.

In this talk, I will describe a randomized algorithm for ATSP which delivers a solution within a factor $O(\log n/ \log\log n)$ of the optimum. This is the first approximation algorithm that breaks the logarithmic glass ceiling of approximability. The algorithm is somewhat reminiscent of Christofides' algorithm for the symmetric case. It first solves the classical Held-Karp linear programming relaxation of the problem, then generates a spanning tree T while disregarding the orientations of the arcs, and finally augments it into a directed Eulerian graph at minimum cost by solving a minimum cost flow problem. The cost of the final step depends on the thinness of the tree T. We show how to construct a suitable probability distribution on spanning trees which are sufficiently thin with high probability.

During the talk, our tour will bring us to visit polyhedral arguments, negative correlation, random spanning trees, maximum entropy distributions, approximate minimum cuts, Kirchhoff's matrix tree theorem, and several other concepts.

Play video

 

 

 

 

 

 

 

The schedule for Friday March 12 center meeting is below. The meeting will be at the usual place (room 402 in Princeton CS).

10:00 - PI meeting

10:45 - Alexandra Kolla:  Spectral Algorithms for Unique Games [Video]

11:30 - Lunch + talk - Steven Myers :  One-bit Encryption is Complete [Video]

12:30 - Coffee break

13:30 - David Steurer: An [latex] \mathrm{exp}(n^{\mathrm{poly}(\epsilon)})[/latex]-time algorithm for [latex] (1-\epsilon)[/latex]-satisfiable unique games [Video]

"Barriers in Computational Complexity II" workshop

August 26 - 30, 2010

Continuing the program that started with the first Barriers in Computational Complexity workshop in 2009, this workshop will focus on identifying and circumventing barriers that are preventing progress in several sub-fields of Computational Complexity.

This workshop will focus on five sub-fields that were not covered in the 2009 workshop: approximation algorithms and hardness of approximation, quantum computation, cryptography, communication and information in complexity and (geo)metric algorithms.

Schedule and abstracts

Here is a list of talks with slides:

Thursday, August 26

Approximation Algorithms and Hardness of Approximation

Organizer: Moses Charikar

Mohit Singh : Iterative Methods in Combinatorial Optimization [slides]

Seffi Naor : Online Algorithms, Linear Programming, and the k-Server Problem [slides]

[Video]

Sanjeev Arora : Semidefinite Programming based Approximation Algorithms [slides]

[Video]

Prasad Raghvendra : Complexity of CSPs: Exact and Approximation [slides]

[Video]

David Steurer : Subexponential Algorithms for Unique Games and Related Problems [slides]

[Video]



Friday August 27

Recent Advances and Challenges in Cryptography

Organizers: Shafi Goldwasser and Yuval Ishai

Daniele Micciancio (UCSD): Solving All Lattice Problems in Deterministic Single ExponentiaTime [slides]

[Video]

Craig Gentry (IBM Research): Directions in Homomorphic Encryption [slides]

[Video]

Omer Reingold (Microsoft Research & Weizmann): The Many Entropies in One-Way Functions [slides]

[Video]

Rafael Pass (Cornell): Concurrency and Parallel Repetition [slides]

[Video]

Vinod Vaikuntanathan (Microsoft Research): New Developments in Leakage-Resilient Cryptography [slides]

[Video]

Guy Rothblum (Princeton & IAS): Differentially Private Data Analysis: Progress and Challenges [slides]

[Video]



Saturday August 28

Quantum computation

Organizers: Scott Aaronson and Umesh Vazirani

Scott Aaronson: The Computational Complexity of Linear Optics [slides]

[Video]

Umesh Vazirani: Challenges of Hamiltonian Complexity [slides]

[Video]

Ronald deWolf: Quantum Proofs for Classical Theorems [slides]

[Video]

Chris Peikert: Lattices and Quantum Computation: Barriers and Opportunities [slides]

[Video]





Sunday August 29

Title: Communication and information in complexity

Organizer: Paul Beame

Paul Beame: Communication Complexity and Applications: An introduction and survey [slides]

T.S. Jayram: Information Complexity and the Geometry of Communication [slides]

Alexander Sherstov: Quantum and Unbounded-Error Communication Complexity [slides]

[Video]

Mihai Patrascu: Lower Bounds for Data Structures [slides]

[Video]

Anup Rao: Direct Sums and Compression in Communication Complexity [slides]

[Video]



Monday August 30

Title: (Geo)metric algorithms

Organizer: Piotr Indyk

Sariel Har-Peled: Finding Haystacks (and Other Structures) in Geometry [slides]

[Video]

Alex Andoni: Nearest neighbor search in high-dimensional spaces [slides]

[Video]

Jeff Erickson: Computational topology: Paths, Cuts, Flows, and Embeddings [slides]

[Video]

Anupam Gupta: Algorithmic applications of doubling metrics [slides]

[Video]

James Lee: Geometric obstructions for the Sparsest Cut problem [slides]

[Video]

Organizing committee:

Michael Saks (chair), Scott Aaronson, Sanjeev Arora, Paul Beame, Moses Charikar, Shafi Goldwasser, Piotr Indyk, Yuval Ishai, Robert Tarjan, Umesh Vazirani

 

Lodging: If you plan to come to the workshop and need a hotel room, we suggest you register (using the registration form at the bottom of this page) and reserve a room at the Nassau Inn as soon as possible. Their phone number is 1-800-862-7728 or 609-921-7500 and you should ask for group number 14120 or `Barriers workshop' to get the special workshop rate. We encourage you to reserve your room early since the hotel has limited space. DO NOT BOOK YOUR ROOM ONLINE! THE SPECIAL RATE IS ONLY AVAILABLE WHEN MAKING A RESERVATION BY PHONE.

Registration: Please use the form at the bottom of this page to register to the workshop. (Last minute registration is ok but please do not register on the last business day prior to the workshop).

Financial support: We have some limited funds to cover expenses of students attending the workshop. If you need such support please fill in the support request form at the bottom of this page. Once the workshop is over, you will also need to fill the following form: pu-expense-report. Guidelines for filling the expense report are available here. If you are being reimbursed by PU  please read the following airfare guidelines carefully. All flights must be booked with a US flagship carrier airlines in order to receive reimbursement for the expense. Ask your travel agent or airline customer service representative if your flight will qualify if in doubt.

Important: If the travel includes stops in addition to the workshop location, appropriate documentation including the fare comparison direct to/from the conference location at the time of purchase must be included with the request for reimbursement. Documentation/comparisons cannot be dated  after the trip dates.

While the initial deadline for applications for financial support has past, we will continue to consider applications for support subject to availability of resources.

The Center for Computational Intractability especially encourages the participation in our workshops of researchers from backgrounds that are  traditionally underrepresented within the computer science research community.

Local Information

There is a shuttle service you can reserve in advance called Olympic Airporter (ask for PU rate). A list of Princeton Taxis is available here. The Newark airport website should also have information regarding transportation. You can also click here for information for Princeton university visitors including driving directions and maps.

Parking for participants is in Lot 21 (see this map) with this pass (place on your dashboard). There is a university shuttle service that connects this parking lot with the workshop location. For timetables click here (look for the West and East Extension Lines summer schedule).

Contact

Questions regarding the scientific program should be directed to barriers.ws2@gmail.com .

For questions regarding local arrangements contact barriers2.local@gmail.com.

Registration for the workshop is now closed

Dec 11, 2009

Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size

Ankur Moitra, MIT

Abstract. Linial, London and Rabinovich and Aumann and Rabani proved that the min-cut max-flow ratio for general maximum concurrent flow problems (when there are $k$ commodities) is $O(\log k)$. This ratio is independent of the size of the graph, and only depends on the number of commodities. Here we attempt to derive a more general theory of Steiner cut and flow problems, and we prove bounds that are poly-logarithmic in $k$ for a much broader class of multicommodity flow and cut problems. Our structural results are motivated by the meta question: Suppose we are given a $poly(\log n)$ approximation algorithm, integrality gap or competitive ratio for a flow or cut problem -  when can we give a $poly(\log k)$ guarantee for a generalization of this problem to a Steiner cut or flow problem?

Thus we require that these guarantees be independent of the size of the graph, and only depend on the number of commodities (or the number of terminal nodes in a Steiner cut problem). For many natural applications (when $k = n^{o(1)}$) this yields much stronger guarantees.

We construct vertex-sparsifiers that approximately preserve the value of all terminal multicommodity flows. We prove such sparsifiers exist through zero-sum games and metric geometry, and we construct such sparsifiers through oblivious routing guarantees. These results let us reduce a broad class of multicommodity-type problems to a uniform case (on $k$ nodes) at the cost of a loss of a $poly(\log k)$ in the approximation guarantee. We then give $poly(\log k)$ approximation algorithms for a number of problems for which such results were previously unknown, such as requirement cut, l-multicut, oblivious $0$-extension, and natural generalizations of oblivious routing, min-cut linear arrangement and minimum linear arrangement.

Play video

 

Nov 13, 2009

QIP = PSPACE

John Watrous, University of Waterloo

Abstract. The interactive proof system model of computation is a cornerstone of complexity theory, and its quantum computational variant has been a topic of study in quantum complexity theory for the past decade. In this talk I will present an exact characterization of the expressive power of quantum interactive proof systems that I recently proved in collaboration with Rahul Jain, Zhengfeng Ji, and Sarvagya Upadhyay. The characterization states that QIP = PSPACE, or in other words that the collection of computational problems having quantum interactive proof systems consists precisely of those problems solvable in polynomial space with an ordinary classical Turing machine. This characterization implies the striking fact that quantum computing does not provide an increase in computational power over classical computing in the context of interactive proof systems.

 

October 30, 2009

Satisfiability Allows No Nontrivial Sparsification Unless The Polynomial-Time Hierarchy Collapses

Dieter van Melkebeek, University of Wisconsin Madison

Abstract. Consider the following two-player communication process to decide a language $latex L$: The first player holds the entire input $latex x$ but is polynomially bounded; the second player is computationally unbounded but does not know any part of $latex x$; their goal is to cooperatively decide whether $latex x$ belongs to $latex L$ at small cost, where the cost measure is the number of bits of communication from the first player to the second player.

For any integer $latex d \geq 3$ and positive real $latex \epsilon$ we show that if satisfiability for $latex n$-variable $latex d$-CNF formulas has a protocol of cost $latex O(n^{d-\epsilon})$ then coNP is in NP/poly, which implies that the polynomial-time hierarchy collapses to the third level. The result even holds for conondeterministic protocols, and is tight as there exists a trivial deterministic protocol for $latex \epsilon = 0$. Under the hypothesis that coNP is not in NP/poly, our result implies tight lower bounds for parameters of interest in several areas, including sparsification, kernelization in parameterized complexity, lossy compression, and probabilistically checkable proofs.

By reduction similar results hold for other NP-complete problems. For the vertex-cover problem on $latex n$-vertex $latex d$-uniform hypergraphs the above statement holds for any integer $latex d \geq 2$. The case $latex d=2$ implies that no NP-hard vertex deletion problem based on a hereditary graph property can have kernels consisting of $latex O(k^{2-\epsilon})$ edges unless coNP is in NP/poly, where $latex k$ denotes the size of the deletion set. Kernels consisting of $latex O(k^2)$ edges are known for several problems in the class, including vertex cover, bounded-degree deletion, and feedback vertex set.

Joint work with Holger Dell.

 

October 23rd, 2009

Towards Polynomial Lower Bounds for Dynamic Problems

Mihai Patrascu, AT&T Labs - Research

Abstract:

We formulate a conjecture about the hardness of a certain

data-structural version of set disjointness, and show that it implies

polynomial lower bounds for many central questions in data structures.

We then show that our conjecture follows from the widely-accepted

hypothesis on the hardness of 3SUM. Ours is the first non-algebraic

reduction from 3SUM, which is a development of independent interest.

We also describe how our conjecture could be proved unconditionally,

by analyzing a certain number-on-forehead communication game.

 

October 16th, 2009

On the Geometry of Differential Privacy

Moritz Hardt, Princeton University

Abstract:

We consider the noise complexity of differentially private mechanisms in the setting where the user asks d linear queries f:R^n->R non-adaptively. Here, the database is represented by a vector in R^n. Proximity between databases is measured in the l1-metric.

We show that the noise complexity is determined by two geometric parameters of a convex body associated with the set of queries. Using this connection we give tight upper and lower bounds on the noise complexity of random linear queries for any d

Quantitatively, our result shows that it is necessary and sufficient to add l2-error \Theta(min{d\sqrt{\log n},d\sqrt{d}}) to achieve differential privacy. The best previous upper bound (Laplacian mechanism) gives a bound of O(d\sqrt{d}), while the best known lower bound was \Omega(d). In contrast, our lower bound is strong enough to separate differential privacy from the notion of approximate differential privacy where an upper bound of O(d) can be achieved.

Joint work with Kunal Talwar.

 

 

 

Thanks to everybody who attended the workshop!

We all had a great time.

Slides for Milind Sohoni's talk are available here. [Video]

Slides for Peter Burgisser's talk are available here. [Video]

Slides for K. V. Subrahmanyam's talk are available here. [Video]

Slides for Bharat Adsul's talk are available here. [Video]

Slides for Hari Narayanan's talk are available here. [Video]

Slides for Christian Ikenmeyer's talk are available here. [Video]

Videos for Ketan Mulmuley's talks (we sincerely apologize for the typo in Ketan's name): [Talk1] [Talk2] [Talk3] [Talk4] [Talk5] [Talk6] [Talk7] [Talk8] [Talk9]

---

The center (co-sponsored with DIMACS) will host a workshop on Gemetric Complexity Theory (GCT), an approach to the P vs. NP and related problems through algebraic geometry and representation theory. The workshop will be organized by Peter Burgisser, Ketan Mulmuley, Milind Sohoni and K.V. Subrahmanyam. There will be a short course on basic GCT on the first two days of the workshop and a few talks on the third day.

Registration for the workshop is free, but it is strongly recommended that the people should register before March 15. The registration form is at the bottom of this post. Some travel money is available for students. Students should use the form below to request support.

All talks will take place in  Friends Center, Room 006. The Friends center is adjacent to the computer science department, Princeton University. Its location is shown in the campus map.

Schedule: The workshop schedule is available here.

Local information: If you plan to come to the workshop and need a hotel room, we suggest you register and reserve a room at the Nassau Inn . The special  rate for the workshop 132.00 per night plus taxes. Call 1-800-862-7728 to make your reservation. Ask for group number 14019 or GCT workshop room block. The cutoff date is 6/4/2010. In addition to the Nassau Inn some modest dorm accommodation ($47.75 per person per night, two in a room) will be available. Interested participants should indicate in the registration form what form of accommodation they prefer: hotel (Nassau Inn), dorm, or none (on their own).  The dorms are located at Wilf Hall in the butler complex (see campus map).

Driving and Parking information. Visitors coming to campus on weekdays from 8 am to 5 pm may park in Lot 21 near Jadwin Gymnasium.  Place this parking pass on your dashboard. The location of Lot 21 can be found in the campus map above.

Newark airport is the closest to Princeton. See this site to help with travel questions including cost estimates.

Use this link to make reservations to an airport shuttle with Princeton University discount.

Financial support

We have some limited funds to cover participants cost, if you need such support please contact the organizers. You'll also need to use the following forms: pu-expense-reports1 pu-expense-report. If you are being reimbursed by PU  please read the following guidelines carefully. All flights must be booked with a US flagship carrier airlines in order to receive reimbursement for the expense. Ask your travel agent or airline customer service representative if your flight will qualify if in doubt.

The Center for Computational Intractability especially encourages the participation in our workshops of researchers from backgrounds that are  traditionally underrepresented within the computer science research community.

Contact

Questions regarding the scientific program should be directed to gct.workshop@gmail.com. For questions regarding local arrangements contact gct.local@gmail.com.

The last meeting for the intractability center this calendar

year will be held on December 4.

We shall start the day in room 405, and then move to the small auditorium when it is available,

for the two afternoon talks.

In room 405:

10:00 - 10:35 :   PI meeting

10:45 - 12:00 :   Umesh Vazirani (On Hastings' Proof of the Area Law) Watch online: Part 1, Part 2

12:00 -   2:15 :   Lunch + Collaboration Time

In small auditorium:

3:15 - 3:40 : Approximation Resistance,  Per Austrin Watch online

3:40 - 4:05 : Local Embeddings,  Ofer Neiman Watch online

 

Abstract for Vazirani talk:  Hamiltonian complexity is an emerging area that bridges quantum complexity theory and condensed matter physics. The main focus of study in this area are properties of ground states of local Hamiltonians, which are the quantum analog of constraint satisfaction problems. In this talk I will give a simplified exposition of Matt Hastings' celebrated area law for 1-Dim systems with local Hamiltonians. The exposition is based on the quantum detectability lemma and is joint work with Aharonov, Arad and Landau.

Click here for registration form

Monday Nov.2

09:15-10:00 - Breakfast

10:00-10:30 - Devavrat Shah, "Belief Propagation and Combinatorial Optimization"

10:30-11:00 - Jorge Cortes, "Distributed wombling by robotic sensor networks"

11:00-11:30 - Break

11:30-12:00 - Leah Edelstein-Keshet,  "Group constraints on foraging" video

12:00-12:30 - Tanya Berger-Wolf, "Finding structure in dynamic social networks" video

12:30-2:00 Lunch

2:00-2:30 - Magnus Egerstedt, "Cooperative Foraging Among Bottlenose Dolphins and Engineered Systems" video

2:30-3:00 - Julien Hendrickx, "Distributed deterministic computation of functions in anonymous networks" video

3:00-3:30 - Break

3:30-4:00 - Ali Jadbabaie, "From Consensus to Social Learning in Complex Networks" video

4:00-4:30 - Herbert G. Tanner, "Coordination in heterogeneous multi-agent teams: exploiting diversity" video

7:00 - Banquet (Palmer House)

Tuesday Nov.3

09:15-10:00 - Breakfast

10:00-10:30 - Ryan Lukeman, "Inferring individual rules from a field study of collective behaviour" video

10:30-11:00 - Naomi Leonard, "Robustness of collective decision dynamics for directed sensing topologies" video

11:00-11:30 - Break

11:30-12:00 - Joel Lebowitz, "Statistical Mechanics and Emergent Phenomena in Systems of Many Interacting Components" video

12:00-12:30 - A. Stephen Morse, "Convergence Rates for Deterministic Gossip Sequences" video

12:30-2:00 Lunch

2:00-2:30 - John Tsitsiklis, "Distributed consensus and averaging" video

2:30-3:00 - Vijay Kumar, "Collective Behaviors for Micro Bio Robots" video

3:00-3:15 - Break

3:15-4:30 - Brief presentation (B. Chazelle), followed by panel discussion video of Bernard Chazelle's presentation video of panel discussion

Click here for the workshop's homepage

This is a tentative program and subject to change.

Barriers in Computational Complexity workshop

Click here for PDF version of program.

Talks are in Room 101 in the Friend Center auditorium, lunch is located in the Friend center convocation room (room 113). Breakout rooms available are Friend 004 and 006.

Wireless networks: use either SSID "csvapornet" or SSID "puvisitor"

Tue, Aug 25: Boolean complexity

Organizers: Scott Aaronson, Alexander Razborov

08:00 Breakfast

09:30 - 10:20 : Alexander Razborov, Somewhat Impartial Survey of Results in Circuit Complexity alexander_razborov_slides hi-res video low-res video

10:30 - 11:20 : Scott Aaronson, Has There Been Progress on the P vs. NP Question? scott_aaronson_slides hi-res video low-res video

NP and reality P vs NP independent? Fortnow survey Sipser survey Sipser video Quantum adiabatic 1 Quantum adiabatic 2 solution space of k-sat

11:20 – 11:40 Break

11:40 – 12:30 : Benjamin Rossman, The monotone complexity of k-clique on random graphs ben_rossman_slides

12:30 - 14:30 Lunch

14:30 - 15:20 : Ketan Mulmuley, On P vs. NP, Geometric Complexity Theory, Explicit Proofs and the Complexity Barrier ketan_mulmuley_slides hi-res video low-res video

all papers available from Mulmuley's homepage see also videos of IAS lectures

15:20 - 17:00 Break

17:00 - 18:00 : Panel discussion, moderated by Scott Aaronson hi-res video low-res video

Wed, Aug 26: Arithmetic computation

Organizers: Ran Raz, Amir Shpilka.

08:00 Breakfast

09:30 - 11:20 : Amir Shpilka: A (biased) survey of arithmetic circuits amir_shpilka_slides hi-res video low-res video

11:20 – 11:40 Break

11:40 – 12:30 : Amir Yehudayoff: On the structure of arithmetic circuits, with applications amir_yehoudayoff_slides hi-res video low-res video

12:30 - 14:30: Lunch

14:30 - 15:20 : Chris Umans: Group-theoretic algorithms for matrix Multiplication chris_umans_slides hi-res video low-res video

paper 1 paper 2

15:40 - 16:30 : Ran Raz: How to fool people to work on circuit lower bounds ran_raz_slides hi-res video low-res video

16:30 – 17:00 Break

17:00 - 18:00 : Rump Session + Open Problems hi-res video low-res video

18:30 – 21:00: Workshop Banquet, Palmer House

Thu, Aug 27: Proof complexity

Organizers: Toni Pitassi, Pavel Pudlak

8:00 Breakfast

09:00 - 09:45 Steve Cook, Branching Programs: Avoiding Barriers steve_cook_slides hi-res video low-res video

09:50 - 10:35 Pavel Pudlak, Proof complexity of search problems. pavel_pudlak_slides hi-res video low-res video

10:35-10:50 Break 10:50 - 11:35 Toniann Pitassi, Hardness Amplification in Proof Complexity tonnian_pitassi_slides hi-res video low-res video

11:40 - 12:25 Jan Krajicek, Hard Tautologies jan_krajicek_slides hi-res video low-res video

12:30- 14:00 Lunch

14:00 - 14:45 Russell Impagliazzo, An Axiomatic Approach to Algebrization (overheads talk) hi-res video low-res video

14:45 – 15:00 Break

15:00 – 16:15 Short talks (25 minutes each)

Rahul Santhanam, Effective Polynomial Simulations rahul_santhanam_slides hi-res video low-res video

Jacob Nordstrom, Understanding Space in Proof Complexity: Separations and Tradeoffs via Substitutions jacob_nordstrom_slides hi-res video low-res video

Neil Thapen, TBA

16:15 - 16:30 Break

16:30 - 17:45 Short talks (25 minutes each

Iddo Tzamaret, Proofs of polynomial identities iddo_tzameret_slides hi-res video low-res video

paper

Emil Jarabek, On monotone sequent calculus emil_jerabek_slides hi-res video low-res video

17:45 – 20:30 Dinner

20:30 – 21:30 Panel Discussion, Will proof complexity help to solve P vs. NP?"

Sam Buss (moderator)

Steve Cook

Paul Beame

Alasdair Urquhart

Fri, Aug 28: Computational Learning theory

Organiziers: Avrim Blum, Rocco Servedio

08:00 Breakfast

09:20 – 09:30 Opening remarks

9:30 – 10:20: Tong Zhang, Computation and Optimization in Machine Learning tong_zhang_slides hi-res video low-res video

10:30 – 11:20 Nina Balcan, Approximate Clustering without the Approximation nina_balcan_slides hi-res video low-res video

approx clustering low error clustering agnostic clustering sparsest cut clustering clustering framework

11:20 – 11: 40 Break

11:40 – 12:30 Adam Kalai, Learning and Smoothed Analysis adam_kalai_slides hi-res video low-res video

12:30 Lunch break

14:30 – 15:20 John Langford, Getting around Barriers in Learning Theory john_langford_slides hi-res video low-res video

15:30 - 16:20 Adam Klivans, Learning, Polynomials, and Circuit Lower Bounds adam_klivans_slides hi-res video low-res video

16:20 – 16:40 Break

16:40 – 18:00 Discussion hi-res video low-res video

Sat, Aug 29: Pseudorandomness & Derandomization

Organizers: Valentine Kabanets, Luca Trevisan

08:00 Breakfast

09:15 -10:00 Mark Braverman: Polylog-wise Independence Fools AC0 (blackboard talk) hi-res video low-res video

paper

10:15 -11:00 Valentine Kabanets: Derandomization vs. Circuit Lower Bounds valentine_kabanets_slides hi-res video low-res video

11:00 – 11:15 Break

11:15 -12:00 Omer Reingold: Randomness vs. Memory: Prospects and Barriers omer_reingold_slides hi-res video low-res video

12:00 - 14:00 Lunch

14:00 -14:45 Luca Trevisan: Pseudorandomness in Additive Combinatorics luca_trevisan_slides hi-res video low-res video

14:45 - 15:15 Break

End of program

Some abstracts Ketan Mulmuley

Title: On P vs. NP, Geometric Complexity

Theory, Explicit Proofs and the Complexity Barrier

Abstract:

This talk will give its informal overview of the complexity barrier and its role in geometric complexity theory (GCT), an approach to the P vs. NP and related problems. The relevant paper (with the same title as the talk) is available on the web at the speaker's personal home page.

---------------------------

Tong Zhang

Title: Computation and Optimization in Machine Learning

Abstract: Many problems in statistical machine learning involve non-convex objective functions that are difficult to optimize. A frequently employed approach is to solve a convex approximation (or relaxation) of the original problem, which raises the question about the quality of such relaxation methods. That is, whether the solution of an approximation is close to the solution of the original problem. A different approach is to use traditional numerical optimization procedures that directly find a local minimum of the nonconvex problem. Again, an important question is the quality of the local minimum being found.

I will discuss some recent results for both approaches as well as some future directions. In the first part, I will discuss convex relaxation methods, and the emphasis is on the effectiveness of convex relaxation. The second part discusses local optimization methods; again, the emphasis is the on effectiveness of such procedures.

Adam Kalai

Title: Learning and Smoothed Analysis

Abstract:

We give a new model of learning motivated by smoothed analysis (Spielman and Teng, 2001). In this model, we analyze two new algorithms, for PAC-learning DNFs and agnostically learning decision trees, from random examples drawn from a constant-bounded product distributions. These two problems had previously been solved using membership queries (Jackson, 1995; Gopalan et al, 2005). Our analysis demonstrates that the "heavy" Fourier coefficients of a DNF alone suffice to recover the DNF. We also show that a structural property of the Fourier spectrum of any boolean function holds over "typical" product distributions.

Joint work with Alex Samorodnitsky and Shang-Hua Teng

--------------------------

Adam Klivans

Title: Learning, Polynomials, and Circuit Lower Bounds.

Abstract:

In 1989, Linial, Mansour, and Nisan pioneered the "Fourier method" in computational learning theory by reducing the problem of uniform-distribution learning to the problem of approximating concept classes by real polynomials. Additionally, they gave applications to proving circuit lower bounds for constant depth circuits. In this two-part talk, I will continue these themes and describe 1) how real approximation theory is still a fundamental problem in learning theory (in particular, by examining the complexity of empirical risk minimization over R^n) and 2) why-- in a precise sense-- learning algorithms actually imply circuit lower bounds.

--------------------------

Maria-Florina Balcan

Title: Approximate Clustering without the Approximation

Abstract:

There has been substantial work on approximation algorithms for clustering

data under distance-based objective functions such as k-median, k-means,

and min-sum objectives. This work is fueled in part by the hope that

approximating these objectives well will indeed yield more accurate

solutions. That is, for problems such as clustering proteins by function,

or clustering images by subject, there is some unknown correct "target"

clustering and the implicit assumption is that clusterings that are

approximately optimal in terms of these distance-based measures are also

approximately correct in terms of error with respect to the target. In

this work we show that if we make this implicit assumption explicit ---

that is, if we assume that any c-approximation to the given clustering

objective Phi is epsilon-close to the target --- then we can produce

clusterings that are O(epsilon)-close to the target, even for values c for

which obtaining a c-approximation is NP-hard. In particular, for the

k-median, k-means, and min-sum objectives, we show that we can achieve

this guarantee for any constant c > 1.

Our results show how by explicitly considering the alignment between the

objective function used and the true underlying clustering goals, one can

bypass computational barriers and perform as if these objectives were

computationally substantially easier.

--------------------------

John Langford

Title: Getting around Barriers in Learning Theory

Abstract:

This talk is about a collection of examples where a barrier in learning theory has fallen, how it fell, and some discussion about how we can get around remaining barriers. I plan to discuss and compare problems in sample complexity, computational complexity, and complex learning problems.

--------------------------

Tentative program for the workshop on

"Complexity and Cryptography: Status of Impagliazzo's Worlds"

June 3-5, Princeton

Talks are in Room 006 in the Friend center , lunch and rump session in convocation room of Friend center, banquet is in Palmer House.

Parking: You can park in lots 3 and 21 using this permit, see  campus map . There are also metered parking spots on Olden St and Propspect Ave.

Below are streaming versions of videos, you can also download them via this link

Wednesday June 3rd.

10:30           Breakfast, coffee etc...
11:15-11:30 Opening words
11:30-12:30  Russell Impagliazzo: 5 worlds of problems hi-res video
12:30-2:30    Lunch
2:30-3:30      Chris Peikert: Public-Key Cryptosystems from the Worst-Case Shortest Vector Problem
 hi-res video  slides
3:30-4          Coffee break
4-5               Craig Gentry: A Homomorphic Public Key Cryptosystem hi-res video

6-9pm          Banquet at Palmer House

Thursday, June 4th.

9                Breakfast, coffee etc..
9:30-10:30  Iftach Haitner: Inaccessible Entropy hi-res video slides
10:30-11     Coffee break
11-12          Luca Trevisan: On Algorithmica vs Heuristica
12-1:30       Lunch
1:30-2:30    Dimitris Achlioptas: Algorithmic Phase Transitions in Constraint Satisfaction Problems hi-res video slides
2:30-3:30    Uri Feige: Dense subgraphs of random graphs hi-res video
3:30-4         Coffee Break
4-5             Benny Applebaum: Cryptography from Average-Case Hardness hi-res video  slides

Dinner on your own.

7-9pm        Rump/open problems  session schedule

slides:
Dodis Goyal Vadhan Ostrovski Naor Mahmoody-Ghidary Chung Prabhakaran Trevisan Haitner Wee Rothblum Gordon Viola Xiao Peikert Barak

Friday, June 5th.

9                Breakfast, coffee etc..
9:30-10:30  Scott Aaronson:  Impagliazzo's Worlds in Arithmetic Complexity hi-res video slides
10:30-11     Coffee break
11-12         Valentine Kabanets: Direct Product Testing hi-res video slides
12-1:30      Lunch
1:30-2:30   Moni Naor: How Fair Can a Coin Toss Be? hi-res video
2:30-3:30   Yuval Ishai:  Efficiency vs. assumptions in secure computation hi-res video slides
3:30-4       Coffee break
4-5            Amit Sahai: A New Protocol Compiler hi-res video  slides (keynote)

Abstracts

Russell Impagliazzo : Five Worlds of Problems

``A personal view on average-case complexity'' introduced five possible worlds as
metaphors for the outcomes of  fundamental questions in complexity concerning
whether and to what extent intractable problems exist.
In this talk, I will try to put forward some concrete open problems addressing these issues.
I will emphasize those problems I believe are both within reach,
in that there is no fundamental reason they should be difficult, but whose solutions
would cast light on which of the five worlds is the case and what these worlds look like.

Chris Peikert: Public-Key Cryptosystems Based from the Worst-Case Shortest Vector Problem

We construct public-key cryptosystems that are secure assuming the
worst-case hardness of approximating the minimum distance on
$n$-dimensional lattices to within small poly(n) factors.  Prior
cryptosystems with worst-case connections were based either on the
shortest vector problem for a *special class* of lattices (Ajtai and
Dwork, STOC 1997; Regev, J.~ACM 2004), or on the conjectured hardness
of lattice problems for *quantum* algorithms (Regev, STOC 2005).

Our main technical innovation is a reduction from variants of the
shortest vector problem to corresponding versions of the ``learning
with errors'' problem; previously, only a quantum reduction of this
kind was known.  As an additional contribution, we construct a natural
*chosen ciphertext-secure* cryptosystem having a much simpler
description and tighter underlying worst-case approximation factor
than prior schemes.

 Craig Gentry: A Homomorphic Public Key Cryptosystem

We propose a fully homomorphic encryption scheme – i.e., a scheme that
allows one to evaluate circuits over encrypted data without being able
to decrypt. Our solution comes in three steps. First, we provide a
general result – that, to construct an encryption scheme that permits
evaluation of arbitrary circuits, it suffices to construct an encryption
scheme that can evaluate (slightly augmented versions of) its own
decryption circuit; we call a scheme that can evaluate its (augmented)
decryption circuit bootstrappable.

Next, we describe a public key encryption scheme using ideal lattices
that is almost bootstrappable. Lattice-based cryptosystems typically
have decryption algorithms with low circuit complexity, often dominated
by an inner product computation that is in NC1. Also, ideal lattices
provide both additive and multiplicative homomorphisms (modulo a
public-key ideal in a polynomial ring that is represented as a lattice),
as needed to evaluate general circuits.

Unfortunately, our initial scheme is not quite bootstrappable – i.e.,
the depth that the scheme can correctly evaluate can be logarithmic in
the lattice dimension, just like the depth of the decryption circuit,
but the latter is greater than the former. In the final step, we show
how to modify the scheme to reduce the depth of the decryption circuit,
and thereby obtain a bootstrappable encryption scheme, without reducing
the depth that the scheme can evaluate. Abstractly, we accomplish this
by enabling the encrypter to start the decryption process, leaving less
work for the decrypter, much like the server leaves less work for
decrypter in a server-aided cryptosystem.

Iftach Haitner: Inaccessible Entropy

We put forth a new computational notion of entropy, which measures the
(in)feasibility of sampling high entropy strings that are consistent
with a given protocol.  Specifically, we say that the i'th round of a
protocol (A, B) has _accessible entropy_ at most k, if no
polynomial-time strategy A^* can generate messages for A such that the
entropy of its message in the i'th round has entropy greater than k
when conditioned both on prior messages of the protocol and on prior
coin tosses of A^*.  We say that the protocol has _inaccessible entropy_
if the total accessible entropy (summed over the rounds) is noticeably
smaller than the real entropy of A's messages, conditioned only on
prior messages (but not the coin tosses of A).  As applications of
this notion, we

* Give a much simpler and more efficient construction of statistically
hiding commitment schemes from arbitrary one-way functions.

* Prove that constant-round statistically hiding commitments are
necessary for constructing constant-round zero-knowledge proof systems
for NP that remain secure under parallel composition (assuming the
existence of one-way functions).

Luca Trevisan: On Algorithmica vs Heuristica

Dimitris Achlioptas: Algorithmic Phase Transitions in Constraint Satisfaction Problems

For many Constraint Satisfaction Problems by now we have a good
understanding of the largest constraint density for which solutions
exist. At the same time, though, all known polynomial-time algorithms
for these problems stop finding solutions at much smaller densities. We
study this phenomenon by examining how the different sets of solutions
evolve as constraints are added. We prove in a precise mathematical
sense that, for each problem studied, the barrier faced by algorithms
corresponds to a phase transition in that problem’s solution-space
geometry. Roughly speaking, at some problem-specific critical density,
the set of solutions shatters and goes from being a single giant ball
to exponentially many, well-separated, tiny pieces. All known
polynomial-time algorithms work in the ball regime, but stop as soon as
the shattering occurs. Besides giving a geometric view of the solution
space of random CSPs our results provide novel constructions of one-way functions.

Joint work with Amin Coja-Oghlan.

Uri Feige: Dense subgraphs of random graphs

 see pdf file

Benny Applebaum: Cryptography from Average-Case Hardness 

We construct a public key cryptosystem based on the assumption that
it is hard to solve n^{1.41} random 3-sparse equations modulo 2 in n
variables, where an n^{-0.2} fraction of the equations are noisy.

This assumption seems different than previous assumptions used to
construct public key systems. In particular, to our knowledge, it is the
first noisy equations type public key system with noise magnitude larger
than 1/sqrt{n}. We also show that our assumption is not refuted
by certain natural algorithms such as Lassere SDP's, low-degree polynomials and ACO circuits,
and, using Feige's 3XOR Principle, that the refutation variant of
this assumption with the same parameters is implied by the hardness
of refuting random 3CNFs with O(n^{1.41}) clauses.

We also construct a public key cryptosystem based on the hardness o
the above problem with fewer equations- as low as c*n for a large
constant c - at the expense of making an additional assumption about
a planted dense subgraph problem in random 3-uniform hypergraphs.

Joint work with Boaz Barak and Avi Wigderson.

Scott Aaronson:  Impagliazzo's Worlds in Arithmetic Complexity

In this talk, I'll examine Impagliazzo’s worlds through the "funhouse
mirror" of arithmetic computation over finite fields.  The motivation
is not only to gain insight into the ordinary Boolean worlds, but also
to create a Natural Proofs theory for arithmetic circuits, which would
explain our failure to prove superpolynomial lower bounds for the
Permanent.  I'll prove two main results.  Firstly, in a reasonable
model of arithmetic computation over "small" finite fields F---where
"small" means |F|<=2^poly(n)---one-way functions, pseudorandom
generators, and pseudorandom functions exist if and only if they exist
in the ordinary Boolean world.  The proof uses a shifted quadratic
character problem due to Boneh and Lipton as a "bridge" between the
Boolean and arithmetic worlds.  Secondly, over "large" finite fields
F—where "large" means |F|>2^poly(n)---there's a meaningful sense in
which "P!=NP implies the existence of one-way functions": that is,
Heuristica, Pessiland, and Minicrypt all collapse to a single world.
I'll end by speculating about the possibility of a Natural Proofs
theory for low-degree arithmetic circuits, and proposing a concrete
candidate for a low-degree arithmetic pseudorandom function.

Joint work with Andrew Drucker

Valentine Kabanets: Direct Product Testing

Moni Naor: How Fair Can a Coin Toss Be?

Coin-flipping protocols allow mutually distrustful parties to
generate a common unbiased random bit, guaranteeing that even if
one of the parties is malicious, it cannot significantly bias the
output of the honest party.

A classical result by Cleve from STOC 1986 showed that without
simultaneous broadcast, for any two-party coin-flipping protocol
with r rounds, there exists an efficient adversary that can bias
the output of the honest party by Omega(1/r). However, the best
previously known protocol only guarantees O(1/sqrt(r)) (based on
Blum's protocol) and Cleve and Impagliazzo have shown that this is
optimal in the fail-stop model (where the adversary is limited to
early stopping but has unbounded computational power).

We establish the optimal tradeoff between the round complexity and
the maximal bias of two-party coin-flipping protocols. Under
standard assumptions, we show that Cleve's lower bound is tight:
we construct an r-round protocol with bias O(1/r). We make use of
recent progress by Gordon, Hazay, Katz and Lindell regarding fair
protocols (STOC 2008).

Unlike Blum's coin flipping protocol that requires only the
existence of any one-way function, our protocol (like the Protocol
of Gordon et al) requires "cryptomania" style assumptions. One of
the main interesting questions is whether this is essential.

Joint work with Tal Moran and Gil Segev

Yuval Ishai:  Efficiency vs. assumptions in secure computation

The talk will survey the state of the art in the complexity of secure computation, highlight
connections with the topics of the workshop, and discuss the role of
nonstandard assumptions in some of the current frontiers.

Amit Sahai: A New Protocol Compiler

One of the most fundamental goals in cryptography is to design
protocols that remain secure when adversarial participants can engage
in arbitrary malicious behavior.  In 1986, Goldreich, Micali, and
Wigderson presented a powerful paradigm for designing such protocols:
their approach reduced the task of designing secure protocols to
designing protocols that only guarantee security against
"honest-but-curious" participants. By making use of zero-knowledge
proofs, the GMW paradigm enforces honest behavior without compromising
secrecy.  Over the past two decades, this approach has been the
dominant paradigm for cryptographic protocol design.

In this talk, we present a new general paradigm / protocol compiler
for secure protocol design. Our approach also reduces the task of
designing secure protocols to designing protocols that only guarantee
security against honest-but-curious participants.  However, our
approach avoids the use of zero-knowledge proofs, and instead makes
use of multi-party protocols in a much simpler setting - where the
majority of participants are completely honest (such multi-party
protocols can exist without requiring any computational assumptions).

Our paradigm yields protocols that rely on Oblivious Transfer (OT) as
a building block.  This offers a number of advantages in generality
and efficiency.

In contrast to the GMW paradigm, by avoiding the use of zero-knowledge
proofs, our paradigm is able to treat all of its building blocks as
"black boxes". This allows us to improve over previous results in the
area of secure computation. In particular, we obtain:

* Conceptually simpler and more efficient ways for basing
unconditionally secure cryptography on OT.

* More efficient protocols for generating a large number of OTs using
a small number of OTs.

* Secure and efficient protocols which only make a black-box use of
cryptographic primitives or underlying algebraic structures in
settings where no such protocols were known before.

This talk is based primarily on joint works with Yuval Ishai
(Technion and UCLA) and Manoj Prabhakaran (UIUC).

EIGHTH INTRACTABILITY CENTER MONTHLY MEETING
Friday May 1, 2009, CS Dept, Princeton U.

10:15 - 10:45  Coffee and PI Meeting

10:45 - 11:30  Ryan Williams, "Triangle Detection Versus Matrix Multiplication"
               video: hi-res low-res

11:30 - 11:45  Announcements

11:45 - 12:30  Thomas Holenstein, "XOR Lemma and pseudorandom number
generators from one-way functions" (joint work with Grant Schoenebeck)

12:30 - 1:30    Lunch

1:30 - 2:15    Anup Rao, "2-Source Extractors under Computational Assumptions
and Cryptography with defective Randomness"  video: hi-res low-res

2:15 -         Open time for informal collaboration

SEVENTH  INTRACTABILITY CENTER MONTHLY MEETING
Friday March 27, 2009, CS Dept, Princeton U.

10:00 - 10:45  Pavel Hrubes and Amir Yehudayoff, joint presentation,
               "Towards lower bounds on non-commutative arithmetic circuits"
               (joint work with Avi Wigderson)
               video: hi-res low-res

10:45 - 11:00  Announcements

11:00 - 12:00  Umesh Vazirani
               video: hi-res low-res

12:00 - 1:00   Lunch  (Lunch can continue past 1 for non-PI's)

1:00 - 3:00    Open time for informal collaboration / PI meeting

3:00 - 3:30    Gabor Kun, ``An analytic approach to the Dichotomy Conjecture''
               (joint work with Mario Szegedy)
               video: hi-res low-res

3:30 - 4:00    Mohammad Bateni
               video: hi-res low-res

SIXTH  INTRACTABILITY CENTER MONTHLY MEETING
Friday January 30, 2009, CS Dept, Princeton U.

10:00-10:30   PI meeting

10:30-11:30   Eddie Farhi  "A quantum computer can determine who wins a game faster than a
classical computer." (Abstract below)
video: part 1 part 2

11:30-12:30   Scott Aaronson  "On BQP Versus the Polynomial Hierarchy."
(Abstract below)
video: part 1 part 2

12:30-12:45   Announcements

12:45-2:00    Lunch

2:00-3:00     Breakout sessions

ABSTRACTS

"A quantum computer can determine who wins a game faster than a classical computer."

Imagine a game where two players go back and forth making moves and at
the end of a fixed number of moves the position is either a win or a
loss for the first player.  In this case, if both players play best
possible, it is determined at the first move who wins or loses.  To
figure out who will be the winner you need not look at all of the N
final positions but only at N0.753.  I will show that with a quantum
computer the exponent can be reduced to 0.5.  The technique involves
quantum scattering theory and illustrates how ideas from physics can
be used to design quantum algorithms that outperform even best
possible classical algorithms.

On BQP Versus the Polynomial Hierarchy
Scott Aaronson (MIT)

The relationship between BQP (quantum polynomial time) and the
polynomial hierarchy has been one of the central mysteries of quantum
computing since 1993, with even an oracle separation remaining
elusive.  In this talk I'll do three things:

(1) Show that there exists a "relational" oracle problem in BQP but not in PH.

(2) Describe Mark Braverman's spectacular recent proof of the
Linial-Nisan Conjecture, that polylog-wise independence fools AC0
circuits.

(3) Show how a "small" extension of Braverman's result would finally
give us an oracle relative to which BQP is not in PH.

video: hi-res low-res

Title: A computational theory of clustering

Speaker: Avrim Blum, CMU

Abstract:

Problems of clustering data come up in many different areas throughout

science. Theoretical treatments of clustering have generally been of

two types: either on algorithms for (approximately) optimizing various

distance-based objectives such as k-median, k-means, and min-sum, or

on clustering under probabilistic "generative model" assumptions such

as mixtures of Gaussian or related distributions.

In this work we propose a new approach to analyzing the problem of

clustering. Building on models used in learning theory, we consider

the goal of approximately recovering an unknown target clustering from

a given similarity matrix (weighted graph), without making

generative-model assumptions about the data. Instead, we ask: what

relations between the similarity information and the desired

clustering are sufficient to cluster well -- these relations taking

the role of the "concept class" in learning theory. We find that if

we are willing to relax our goals a bit (for example, allow the

algorithm to produce a hierarchical clustering that we will call

successful if it contains a pruning that is close to the correct

answer) then this leads to a number of interesting graph-theoretic and

game-theoretic properties that are sufficient to cluster well. We

show we can also produce accurate clusterings under implicit

assumptions made when considering approximation algorithms for

distance-based objectives such as k-median, k-means, and min-sum. In

fact, we can do as well as if we had been able to approximate such

objectives to values that are NP-hard to achieve.

This talk is based on work joint with Maria-Florina Balcan, Anupam

Gupta, and Santosh Vempala.

 

 

video: hi-res low-res

Title: Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors.

Speaker: Amir Yehudayoff, IAS

Abstract:

In this paper we study multilinear formulas, monotone arithmetic circuits, maximal partition discrepancy, best partition communication complexity and mixed two source extractors.

In the talk we will focus on proving a tight exponential lower bound for the size of monotone arithmetic circuits. We will show how it is related to best partition discrepancy, and to multilinear formulas. We will also discuss shortly the connection to best partition communication complexity and mixed two source extractors.

This is joint work with Ran Raz.

video: hi-res low-res Title: The truth about quantum computers. Speaker: Umesh Vazirani, UC Berkeley Abstract: Popular articles on quantum computers sometimes portray them as mythical devices that speed up any computation by an exponential factor. The truth is much more subtle, and over the last decade and a half we have learned a great deal about the circumstances under which Nature allows us access to its exponential computational resources. This has a bearing on our understanding of the foundations of both computer science and quantum physics. In this talk I will try to outline some of these issues. No background in quantum physics will be assumed.

video: hi-res low-res Title: Noise Tolerance of Expanders and Sublinear Expander Reconstruction Speaker: Satyen Kale, MSR New England Abstract: We consider the problem of online sublinear expander reconstruction and its relation to random walks in "noisy" expanders. Given access to an adjacency list representation of a bounded-degree graph G, we want to convert this graph into a bounded-degree expander G' changing G as little as possible. The graph G' will be output by a distributed filter: this is a sublinear time procedure that given a query vertex, outputs all its neighbors in G', and can do so even in a distributed manner, ensuring consistency in all the answers. One of the main tools in our analysis is a result on the behavior of random walks in graph that are almost expanders: graphs that are formed by arbitrarily connecting a small unknown graph (the noise) to a large expander. We show that a random walk from almost any vertex in the expander part will have fast mixing properties, in the general setting of irreducible finite Markov chains. We also design sublinear time procedures to distinguish vertices of the expander part from those in the noise part, and use this procedure in the reconstruction algorithm. This is joint work with Yuval Peres and C. Seshadhri.

video: hi-res low-res Title: Games in Networks: the price of anarchy and learning Abstract: Network games play a fundamental role in understanding behavior in many domains, ranging from communication networks through markets to social networks. Such networks are used, and also evolve due to selfish behavior of the users and owners. In light of these competing forces, it is surprising how efficient these networks are. It is an exciting challenge to understand the operation and success of these networks in game theoretic terms: what principles of interaction lead selfish participants to form such efficient networks? We will focus on congestion games, and study the degradation of quality of solution caused by the selfish behavior of users. We model users as learning algorithms, and show that natural learning behavior can avoid bad outcomes predicted by the price of anarchy in atomic congestion games such as the load-balancing game. We use tools from the theory of dynamical systems and algebraic geometry to show when players use a class of natural learning algorithms the distribution of play converges to the set of weakly stable equilibria, and that the set of weakly stable equilibria are the pure Nash equilibria with probability 1 when congestion costs are selected at random independently on each edge (from any monotonically parametrized distribution). The talk is a survey and self-contained. ----- About the speaker: Eva Tardos is a Professor of Computer Science at Cornell University where she is currently chair. Her research is in Algorithm Design and Algorithmic Game Theory. Algorithmic game theory is an emerging new area of designing systems and algorithms for selfish users. She is a winner of the Fulkerson Prize and the Dantzig Prize.

FOURTH INTRACTABILITY CENTER MONTHLY MEETING Friday December 12, 2008, CS Dept, Princeton U. 10:00-10:30 PI meeting 10:30-11:00 Sanjeev Arora: "Efficient algorithms to compute SDPs and convex programs" (video: hires lowres) 11:00-11:30 Subhash Khot: "Unique games and SDP integrality gap" (video: hires lowres) 11:30-12:00 Michael Saks: "SDP and quantum computing" (video: hires lowres) 12:00-12:30 Open problems and announcements 12:30-1:30 Eva Tardos: TBA   (& lunch) (video: hires lowres) 1:30-2:30 Breakout sessions

THIRD INTRACTABILITY CENTER MONTHLY MEETING

Friday November 7, 2008, CS Dept, Princeton U [...]

10:00-10:30

Private PI meeting + Coffee for all

10:30-11:00

Adi Akavia: "Deterministically and Locally Finding Significant Fourier Transform Coefficients"

videos: hi-res, low-res, (older version)

11:00-11:30

Virginia Vassilevska: " Matrix Products and All Pairs Path Problems"

videos: hi-res, low-res, (older version)

11:30-Noon

Open problems and announcements

Noon-1:00

Lunch

1:00-2:00

Breakout sessions

2:00-3:30

Sanjeev Arora and Moses Charikar: "Semidefinite programming and approximation algorithms: a survey."

hi-res video: part 1 part 2, low-res video: part 1 part 2 (older version: part 1 part 2)

Oct 29-31, Friend Center 006, Princeton University, Princeton NJ.

Wednesday, Oct 29 8:15-9:00 breakfast and registration (outside Friend 006) 9:00-10:10 Piotr Indyk, Survey on Compressed Sensing 10:10-10:50 break 10:50-11:25 Stephen Smale, Understanding Patterns in Data hi-res video low-res video 11:25-12:00 Santosh Vempala, Isotropic Principal Components hi-res video low-res video 12:00-2:00 lunch (Friend Center convocation room) 2:00-2:35 James Lee, On the geometry of graphs and L_1 embeddings hi-res video low-res video 2:35-3:10 Joel Tropp, Column subset selection, matrix factorization, and eigenvalue optimization hi-res video low-res video 3:10-3:45 Assaf Naor, The Myth of Metric Dimension Reduction hi-res video low-res video 3:45-4:25 break 4:25-5:00 Yury Makarychev, Lower bounds for Sherali Adams via local-global metrics hi-res video low-res video 5:00-5:35 Robi Krauthgamer, Metric Embeddings As Computational Primitives hi-res video low-res video Thursday, Oct 30 8:30-9:00 breakfast (outside Friend 006) 9:00-9:35 Guy Kindler, Can cubic tiles be sphere-like? hi-res video low-res video 9:35-10:10 Leonard Schulman, Contraction and Expansion of Convex Sets hi-res video low-res video 10:10-10:50 break 10:50-11:25 Venkat Guruswami, Explicit Euclidean sections from expander codes hi-res video low-res video 11:25-12:00 Ben Recht, Exact Low-rank Matrix Completion via Convex Optimization hi-res video low-res video 12:00-2:00 lunch (Friend Center convocation room) 2:00-2:35 Partha Niyogi, Manifold Learning: A geometric perspective on learning theory and algorithms hi-res video low-res video 2:35-3:10 Sanjoy Dasgupta, Open problems in learning low dimensional representations hi-res video low-res video 3:10-3:45 Anna Gilbert, Applications of Compressed Sensing to Biology hi-res video low-res video 3:45-4:25 break 4:25-5:35 Rump session: open problems, brief announcements, etc Hi-res: Akavia Alon Arora Khot Magen Naor Low-res: Akavia Alon Arora Khot Magen Naor 6:15 Banquet at Palmer House (map) Friday, Oct 31 8:30-9:00 breakfast (outside Friend 006) 9:00-9:35 Yuval Rabani, Explicit construction of a small epsilon-net for linear threshold functions hi-res video low-res video 9:35-10:10 Hamed Hatami, Graph norms and Sidorenko's conjecture hi-res video low-res video 10:10-10:40 break 10:40-11:00 Navin Goyal, Learning Convex Bodies is Hard (short talk) hi-res video low-res video 11:00-11:35 Gideon Schechtman, Local Versions of Dimension Reduction hi-res video low-res video 11:35-12:10 Ilan Newman, Online embedding of metrics hi-res video low-res video 12:10-1:10 lunch (Friend Center convocation room) 1:10-1:45 Prasad Raghavendra, A Simple SDP Gap Instance for Unique Games hi-res video low-res video 1:45-2:20 Luis Rademacher, Expanders via Random Spanning Trees hi-res video low-res video 2:20-2:55 Moritz Hardt, Rounding Parallel Repetitions of Unique Games hi-res video low-res video 2:55-3:30 Alexandr Andoni, Hardness of Nearest Neighbor under L_infinity hi-res video low-res video

---

Abstracts

Isotropic Principal Components Santosh Vempala We present an extension of standard Principal Component Analysis (PCA) that appears to uncover interesting directions when PCA does not. We apply this to the problem of unraveling a mixture of arbitrary Gaussians, and give an algorithm that succeeds well beyond the known threshold for inter-Gaussian separation. We mention other potential applications.

---

On the geometry of graphs with forbidden minors James Lee I will give a structure theorem for the geometries induced on families of graphs that forbid a fixed minor, and discuss implications for the L_1 embedding/multi-flow conjecture.

---

Column subset selection, matrix factorization, and eigenvalue optimization Joel Tropp Given a fixed matrix, the problem of column subset selection requests a column submatrix that has favorable spectral properties. Most research from the algorithms and numerical linear algebra communities focuses on a variant called rank-revealing {\sf QR}, which seeks a well-conditioned collection of columns that spans the (numerical) range of the matrix. The functional analysis literature contains another strand of work on column selection whose algorithmic implications have not been explored. In particular, a celebrated result of Bourgain and Tzafriri demonstrates that each matrix with normalized columns contains a large column submatrix that is exceptionally well conditioned. Unfortunately, standard proofs of this result cannot be regarded as algorithmic. This paper presents a randomized, polynomial-time algorithm that produces the submatrix promised by Bourgain and Tzafriri. The method involves random sampling of columns, followed by a matrix factorization that exposes the well-conditioned subset of columns. This factorization, which is due to Grothendieck, is regarded as a central tool in modern functional analysis. The primary novelty in this work is an algorithm, based on eigenvalue minimization, for constructing the Grothendieck factorization. These ideas also result in an approximation algorithm for the $(\infty, 1)$ norm of a matrix, which is generally {\sf NP}-hard to compute exactly. As an added bonus, this work reveals a surprising connection between matrix factorization and the famous {\sc maxcut} semidefinite program.

---

Metric Embeddings As Computational Primitives Robi Krauthgamer Metric embedding has become an indispensable algorithmic tool, and in fact may be viewed as a computational primitive. This talk is intended to explore the boundaries of this approach, by considering richer host spaces or extending the computational model. I will survey recent progress in these directions, geared towards describing open questions. [Based on joint work with Alex Andoni.]

---

Can cubic tiles be sphere-like? Guy Kindler The unit cube tiles R^d by Z^d, in the sense that its translations by vectors from Z^d cover R^d. It is natural to ask what is the minimal surface area of a body that tiles R^d by Z^d. The volume of any such body should clearly be at least 1, and therefore its surface area must be at least that of a unit volume ball, which of order sqrt(d). The surface area of the cube, however, is of order d, and no better tiling was known. In this work we use a random construction to show that the optimal surface area is indeed of order sqrt(d), namely there exist bodies that tile R^d as a cube would, but have sphere-like surface areas. Tiling problems were considered for well over a century, but this particular tiling problem was also recently considered in computer science because of its relations with the Unique Games conjecture and with the Parallel Repetition problem. Indeed, our current result follows from the same idea that was used recently by Raz in his counter example for the strong Parallel Repetition conjecture. Joint work with Ryan O'Donnell, Anup Rao, and Avi Wigderson.

---

Expander codes over reals and explicit Euclidean sections Venkat Guruswami Classical results from the 1970's state that a random subspace of R^N of dimension N/2 has "distortion" O(1) w.h.p where the distortion is measured by sqrt{N} times the largest ratio of the L_2 to L_1 norms of a vector in the subspace. Similar randomized geometric constructions arise in areas like dimensionality reduction and compressed sensing. Explicit constructions of such objects, however, seem very hard to come by. Low distortion subspaces are of interest as they lead to good compressed sensing matrices and error-correcting codes over reals. The talk will describe constructions inspired by expander codes that can be used to produce subspaces with low distortion either explicitly or with sublinear randomness. The talk will also touch upon the connection to compressed sensing, and a near-linear time iterative signal recovery algorithm for our expander based construction. Based on joint works with James Lee, Alexander Razborov, and Avi Wigderson

---

Exact Low-rank Matrix Completion via Convex Optimization Ben Recht How can we infer answers from a survey that is only partially filled out? Suppose we ask a large collection of individuals a series of questions. We collect some data but, unfortunately, many questions are left unanswered. Is it possible for us to make an educated guess about what the missing answers should be? How can we make such a guess? In general, with no additional assumptions, this is impossible. However, if we assume that we can arrange all of the answers into a low rank matrix, there is often a unique assignment for the missing entries. In this talk, I will discuss very general settings in which one can perfectly recover all of the missing entries of a low-rank matrix from a sufficiently large random subset of entries by solving a convex programming problem. Out of all of the matrices whose entries agree with the given subset, this program finds the matrix with the minimum nuclear norm (also known as the Ky-Fan norm or the Schatten 1-norm). I will show that if the number of sampled entries is greater than C n^{1.25} r log n for some positive numerical constant C, then with very high probability, most n x n matrices of rank r are perfectly recovered by the nuclear norm heuristic. The techniques for proving the main results build upon geometric ideas from the the recent literature on compressed sensing together with probabilistic tools such as the powerful techniques of Bourgain and of Rudelson for bounding norms of operators between Banach spaces. These results illustrate a general program for perfectly reconstructing geometric objects from very limited information.

---

Manifold Learning: A geometric perspective on learning theory and algorithms Partha Niyogi We consider the following learning-theoretic question. Suppose you are given a collection of data points (a point cloud) sampled from a Riemannian submanifold of Euclidean space. What geometric or topological properties of this manifold can you provably learn (estimate) from such randomly sampled points? We show how to learn the laplace operator, the heat kernel, the harmonic forms, and the homology from random samples. The analysis of the algorithmic framework requires us to relate the geometry of a suitable data-derived random graph (or complex) to the geometry of the underlying manifold. We will consider the implications of this point of view for machine learning, statistics, and numerical analysis.

---

Open problems in learning low dimensional representations Sanjoy Dasgupta In the past decade, one of the most exciting and fruitful research directions in machine learning has been finding ways to exploit "intrinsic low dimensionality" of data that are superficially high dimensional. Numerous models and algorithms have been proposed and empirically shown to hold promise, but the underlying theory remains largely underdeveloped. There are several broad types of "intrinsic low dimensionality" that repeatedly arise in learning scenarios. I will give examples of these and explain why they are not adequately captured by existing popular dimensionality notions. I'll then describe core algorithmic/statistical tasks on such data, along with some of failings of the heuristics by which they are currently handled. Explicit construction of a small epsilon-net for linear threshold functions

---

Explicit construction of a small epsilon-net for linear threshold functions Yuval Rabani We give explicit constructions of epsilon nets for linear threshold functions on the binary cube and on the unit sphere. The size of the constructed nets is polynomial in the dimension and 1/epsilon. To the best of our knowledge no such constructions were previously known. Our results match, up to the exponent of the polynomial, the bounds that are achieved by probabilistic arguments. As a corollary we also construct subsets of the binary cube that have size polynomial in the dimension and covering radius of $n/2 - c\sqrt{n\log n}$, for any constant c. This improves upon the well known construction of dual BCH codes that only guarantee covering radius of $\n/2 - c\sqrt{n}$. Our work is motivated by questions of constructing interesting geometric objects, known to exist via probabilistic arguments. We will discuss some of this motivation. This is joint work with Amir Shpilka.

---

Graph norms and Sidorenko's conjecture. Hamed Hatami I will prove some results in the direction of answering a question of Lovasz about the norms defined by certain combinatorial structures: Inspired by the similarity of the definitions of $L_p$, Schatten, and Gowers norms, we introduce and study a wide class of norms containing these, as well as many other norms. It will be proven that every norm in this class must satisfy a Holder type inequality. Then using this condition we will verify the Hanner inequality with certain parameters for this class of norms. This will give a unified proof for the result of Hanner and a result of Tomczak-Jaegermann, and more importantly generalizes them to a wider class of norms which includes Gowers norms. In a different direction we will show an application of the above mentioned Holder type inequality to a conjecture of Sidorenko about subgraph densities. I will discuss many related open problems.

---

Learning Convex Bodies is Hard. Navin Goyal The problem we are really interested in is whether the volume of a convex body in dim n be determined from polynomially many independent uniformly random points from the body. [Note that we do not have the power of membership queries, which is used crucially in the well-known volume estimation algorithms.] We are only concerned with the number of samples, and not the complexity issue of computing the volume from these samples. We show that it is not possible to learn convex bodies in this model using polynomially many random samples. This shows that one cannot compute the volume by first learning the body. Our construction of hard distribution on convex bodies is quite simple, and may be of independent interest. Joint work with Luis Rademacher.

---

Online embedding of metrics Ilan Newman In the online setting, one has to produce an embedding of an input metric that is exposed bit by bit in the fixed host space. No changes to previous decisions are allowed. The objective is to minimize the multiplicative distortion. To the best of our knowledge, no systematic study of online metric embeddings were studied so far. We initiate such a study, and show several positive and negative results in this direction. This is a joint work with Yuri Rabinovich.

---

Expanders via Random Spanning Trees Luis Rademacher Motivated by the problem of routing reliably and scalably in a graph, we introduce the notion of a {\em splicer}, the union of spanning trees of a graph. We prove that for any bounded-degree $n$-vertex graph, the union of two {\em random} spanning trees approximates the expansion of every cut of the graph to within a factor of $O(\log n)$. For the random graph $G_{n,p}$, for $p> c\log{n}/n$, two spanning trees give an expander. This is suggested by the case of the complete graph, where we prove that two random spanning trees give an expander. The construction of the splicer is elementary --- each spanning tree can be produced independently using an algorithm by Aldous and Broder: a random walk in the graph with edges leading to previously unvisited vertices included in the tree. A second important application of splicers is to graph sparsification where the goal is to approximate every cut (and more generally the quadratic form of the Laplacian) using only a small subgraph of the original graph. Benczur-Karger \cite{BK} as well as Spielman-Srivastava \cite{SS} have shown sparsifiers with $O(n \log n/\eps^2)$ edges that achieve approximation within factors $1+\eps$ and $1-\eps$. Their methods, based on independent sampling of edges, need $\Omega(n\log n)$ edges to get any approximation (else the subgraph could be disconnected) and leave open the question of linear-size sparsifiers. Splicers address this question for random graphs by providing sparsifiers of size $O(n)$ that approximate every cut to within a factor of $O(\log n)$. This is joint work with Navin Goyal and Santosh Vempala.

---

Hardness of Nearest Neighbor under L_infinity Alex Andoni Recent years have seen a significant increase in our understanding of high-dimensional nearest neighbor search (NNS) for distances like the L_1 and L_2 norms. By contrast, our understanding of the L_infinity norm is now where it was 10 years ago. In FOCS'98, Indyk proved the following unorthodox result: there is a data structure (in fact, a decision tree) of polynomial size, which achieves O(log log d) approximation for NNS in the d-dimensional L_infinity metric. More generally, the data structure has space O(n^r), for any r>1, for approximation O(log_r log d). Our lower bound indicates that Indyk's unconventional bound might in fact be optimal. Specifically, we show a lower bound for the asymmetric communication complexity of NNS under L_infinity, which proves that this space/approximation trade-off is optimal for decision trees and for data structures with constant cell-probe complexity. In the talk, I will start out with an intuitive "information" view of Indyk's result, which will also help us understand where the lower bound comes from. This is joint work with Dorian Croitoru (MIT) and Mihai Patrascu (MIT).

---

Zeev Dvir on "A short survey on extractors for algebraically defined sources"  video (old version: video) Dana Moshkovitz on "Probabilistically Checkable Proofs" video (old version: video)

hi-res video: part 1 part 2, low-res video: part 1 part 2 (older version: video part 1 video part 2) Abstract: This talk is intended as an introductory talk for non-experts in preparation for the upcoming Princeton workshop on metric embeddings. This workshop will focus on new directions in this area, so the purpose of the tutorial is to explain some of the relevant background. We will explain the basic definitions, show some important examples, discuss some of the fundamental theorems (with a few complete proofs), show some lower bound techniques, and describe a few applications of this mathematical discipline to computer science. No prerequisites will be assumed.

paper slides video part 1 video part 2 (old version: video part 1 video part 2) We construct a new public key encryption based on two assumptions: 1. One can obtain a pseudorandom generator with small locality by connecting the outputs to the inputs using any sufficiently good unbalanced expander. 2. It is hard to distinguish between a random graph that is such an expander and a random graph where a (planted) random logarithmic-sized subset S of the outputs is connected to fewer than |S| inputs. The validity and strength of the assumptions raise interesting new algorithmic and pseudorandomness questions, and we explore their relation to the current state-of-art.

hi-res video: part 1 part 2, low-res video: part 1 part 2 (older version: part 1 part 2) Abstract: Public key encryption is one of the most important and widely used applications of intractability.  Unfortunately, a characterization of the kinds of difficult problems useful for public key encryption or other forms of secret key agreement has proved elusive.  This talk will summarize the various existing proposals for public-key encryption .  In particular, we will stress the way public-key encryption (paradoxically) needs to combine hidden mathematical structure with apparent randomness. We will also discuss efforts (both failed and successful) to link the security of encryption and worst-case complexity. What is the minimal complexity assumption we need for secure public key encryption?  What is the relationship between NP-hardness and utility of a problem in public key cryptography? What do relativization results tell us about constructions of public-key encryption functions?     The talk will try to give an intuitive presentation of the state-of-the-art (and its limits) and will omit most technical details.