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.

### 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.