Theoretical Computer Science Group

Theory Seminar Schedule - Spring 2008

Date Speaker Title
Jan 15, 2008 Adam Smith The Distinct Elements Problem (or Approximating the Support Size of a Distribution)
Jan 22, 2008 Shiva Kasiviswanathan What can we learn Privately?
Jan 29, 2008 Sean Hallgren Quantum Algorithms and The Hidden Subgroup Problem
Feb 12, 2008 (starts at 11:15) Swarat Chaudhuri Branching Pushdown Tree Automata
Feb 13, 2008 Mohammad Taghi Hajiaghayi Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design and Related Problems
(Part of Deparamental Colloquium)
Feb 19, 2008 Sanjukta Bhowmick Combinatorial Problems in Automatic Differentiation
Feb 21, 2008 Arie Matsliah Approximate Hypergraph Partitioning and Applications (Part of Deparamental Colloquium)
Mar 03, 2008 Ravi Kumar Structural Properties Of Online Social Networks (Part of Deparamental Colloquium)
Mar 25, 2008 Adam Smith Proof of Knowledge and Incrementally Verifiable Computation
Apr 01, 2008 Takis Konstantopoulos SPQR (Skorokhod, Palm, Queueing, and Reflection)
Apr 08, 2008 Youngtae Youn Space-Efficient Identity-Based Encryption (by Boneh, Gentry and Hamburg)
Apr 22, 2008 Adam Smith Proofs of knowledge II
Apr 25, 2008 Daniel Gottesman The Power of Quantum Systems on a Line (Part of Deparamental Colloquium)
May 06, 2008 Martin Furer Solving NP-Complete Problems with Quantum Search

All talks will be at 11am in IST 333 (unless they are part of the departmental colloquium).

If you would like to speak, please email: theory at cse psu dot edu.

If you want to receive announcements of upcoming talks join the theory-local mailing list.

Archives

Spring 2007     Fall 2007     Spring 2008    Summer 2008     Fall 2008     Spring 2009

The Distinct Elements Problem (or Approximating the Support Size of a Distribution)

We consider the problem of approximating the support size of a distribution from a small number of samples, when each element in the distribution appears with probability at least 1/n. This problem is closely related to the problem of approximating the number of distinct elements in a sequence of length n. For both problems, we prove a nearly linear (in n) lower bound on the query complexity, applicable even for approximation with additive error.

At the heart of the lower bound is a construction of two positive integer random variables, X and Y, with very different expectations and the following condition on the first k moments: E[X]/E[Y] = E[X^2]/E{Y^2] = ... = E[X^k]/E[Y^k]. Our lower bound method is also applicable to other problems. In particular, it gives new lower bounds for the sample complexity of (1) approximating the entropy of a distribution and (2) approximating how well a given string is compressed by the Lempel-Ziv scheme.

Based on joint work with Sofya Raskhodnikova, Dana Ron and Amir Shpilka, published in FOCS 2007.

What can we learn Privately?

Learning problems form an important category of computational tasks that generalizes many of the computations researchers apply to large real-life datasets. We ask (and answer): what concept classes can be learned privately, namely, by an algorithm whose output does not depend too heavily on any one input or specific training example? Our goal is a complexity-theoretic classification of learning problems efficiently solvable with the privacy restriction.

In this talk, we present four private learning models: local interactive (LI), learning non-interactive (LNI), centralized interactive (CI), and centralized non-interactive (CNI). We give a characterization of these models with respect to standard learning models, PAC and SQ. We show that for learning problems LNI is a strict subset of LI, and LI is a strict subset of CNI=CI. This characterization takes into account the number of samples required for learning, but not computational efficiency. We also present a partial characterization of these models when efficiency is taken into account.

Joint work with Homin Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith.

Quantum Algorithms and The Hidden Subgroup Problem

The hidden subgroup problem encompasses most problems where quantum computers have an exponential speedup over the best known classical algorithm. It is also one of the main open problems in quantum algorithms. Efficient quantum algorithms for certain instances would result solve graph isomorphism and the unique shortest lattice vector problem. In this talk I will give a general introduction and state some open problems.

Branching Pushdown Tree Automata

We observe that pushdown tree automata known in the literature cannot express combinations of branching and pushdown properties. This is because a pushdown tree automaton processes the children of a tree node in possibly different control states but with identical stacks. We propose branching pushdown tree automata (BPTAs) as a solution. In a BPTA, a push-move views its matching pops as an unbounded, unordered set of successor moves and can assert existential and universal requirements on them, just the way finite automata on unranked, unordered trees pass requirements to the children of a tree node. We show that BPTAs can express some natural properties and are more expressive than pushdown tree automata. Using a small-model theorem, we prove their emptiness problem to be decidable. The problem becomes undecidable, however, if push-moves are allowed to specify the ordering of matching pops.

Approximation Algorithms for Non-Uniform Buy-at-Bulk Network Design and Related Problems

We consider approximation algorithms for non-uniform buy-at-bulk network design problems. Buy-at-bulk network design problems arise in settings where economies of scale and/or the availability of capacity in discrete units result in concave or sub-additive cost functions on the edges. One of the main application areas is in the design of telecommunication networks. The typical scenario is that capacity (or bandwidth) on a link can be purchased in some discrete units u_1 < u_2 < ... < u_r with costs c_1 < c_2 < ... < c_r such that the cost per bandwidth decreases c_1/u_1 > c_2/u_2 > ... > c_r/u_r. The capacity units are sometimes referred to as cables or pipes. A basic problem that needs to be solved in this setting is the following: given a set of bandwidth demands, install sufficient capacity on the links of an underlying network topology so as to be able to route the demands. The goal is to minimize the total cost. Alternatively, we can think of the following scenario. We have two independent cost functions on the links of the network: a buy cost b(e) a rent cost r(e). We are given a set of demands between some pairs of nodes. A feasible solution for the non-uniform multicommodity buy-at-bulk instance is to buy some links and rent some other ones such that all the demands can be routed and the total cost is minimized; the cost of every bought edge is b(e) and for rented edges it is r(e) per unit of flow (bandwidth) over that link. This problem generalizes several classical problems, such as minimum cost flow to the settings that the cost of each edge is a concave monotone actor of \\Omega(log^{1/4-\\eps} n) for any \\eps>0. We give the first poly-logarithmic approximation algorithm for this problem. Time permitting we will mention the applications of our approach for stochastic two-stage network design and network design with vertex costs.

Combinatorial Problems in Automatic Differentiation

Automatic differentiation is based on evaluating exact derivatives of functions by using the chain rule in order to avoid the inevitable numerical errors of Taylor's method. Function sequences in the chain rule are represented as directed acyclic graphs. In this talk, I will present some of the combinatorial problems associated with automatic differentiation related to optimal Jacobian and Hessian computation.

Approximate Hypergraph Partitioning and Applications

I will present an algorithm that given eps>0 and a graph G on n vertices outputs an eps-regular partition of G in O(n) time.Unlike the previous approaches for this problem that \"reproved\"Szemerdi\'s regularity lemma algorithmically and therefore guaranteed to find partitions of tower-size only, our algorithm will find a small regular partition if one exists.The main tool that we develop for the above task is an algorithm for finding approximate partitions of hypergraphs, which generalizes the algorithm of Goldreich-Goldwasser-Ron for finding approximate partitions of graphs. Joint work with Eldar Fischer and Asaf Shapira.

Structural Properties Of Online Social Networks

Online social networks have become major and driving phenomena on the web. In this talk we focus on structural and algorithmic questions related to large online social networks. We formulate a simple and general model of social networks that can explain the success of Milgram's famous experiment that gave rise to `six-degrees of separation'. We then study the neighborhood connectivity structure of users in a social network, where two users are connected if they share a common interest.

Proof of Knowledge and Incrementally Verifiable Computation

I will introduce proofs of knowledge -- an important ingredient in modern cryptography -- and discuss some recent connections between proofs of knowledge and short proofs of a computation's correctness. The talk will be based on the "Computationally-Sound Proofs" of Killian and Micali, as well as the winner of the Best paper award at TCC this year, "Incrementally Verifiable Computation" by Paul Valiant. The talk will be self-contained.

SPQR (Skorokhod, Palm, Queueing, and Reflection)

The Skorokhod reflection problem, originally introduced as a means for constructing solutions to stochastic differential equations in bounded regions, has found applications in many areas of Probability, for example in queueing-like stochastic dynamical systems; its uses range from methods for proving limit theorems to representations of local times of diffusions and control. In this talk, I will present several applications, e.g. to Levy stochastic networks and to queueing-like systems driven by local times of Levy processes, and give an order-theoretic approach to the problem by extending the domain of functions involved from the real line to a fairly arbitrary partially ordered set. I will also discuss how Palm probabilities can be used in connection with the Skorokhod problem to obtain information about stationary solutions of certain systems.

Efficient Identity-Based Encryption (by Boneh, Gentry and Hamburg)

Identity Based Encryption (IBE) systems are often constructed using bilinear maps (a.k.a. pairings) on elliptic curves. One exception is an elegant system due to Cocks which builds an IBE based on the quadratic residuosity problem modulo an RSA composite N. The Cocks system, however, produces long ciphertexts. Since the introduction of the Cocks system in 2001 it has been an open problem to construct a space efficient IBE system without pairings. In this paper we present an IBE system in which ciphertext size is short: an encryption of an l-bit message consists of a single element in ZN plus l+1 additional bits. Security, as in the Cocks system, relies on the quadratic residuosity problem. The system is based on the theory of ternary quadratic forms and as a result, encryption and decryption are slower than in the Cocks system.

Proofs of knowledge II

Two weeks ago, I described proofs of knowledge, and how we can construct interactive proof systems with very little communication. This week, I'll describe the additional restriction of *zero-knowledge* and why it is useful. Time permitting, I'll describe some of the difficulties of constructing and analyzing proof systems in the quantum computational model, some results and open questions

The Power of Quantum Systems on a Line

Kitaev defined a complexity class QMA (\"Quantum Merlin-Arthur\"), which is essentially the quantum version of the class NP: QMA is, roughly speaking, the set of problems where the answer may be difficult to find, but is easy to check on a quantum computer. As with NP, QMA has complete problems; if you can solve a QMA-complete problem, you can solve any problem in QMA. In particular, Kitaev showed that the 5-local Hamiltonian problem, which asks for the ground state energy (lowest eigenvalue) of a Hamiltonian matrix interacting up to 5 qubits in a term, is QMA-complete. A series of later results improved this to show that finding the ground state energy remains QMA-complete even for a Hamiltonian only interacting nearest-neighbor qubits in a 2-dimensional lattice. In this talk, I will sketch a proof that nearest-neighbor interactions in a line are sufficient. The individual particles are not qubits now, but 12-state systems. This result is in contrast to the analogous classical problem, which has a polynomial-time algorithm.

Solving NP-Complete Problems with Quantum Search

In his seminal paper, Grover points out the prospect of faster solutions for an NP-complete problem like SAT. If there are n variables, then an obvious classical deterministic algorithm checks out all 2^n truth assignments in about 2^n steps, while his quantum search algorithm can find a satisfying truth assignment in about 2^{n/2} steps.

For several NP-complete problems, many sophisticated classical algorithms have been designed. They are still exponential, but much faster than the brute force algorithms. The question arises whether their running time can still be decreased from T(n) to \tilde{O}(\sqrt{T(n)}) by using a quantum computer. Isolated positive examples are known, and some speed-up has been obtained for wider classes. Here, we present a simple method to obtain the full T(n) to \tilde{O}(\sqrt{T(n)}) speed-up for most of the many non-trivial exponential time algorithms for NP-hard problems. The method works whenever the widely used technique of recursive decomposition is employed.

This included all currently known algorithms for which such a speed-up has not yet been known.