POSTER SESSION -- WOMEN IN THEORY WORKSHOP
Tuesday, June 17th -- 20:00-22:00
Part 1: 20:00-20:30
Anat Paskin Evaluating Branching Programs on Encrypted Data
We present a public key encryption scheme with the following properties. Given a branching program P, and an encryption c of an input x, it is possible to efficiently compute a succinct ciphertext c' from which P(x) can be efficiently decoded using the secret key.
The size of c' depends polynomially on the size of x and the length of P, but not on the size of P. In interesting special cases, one can evaluate finite automata, decision trees, and OBDDs on encrypted data, where the size of c' does not depend on the size of the object being evaluated.
These are the first general representation models for which such a feasibility result is shown. We also show how to strengthen the above so that c' does not contain additional information about P, even if the public key and c are maliciously formed. This yields a one round (two message) secure protocol for evaluating a length-bounded branching program P held by a server, on an input x held by a client. A distinctive feature of this protocol is that it completely hides the size of the server's input P. In particular, the client's work is independent of the size of P.
Jenn Wortman Learning from Collective Behavior paper
Inspired by longstanding lines of research in sociology and related fields, and by more recent large-population human subject experiments on the Internet and the Web, we initiate a study of the computational issues in learning to model collective behavior from observed data. We define formal models for efficient learning in such settings, and provide both general theory and specific learning algorithms for these models. This talk is based on joint work with Michael Kearns.
Shuxin Nie Finding long cycles and circuits paper
In both directed and undirected graphs, a cycle is a vertex simple closed walk and a circuit is an edge simple closed walk. In general, for a graph G, we define S as a set of vertices. Then an S-circuit is a circuit with every vertex of S visited at most once. When S = V(G), an S-circuit is a simple cycle; When S =\emptyset, it’s an ordinary circuit. Both the longest cycle and longest circuit problems are NP-hard problems. We are interested in finding good approximation algorithms for the problems. For a directed graph, we can find a cycle/circuit of length at least log n/log log n in polynomial time if such a cycle/circuit exists. For an undirected graph with a longest cycle/circuit of length ℓ, we can find a cycle/circuit of length at least exp(\Omega(\sqrt{log ℓ)) in polynomial time.
Alexandra Kolla Unique Games on expanding constraint graphs are easy
I will present efficient algorithms to find a good solution to the Unique Games problem when the constraint graph is an expander. I will show an approach that is based on the observation that the information of the satisfying labeling is encoded within the first few eigenvectors of the label-extended graph. This leads to a simple spectral partitioning algorithm for recovering highly satisfying assignments. This is Joint Work with Sanjeev Arora, Subash Khot, David Steurer, Madhur Tulsiani and Nisheeth Vishnoi.
Sushmita Gupta Hardness Amplification in nondeterministic logarithmic space
Part 2: 20:30-21:00
Anne Broadbent How to use a quantum computer without having to trust it
We consider the scenario where a user wishes to interface with a quantum computer, but is unwilling to reveal her input, output or even the function that she is computing. We call this task "universal blind quantum computation", and discuss how to accomplish it with information-theoretic security.
Gillat Kol Games for exchanging information
In recent years there has been a growing interest in bridging Game Theory and Cryptography. We consider rational versions of two classical cryptographic problems: secret sharing and function evaluation. We show that schemes for these tasks, in which players' values come from a bounded domain, cannot satisfy some of the most desirable properties. In contrast, we suggest protocols for rational secret sharing where the shares come from an unbounded domain, but have a finite expectation. Joint work with Moni Naor
Erin Chambers Finding interesting topological features
We will motivate and present various methods for finding interesting topological features in various settings such as meshes and simplicial complexes.
Nutan Limaye The complexity of membership and counting in generalised VPA.
We will consider pushdown automata models that generalise Visibly Pushdown Automata (VPA) and consider the membership problem and counting problem for such models. The complexity of these fits in the spetrum between NC1 and LogCFL. We thus study the interplay of language classes and complexity classes.
Prajakta Nimbhorkar Longest path problem in planar DAGs in UL \cap coUL.
We investigate the complexity of the longest path problem in graphs. It is known to be NP-complete for general graphs. For DAGs, it is in non-deterministic logspace. We show that it is in unambiguous logspace if the DAG is planar.
Part 3: 21:00-21:30
Christine Chung The Price of Stochastic Anarchy
We consider the evolutionary game theory solution concept of stochastic stability, and propose the price of stochastic anarchy as an alternative to the price of (Nash) anarchy for quantifying the cost of selfishness and lack of coordination in games. As a solution concept, the Nash equilibrium has disadvantages that the set of stochastically stable states of a game avoid: unlike Nash equilibria, stochastically stable states are the result of natural dynamics of computationally bounded and decentralized agents, and are resilient to small perturbations from ideal play. The price of stochastic anarchy can be viewed as a smoothed analysis of the price of anarchy, distinguishing equilibria that are resilient to noise from those that are not.
Geetha Jagannathan Private Inference Control For Aggregate Database Queries
Access control policies and related mechanisms have been used for several decades to prevent unauthorized users from accidentally or deliberately extracting sensitive information. However, access control mechanisms alone cannot ensure the security of a database. An authorized user might invoke a sequence of queries, each of which is under his privileges, but whose results can be combined to infer some additional information about the data. Various ``inference control'' methods have been developed in the past to prevent users from inferring sensitive information through a sequence of queries. Private inference control provides privacy properties to both database owners and users making queries. It protects the database owner by limiting access to the data according to a specified inference control policy, but also to protect the user by preventing the database owner from learning anything about the user's queries.
In this talk, I present private inference control protocols for aggregate queries, such as those provided by statistical databases or modern database languages, to a database in a way that satisfies both privacy requirements and inference control requirements. For each query, the client learns the value of the function for that query if and only if the query passes a specified inference control rule. The server learns nothing about the queries, and the client learns nothing other than the query output for passing queries.
Susan Margulies P, NP and the Nullstellensatz: A Cross-section of Complexity Theory and Combinatorial Optimization. paper Δ
Systems of polynomial equations over an algebraically-closed field K can be concisely used to model many combinatorial problems. In this way, a combinatorial problem is feasible (e.g., a graph is 3-colorable or has an independent set of size k) if and only if a related system of polynomial equations has a solution over K. If the combinatorial problem is infeasible, Hilbert's Nullstellensatz and a large-scale linear algebra computation yields a certificate of infeasibility. Thus, unless P = NP, there must exist an infinite sequence of infeasible instances for each hard combinatorial problem where the minimum-degree of a Hilbert Nullstellensatz infeasibility certificate grows. We show that the minimum-degree of a Nullstellensatz certificate for the non-existence of an independent set of size greater than the size of the largest independent set in the graph is in fact the size of the largest independent set in the graph. Moreover, such a certificate contains at least one term per independent set in G. By contrast, for graph-3-colorability, the Nullstellensatz-Linear Algebra (NulLA) algorithm proves the infeasibility of instances having thousands of nodes and tens of thousands of edges.
Nadia Heninger Recovering cryptographic keys from memory images
In a recent paper, several colleagues and I demonstrated an attack against encrypted disks that involves finding the encryption keys in data that is still left in a computer's RAM after the computer is rebooted. I will discuss the practical and theoretical aspects of finding keys hidden in gigabytes of data, techniques for efficiently
correcting bit errors that might occur in the recovered keys, and some interesting problems suggested by this attack.
Isabelle Stanton Clustering social networks.
Social networks are ubiquitous. The discovery of close-knit clusters in these networks is of fundamental and practical interest. Existing clustering criteria are limited in that clusters typically do not overlap, all vertices are clustered and/or external sparsity is ignored. We introduce a new criterion that overcomes these limitations by combining internal density with external sparsity in a natural way. We develop several algorithms for finding these new clusters.
Part 4: 21:30-22:00
Carmit Hazay Complete Fairness in Secure Two-Party Computation
In the setting of secure two-party computation, two mutually distrusting parties wish to compute some function of their inputs while preserving, to the extent possible, various security properties such as privacy, correctness, and more. One desirable property is fairness, which guarantees that if either party receives its output, then the other party does too. Complete fairness cannot be achieved in general in the two-party setting. The accepted folklore has been that nothing non-trivial can be computed with complete fairness, and the question of complete fairness in secure two-party computation has been treated as closed since the late '80s. In this paper, we demonstrate that this widely held folklore belief is false by showing completely-fair secure protocols for various non-trivial two-party functions including Boolean AND/OR as well as Yao's ``millionaires' problem. Surprisingly, we show that it is even possible to construct completely-fair protocols for certain functions containing an ``embedded XOR, although in this case we also prove a lower bound showing that a super-logarithmic number of rounds are necessary.
Maria-Florina Balcan Item Pricing for Revenue Maximization
We consider the problem of pricing n items to maximize revenue when faced with a series of unknown buyers with complex preferences, and show that a simple pricing scheme achieves surprisingly strong guarantees. We show that in the unlimited supply setting, a random single price achieves expected revenue within a logarithmic factor of the total social welfare for customers with general valuation functions, which may not even necessarily be monotone. This generalizes work of Guruswami et. al~\cite{GHKKKS-05}, who show a logarithmic factor for only the special cases of single-minded and unit-demand customers.
In the limited supply setting, we show that for subadditive valuations, a random single price achieves revenue within a factor of $2^{O(\sqrt{\log{n}\log\log{n}})}$ of the total social welfare, i.e., the optimal revenue the seller could hope to extract even if the seller
could price each bundle differently for every buyer. This is the best approximation known for any item pricing scheme for subadditive (or even submodular) valuations, even using multiple prices. We complement this result with a lower bound showing a sequence of subadditive (in fact, XOS) buyers for which any single price has approximation ratio $2^{\Omega(\log^{1/4} n)}$, thus showing that single price schemes cannot achieve a polylogarithmic ratio.
This lower bound demonstrates a clear distinction between revenue maximization and social welfare maximization in this setting, for which~\cite{DNS-05,D07} show that a fixed price achieves a logarithmic approximation in the case of XOS~\cite{DNS-05}, and more generally subadditive~\cite{D07}, customers.
Katrina Ligett A Learning Theory Approach to Non-Interactive Database Privacy
In this talk, we'll demonstrate that, ignoring computational constraints, it is possible to release privacy-preserving databases that are useful for all queries from any concept class with polynomial VC-dimension. We'll also mention some computationally efficient database privacy results and highlight a number of interesting open problems. Joint work with Avrim Blum and Aaron Roth
Virginia Vassilevska A new combinatorial approach to sparse graph problems
We give a new combinatorial data structure for representing arbitrary Boolean matrices. After a short preprocessing phase, the data structure can perform fast vector multiplications with a given matrix, where the runtime depends on the sparsity of the input vector. The data structure can also return minimum witnesses for the matrix-vector product. Our approach is simple and implementable: the data structure works by precomputing small problems and recombining them in a novel way. It can be easily plugged into existing algorithms, achieving an asymptotic speedup over previous results. As a consequence, we achieve new running time bounds for computing the transitive closure of a graph, all pairs shortest paths on unweighted undirected graphs, and finding a maximum node-weighted triangle. Furthermore, an asymptotic improvement on our algorithms would imply a o(n^3/\log^2 n) combinatorial algorithm for Boolean matrix multiplication, a longstanding open problem in the area.
Joint work with Guy Blelloch and Ryan Williams