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