Theory Seminar Schedule for Spring 2010
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.
| Date | Speaker | Title |
|---|---|---|
| Jan 11, 2010 | Orientation | |
| Jan 18, 2010 | Holiday | Martin Luther King Day |
| Jan 25, 2010 | Sean Hallgren | Fully Homomorphic Encryption over the Integers |
| Feb 1, 2010 | Yanxi Liu | Computational Regularity – A symmetry group-based Bayesian model |
| Feb 8, 2010 | Jason Morton | Holographic Algorithms without Matchgates |
| Feb 15, 2010 | Alexandra Kolla | Spectral Techniques for Tackling the Unique Games Conjecture |
| Mar 2, 2010 (10 am, 113 IST) | Lance Fortnow | Bounding Rationality by Computational Complexity (This is also part of CSE colloquium.) |
| Mar 8, 2010 | Holiday | Spring Break |
| Mar 22, 2010 | Ishan Behoora | Folding links is hard |
| Mar 22, 2010 | Martin Roetteler | Quantum algorithms for highly non-linear Boolean functions |
| Mar 29, 2010 | Youngtae Youn | Black-Box Separation of Secure Key Agreement from One Way Permutation |
| Mar 31, 2010 (4 pm, 203 Leonhard) | Jin-Yi Cai | Holographic Algorithms Capture Precisely Tractable Planar Counting Problems |
| Apr 5, 2010 (2:30 pm, 222 IST) | Grigory Yaroslavtsev | Linear Bounds on Circuit Complexity and Feebly One-way Permutations |
| Apr 12, 2010 | Abhradeep Guha Thakurta | Differentially Private Min-Cut |
| Apr 19, 2010 | Anupam Gupta | Thresholded Covering Algorithms for Robust and Max-Min Optimization |
| Apr 26, 2010 | Yaoyun Shi | Matrix pencils and entanglement classifications |
All talks will be at 2:30 pm on Mondays in IST 333 (unless they are part of the departmental colloquium).
If you would like to speak, please email us at: theory [at] cse [dot] psu [dot] edu.
If you want to receive announcements of upcoming talks, please join the theory mailing list .
Archives
Spring 2007 Fall 2007 Spring 2008 Summer 2008 Fall 2008 Spring 2009 Fall 2009 Spring 2010 Fall 2010 Spring 2011 Fall 2011 Spring 2012 Fall 2012 Spring 2013 Fall 2013 Fall 2014 Spring 2015 Fall 2015 Spring 2016 Fall 2016
Computational Regularity- A symmetry group-based Bayesian model (Yanxi Liu, Penn State CSE)
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 recursive hierarchies.
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 perspective.
Holographic Algorithms without Matchgates (Jason Morton, Penn State Math and Statistics)
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 .
Spectral Techniques for Tackling the Unique Games Conjecture (Alexandra Kolla, IAS/DIMACS)
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.
Bounding rationality by computational complexity (Lance Fortnow, Northwestern University)
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.
Bio: http://lance.fortnow.com/bio.php
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.
Folding links is hard(Ishan Behoora)
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).
Keywords-folding; approximation; FPTAS; PTAS; hardness
Quantum algorithms for highly non-linear Boolean functions(Martin Roetteler, NEC Labs)
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
Black-Box Separation of Secure Key Agreement from One Way Permutation (Youngtae Youn)
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 result.
[IR89] Russell Impagliazzo and Steven Rudich. Limits on the Provable Consequences of One-way Permutations. STOC 1989
Holographic Algorithms Capture Precisely Tractable Planar Counting Problems (Jin-Yi Cai, University of Wisconsin, Madison)
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, or
(2) those which are \#P-hard on general graphs but tractable on planar graphs, or
(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”.
Linear Bounds on Circuit Complexity and Feebly One-way Permutations (Grigory Yaroslavtsev)
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.
Bio: http://sites.google.com/site/grigoryyaroslavtsev/Home/about-me
Home page: http://logic.pdmi.ras.ru/~grigory
Differentially Private Min-Cut (Abhradeep Guha Thakurta)
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 etc).
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.
References:
[GLMRT10] Differentially Private Combinatorial Optimization. Anupam Gupta, Katrina Ligett, Frank McSherry, Aaron Roth, Kunal Talwar. SODA-2010 [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
Thresholded Covering Algorithms for Robust and Max-Min Optimization (Anupam Gupta, CMU)
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.
Matrix pencils and entanglement classifications (Yaoyun Shi, University of Michigan)
A quantum system consisting of multiple subsystems may be in an “entangled” state. Such inherently non-classical states underly many counter-intuitive properties of quantum mechanics, as well as their information processing applications. While bipartite quantum entanglement is well understood, much less is known about three- or more partite entanglement. A basic question is to classify different “types” 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 probability.
In this talk, I will focus on the entanglement classification in tripartite systems 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 equivalence relation efficiently.
Joint work with Eric Chitambar and Carl A. Miller. Preprint available at arXiv:0911.1803 and arXiv:0911.4058.
Recent Comments