The weekly Theory seminar provides an opportunity to get exposed to cutting edge research in theoretical computer science, to learn to
understand technical material from talks and to give technical presentations. Graduate students interested in doing research in algorithms, complexity theory, cryptography, quantum
computing and related areas are strongly encouraged to attend.
Regularities with varying forms and scales pervade our natural and
man-made world, from atomic structures to galaxies. The ability to
sense regular or near-regular patterns has a biological basis and has
been observed in many levels of insect/animal intelligence. From Felix
Klein's Erlanger program to the Gestalt principles of perception, much
of our understanding of the world is based on the perception and
recognition of repeated patterns, generalized by the mathematical
concept of symmetry and symmetry groups. In this talk, I present a
parallelism between a computational regularity framework and symmetry
group theory, propose a symmetry group-based regularity space embedded
in a Bayesian model, and demonstrate several properties of such a
space, including its finiteness, completeness, smoothness and its
Given the ubiquity of symmetry in both the physical and the digital
worlds, a computational model for symmetry-based regularity perception
becomes especially pertinent to computer vision, computer graphics,
and machine intelligence in general, where an intelligent being seeks
to perceive, reason and interact with the chaotic real world in the
most effective and efficient form. Surprisingly, little progress has
been made in computational regularity/symmetry for dealing with
structured patterns in real-world digital data that is full of noise
and inaccuracies. Despite many practical challenges, if time permits,
I shall show several of our state of the art symmetry detection
algorithms (published in 08-09), their applications, and initiate a
discussion on symmetry and entropy from an information theory
Combinatorial (weighted) counting problems, such as counting the
number of satisfying assignments of a Boolean satisfiability problem
or computing the partition function of a graphical model, can be
expressed as tensor contractions diagrammed by a bipartite graph
$\Gamma=(V,U,E)$. Many algorithms for solving these problems
efficiently use tree structure and factorization over a semiring (the
"sum-product algorithm"). Over a proper ring, cancellation can be
exploited as well. This requires a change of basis so that the
Grassmann-Plucker identities are locally satisfied, and the addition
of orientation or ordering information. Recently, this Pfaffian-based
approach has been used by Valiant and Cai to provide unexpected,
polynomial-time "accidental" algorithms for certain counting problems.
Their method expands the vertices of $\Gamma$ into graph fragments
called matchgates and applies the FKT algorithm to find a Pfaffian
orientation and compute the perfect matching polynomial. We
demonstrate a simplification of this approach using only a $|E| \times
|E|$ matrix and give some generalizations. Natural problems treatable
by these generalizations have been previously considered in a different
context, and we present one such example. This is joint work with
J.M. Landsberg and Serguei Norine. http://arxiv.org/abs/0904.0471
Khot's Unique Games conjecture UGC is one of the most central open
problems in computational complexity theory.UGC asserts that for a
certain constraint satisfaction problem, it is NP-hard to decide whether there is a
labeling that satisfies almost all the constraints or,
for every labeling, the fraction of the constraints satisfied is very
small. Since its origin, the UGC has been applied with remarkable
success to prove tight hardness of approximation results for several
important NP-hard problems such as Vertex Cover , MAXCUT.
In this talk, we will present a purely spectral algorithm for Unique
Games. Our algorithm, given a 1-\epsilon satisfiable instance of UG,
recovers a good labelling (that satisfies more than 99% of the
constraints), when the underlying graph G belongs to a certain general
class of graphs. This class contains, for instance, expander graphs
and Cayley graphs of abelian groups. The running time of the algorithm
depends exponentially on the dimension of a certain eigenspace of G.
As a significant application, our algorithm is able to distinguish (in
quasi-polynomial time) highly satisfiable instances of UG on
underlying graphs that have been proved to be hard for a natural
semidefinite programming relaxation for Unique Games (integrality gap
instances), giving evidence that spectral techniques might be a more
powerful tool for approximation algorithms than SDPs.
Traditional micro-economic theory typically assumes that individuals and institutions can completely understand the consequences of their decisions given the information they have available. This assumption may not be valid as we might have to solve hard computational problems to optimize our choices. What happens if we restrict the computational power of economic agents?
There has been some work in economics treating computation as a fixed cost or simply considering the size of a program. This talk will explore a new direction bringing the rich tools of computational complexity into economic models, a tricky prospect where even basic concepts like "input size" are not well defined.
We show how to incorporate computational complexity into a number of economic models including game theory, prediction markets, forecast testing, preference revelation and contract theory.
This talk will not assume any background in either economics or computational complexity.
Host: Sofya Raskhodnikova
Note: This talk is also part of the CSE Colloquium. It will held at 10 a.m. on March 2 (Tuesday) at 113 IST.
The ruler folding problem asks: Given a set of n line segment links attached at their end points with rotating joints. Find a minimum length folding of this chain of links along a line. In this paper, we provide an improved approximation for the problem if the longest link is significantly larger than the rest. We then consider generalizations to trees of links and instances containing cycles of links. We provide the first fully polynomial time approximation scheme (FPTAS) for the tree variant and prove the inapproximability of cycle variants. Lastly, we consider the area optimization problem, of folding the links to achieve minimum area within minimum width. We prove the problem and any multiplicative approximation to be NP-hard and also prove the impossibility of any additive polynomial time approximation schemes (PTAS).
We provide new examples for exponential separations between quantum and classical query complexity by considering hidden shift problems over families of highly non-linear Boolean functions. These so-called bent functions arise in cryptography, where their property of having perfectly flat Fourier spectra on the Boolean hypercube gives them resilience against certain types of attack. We present quantum algorithms that solve the hidden shift problems for several well-known classes of bent functions in polynomial time and with a polynomial number of queries, while the classical query complexity is shown to be exponential. Our approach uses a technique that exploits the duality between bent functions and their Fourier transforms. Based on a SODA'10 paper. See also http://arxiv.org/abs/0811.3208
Most crypto primitives are constructed based on other primitives, and
the security is proved by reduction. Because the standard crypto
assumptions are unproved, researchers have tried to weaken the
assumptions for a given primitive. So it is natural to ask which
assumptions are too weak to yield a proof that a crypto primitive is
possible. Impagliazzo and Rudich [IR89] were the first to give a
formal treatment of this issue. They showed that proving a key
agreement (KA) protocol using a one-way permutation (OWP) as a
black-box is secure is as hard as proving P is not equal to NP, a
strong evidence that separates KA from OWP. In this talk, I will
explain the actual separation proof and the meaning of this negative
[IR89] Russell Impagliazzo and Steven Rudich. Limits on the Provable
Consequences of One-way Permutations. STOC 1989
Counting type problems and their associated partition functions
have been studied from many interesting perspectives.
In the statistical physics community there is a long history of research on
Exactly Solved Models
(Fisher, Temperley, Kasteleyn, C.N.Yang, Baxter, Lieb, ...)
In the pure mathematics community Lovasz defined
the general graph homomorphism functions in 1967.
There is a general sense that
certain "systems" can be solved "exactly", while others
are "difficult". There is also tremendous interest
in certain "systems" which are "difficult" in general,
but can be solved "exactly" on restricted classes of inputs,
the most prominent of which is the planar case.
Fisher-Kasteleyn-Temperley method is a famous example.
In this talk I will first briefly survey some previous work.
Then I will report some exciting new development.
They give classification theorems
on a broad class of counting type problems, into
(1) those which are tractable (i.e. in polynomial time) on general graphs,
(2) those which are \#P-hard on general graphs but tractable on planar
(3) those which are \#P-hard even on planar graphs.
Holographic algorithms (both with matchgates and with Fibonacci gates)
play a crucial role in this classification theorem. In a fairly general
sense, we are finally able to answer, in a provable sense (assuming
P is not equal to \#P), the venerable question from physics:
Exactly (no pun intended) what "systems" can be solved "exactly" and what
"systems" are "difficult".
Unrestricted circuit complexity is one of the oldest and most difficult parts of complexity theory. We are unable to prove even a superlinear circuit lower bound for any NP problem --- the best we can do after years of effort is 5n -- o(n). Nearly all results in this area are obtained using gate elimination method that is unlikely to give results that are better than linear. This is why study of variations of gate elimination method and its applications is important.
In this talk we will first discuss a method for constructing efficient boolean circuits using SAT-solvers to give an example of how upper bounds in circuit complextity can be obatained automatically. Then we will proceed to methods for proving linear lower bounds and describe a result that uses a combined complexity measure in gate elimination instead of just counting the number of gates. Finally, the existing constructions of feebly one-way permutations by Hiltgen will be presented, that use trivial lower bounds on circuit complexity.
This talk will not assume any background in circuit complexity or cryptography.
Talk is based on recent publications "Finding Efficient Ciruits Using SAT-solvers" and "New upper bounds on Boolean Circuit Complexity of Symmetric Functions" and other work done together with E.Demenkov, E.Hirsch, A.Kojevnikov and A.Kulikov.
In the past few years differential privacy has gained a lot of focus
from the privacy community because of its strong theoretical stand
point. It provides meaningful privacy guarantees to individual entries
in a database against an adversary in the presence of arbitrary
external information. Differential Privacy has been successfully used
in various settings where the queries to the database are some kind
of aggregate queries [Dwork08]. However, before the work of Gupt et
al. [GLMRT10], it was not known how to output combinatorial objects
(for eg. Min-Cut) efficiently in a differentially private setting.
Gupta et al. provided efficient differentially private algorithms for
various combinatorial problems (e.g., Min-Cut, k-Median, Vertex Cover
In my talk, I intend to present the Private Min-Cut algorithm
presented by Gupa et al. The problem is as follows:
The generic problem of min-cut states, given an undirected, unweighted
multi graph G=(V,E) the objective is to output a partition of the
vertex set V=V_1 U V_2 such that the number of edges between V_1 and
V_2 is minimum. In a differentially private setting we want to output
a cut which is "close" to the minimum. Such a relaxation is necessary
as by definition any differentially private algorithm has to be
randomized and hence one has to allow a margin for error.
Gupta et al. provides a differentially private algorithm which outputs
a cut with the expected # of edges as OPT + \theta(ln n /\eps), where
n is the # of vertices, OPT is the optimal cut size and \eps is the
privacy parameter for differential privacy. They also prove a lower
bound showing that one cannot hope to get a strictly differentially
private algorithm which has a better performance. The algorithm
heavily relies on Karger's algorithm [Kar96] for min-cut and a generic
algorithm for differential privacy (called exponential mechanism) due
to McSherry et al. [MT07].
I plan to cover both the private min-cut algorithm and the proof of
the lower bound in sufficient detail.
[GLMRT10] Differentially Private Combinatorial Optimization. Anupam
Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, Kunal Talwar.
[MT07] Mechanism Design via Differential Privacy. Frank McSherry and
Kunal Talwar. STOC 2007
[Dwork08] Differential Privacy: A Survey of Results. TAMC, 2008
[Kar96]A New Approach to Min-cut problem. David Karger. JASM 1996
You are given a set system, how do you find the set of k elements which
are most costly to cover? Or you are allowed to pick some sets on the
cheap today, and tomorrow the worst-case k elements will arrive and need
coverage --- you can then buy (costlier) sets to cover these k elements.
You can imagine similar max-min versions of other covering problems too:
how do you solve such max-min problems?
In this paper, we show that a very simple and natural strategy gives
asymptotically near-optimal algorithms for set cover and several other
covering problems. Our proofs are interesting in their own right, they
use linear-programming (and in particular, rounding the LP *duals*),
even though the algorithms are completely combinatorial.
This is joint work with Viswanath Nagarajan and R.Ravi.
A quantum system consisting of multiple subsystems may be in an
Such inherently non-classical states underly many counter-intuitive
quantum mechanics, as well as their information processing applications. While
bipartite quantum entanglement is well understood, much less is known
or more partite entanglement. A basic question is to classify
of entanglement, according to the feasibility of converting one state to another
through protocols that do not use quantum communication and succeed
with a non-zero
In this talk, I will focus on the entanglement classification in
of 2 by m by n dimensions. I will show that the classical result of Kronecker
on the canonical forms of pairs of matrices (i.e. ``matrix pencils'')
can be used
to describe the equivalence classes of entangled states, and to decide
Joint work with Eric Chitambar and Carl A. Miller. Preprint available at
arXiv:0911.1803 and arXiv:0911.4058.