Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

How to round subspaces: a new spectral clustering algorithm

Ali Kemal Sinop
Simons Institute for the Theory of Computing, Berkeley
February 10, 2015
Given a $k$-dimensional linear subspace, consider the problem of approximating it (with respect to the spectral norm) in terms of another subspace spanned by the indicators of a $k$-partition of the coordinates. This is known as the spectral clustering problem, first introduced by [Kannan, Kumar]. It is a generalization of the standard $k$-means problem, which corresponds to the Frobenius norm. In this talk, I will present a new spectral clustering algorithm.

Quantum computing with noninteracting particles

Alex Arkhipov
Massachusetts Institute of Technology
February 9, 2015
We introduce an abstract model of computation corresponding to an experiment in which identical, non-interacting bosons are sent through a non-adaptive linear circuit before being measured. We show that despite the very limited nature of the model, an exact classical simulation would imply a collapse of the polynomial hierarchy. Moreover, under plausible conjectures, a "noisy" approximate simulation would do the same.

Dimension expanders via rank condensers

Michael Forbes
Member, School of Mathematics
February 3, 2015
Expander graphs are sparse graphs with good connectivity properties and they have become ubiquitous in theoretical computer science. Dimension expanders are a linear-algebraic variant where we ask for a constant number of linear maps that expand subspaces of a vector space (instead of subsets of vertices). After their definition 10 years ago by Barak, Impagliazzo, Shpilka and Wigderson there are now two constructions of constant-degree dimension expanders, both of which suggest dimension expanders are more complicated than expander graphs.

On monotonicity testing and boolean isoperimetric type theorems

Subhash Khot
New York University
February 2, 2015

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand. As an application, we give a monotonicity testing algorithm that makes $\tilde{O}(\sqrt{n}/\epsilon^2)$ non-adaptive queries to a function $f:\{0,1\}^n \mapsto \{0,1\}$, always accepts a monotone function and rejects a function that is $\epsilon$-far from being monotone with constant probability. Joint work with Dor Minzer and Muli Safra. The paper is available on ECCC:

Publicly-verifiable non-interactive arguments for delegating computation

Guy Rothblum
Stanford University
January 26, 2015
We construct publicly verifiable non-interactive arguments that can be used to delegate polynomial time computations. These computationally sound proof systems are completely non-interactive in the common reference string model. The verifier’s running time is nearly-linear in the input length, and poly-logarithmic in the complexity of the delegated computation. Our protocol is based on graded encoding schemes, introduced by Garg, Gentry and Halevi (Eurocrypt 2012). Security is proved under a falsifiable and arguably simple cryptographic assumption about graded encodings.

Small value parallel repetition for general games

Ankit Garg
Princeton University
January 20, 2015
We prove a parallel repetition theorem for general games with value tending to 0. Previously Dinur and Steurer proved such a theorem for the special case of projection games. Our proofs also extend to the high value regime (value close to 1) and provide alternate proofs for the parallel repetition theorems of Holenstein and Rao for general and projection games respectively. Our techniques are elementary in that we only need to employ basic information theory and discrete probability in the small-value parallel repetition proof.

More on sum-of-squares proofs for planted clique

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
December 9, 2014

While this talk is a continuation of the one I gave on Tue Nov 25, it will be planned as an independent one. I will not assume knowledge from that talk, and will reintroduce that is needed. (That first lecture gave plenty of background material, and anyone interested can watch it on

Taming the hydra: the Word Problem, Dehn functions, and extreme integer compression

Timothy Riley
Cornell University; Member, School of Mathematics
December 2, 2014
For a finitely presented group, the Word Problem asks for an algorithm which declares whether or not words on the generators represent the identity. The Dehn function is the time-complexity of a direct attack on the Word Problem by applying the defining relations. I will survey these topics and their interrelationships. A "hydra phenomenon" gives rise to novel groups with extremely fast growing (Ackermannian) Dehn functions. I will explain why, nevertheless, there are efficient (polynomial time) solutions to the Word Problems of these groups.

Parallel Repetition From Fortification

Dana Moshkovitz
Massachusetts Institute of Technology
December 1, 2014
The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game in terms of the value of the base game and the number of repetitions. In this work we give a simple transformation on games -- "fortification" -- and show that for fortified games, the value of the repeated game decreases perfectly exponentially with the number of repetitions, up to an arbitrarily small additive error. Our proof is combinatorial and (very) short.

As corollaries, we obtain: