# Theory Seminar – MSR-Silicon Valley

### Organizers: Parikshit Gopalan and Guy Rothblum

6/10/2013 Prateek Jain (MSR)

1:30-2:30PM. Please notice unusual day (Monday)!

6/5/2013 *No Talk* (STOC@Stanford)

5/28/2013 *No Talk* (Visions Symposium@Berkeley)

5/21/2013 Daniel Weitzner (MIT)

1:30-2:30PM. Please notice unusual day (Tuesday)!

Real Privacy: Context and Individual Control as the Path to Genuine Privacy Protection for the 21st Century.

Daniel J. Weitzner
Director, Decentralized Information Group
MIT Computer Science and Artificial Intelligence Laboratory

We hear that “your privacy matters to us,” but does anyone really know what that means? As public awareness of privacy grows there is also a growing divergence about what privacy really is. Whether we call privacy a fundamental human right, something that exists in the penumbra of other constitutional rights or a matter of consumer fairness, 20th century implementations of privacy are both unsatisfying for individuals and burdensome for innovators. This is a talk about rediscovering the foundations of privacy: freedom of association, protection from discrimination and limiting the tyranny of large institutions, be they public or private. In returning to privacy basics we see that real privacy is depends little on ‘notice’ but places a high value on respect for context and individual control. Pseudo-contractual notions of ‘choice’ are unhelpful to users, but respect for the context of relationships matters. Formalistic misunderstandings about the differences between US and European privacy frameworks are based on the simplistic view that Europe has ‘more’ privacy and the US has ‘less’, leaving us to believe we can chose privacy levels along a linear scale. In reality, we face a more complex set of technical and legal choices about how to enforce highly nuanced rules in complex information relationships. Finally, secrecy through encryption or barriers to the free flow of information are generally fig-leaves over privacy risks, but accountability for how information is actually used can build a world in which real privacy exists alongside a vibrant, open information society.

5/15/2013 Anupam Gupta (CMU)

How to Run your Chores (and Get to Dinner on Time)

In the orienteering problem, we are given a metric space (the distances are supposed to represent travel times between the locations), a start vertex (“home”) and a deadline B, and want to visit as many points as possible using a tour of length at most B. We know constant-factor approximation algorithms for this problem since the work of Blum et al in 2002.

However, suppose it is not enough for us to visit the nodes: upon reaching a location, we also have to wait for some (random) time at each location before we can get the reward. Each such waiting time is drawn from a known probability distribution. What can we do then? In this talk, we will discuss adaptive and non-adaptive approximation algorithms for this stochastic orienteering problem.

This is based on work with Ravi Krishnaswamy, Viswanath Nagarajan, and R.Ravi.

5/8/2013 Vitaly Feldman (IBM Research, Almaden)

Statistical Algorithms and a Lower Bound for Detecting Planted Cliques

We introduce a framework for proving lower bounds on computational problems over distributions, based on a class of algorithms called statistical algorithms. For such algorithms, access to the input distribution is limited to obtaining an estimate of the expectation of any given function on a sample drawn randomly from the input distribution, rather than directly accessing samples. Most natural algorithms of interest in theory and in practice, e.g., moments-based methods, local search, standard iterative methods for convex optimization, MCMC and simulated annealing, are statistical algorithms or have statistical counterparts. Our framework is inspired by and generalizes the statistical query model in learning theory.

Our main application is a nearly optimal lower bound on the complexity of any statistical algorithm for detecting planted bipartite clique distributions (or planted dense subgraph distributions) when the planted clique has size O(n^(1/2-\delta)) for any constant \delta > 0. Variants of these problems have been assumed to be hard to prove hardness for other problems and for cryptographic applications. Our lower bounds provide concrete evidence of hardness, thus supporting these assumptions.

Joint work with Elena Grigorescu, Lev Reyzin, Santosh Vempala and Ying Xiao

5/1/2013 Chandra Chekuri (University of Illinois, Urbana-Champaign)

Large-Treewidth Graph Decompositions and Applications

Treewidth is a graph parameter that plays a fundamental role in many structural and algorithmic results. We study the problem of decomposing a given graph $G$ into several node-disjoint subgraphs, where each subgraph has sufficiently large treewidth. We prove two theorems on the tradeoff between the number of the desired subgraphs $h$, and the desired lower bound $r$ on the treewidth of each subgraph. The theorems assert that, given a graph $G$ with treewidth $k$, a decomposition with parameters $h,r$ is feasible whenever $hr^2 \le k/\polylog(k)$, or $h^3r \le k/\polylog(k)$ holds.

The decomposition theorems are inspired by the breakthrough work of Chuzhoy on the maximum edge-disjoint paths problem in undirected graphs and follow up work that extended the ideas to node-disjoint paths. The goal of the talk to explain the background for the theorems and their application to routing and to fixed-parameter tractability and Erdos-Posa-type theorems.

The latter applications allow one to bypass the well-known Grid-Minor theorem of Robertson and Seymour. No prior knowledge of treewidth will be assumed.

The decomposition theorems are from a paper joint with Julia Chuzhoy that is to appear in STOC 2013 but the talk is also based on several previous papers on the maximum disjoint paths problem.

4/24/2013 Robert Krauthgamer (Weizmann Institute of Science)

Cutting corners cheaply, or how to remove Steiner points

The main result I will present is that the Steiner Point Removal (SPR) problem can always be solved with polylogarithmic distortion, which resolves in the affirmative a question posed by Chan, Xia, Konjevod, and Richa (2006). Specifically, for every edge-weighted graph $G=(V,E,w)$ and a subset of terminals $T\subset V$, there is a graph only on the terminals, denoted $G’=(T,E’,w’)$, which is a minor of $G$ and the shortest-path distance between any two terminals is approximately equal in $G’$ and in $G$, namely within factor $O(\log^6|T|)$. Our existence proof actually gives a randomized polynomial-time algorithm.

Our proof features a new variant of metric decomposition. It is well-known that every $n$-point metric space $(X,d)$ admits an $O(\log n)$-separating decomposition, which roughly speaking says there is a randomized partitioning of $X$, with a certain bound on the probability of separating any two points $x,y \in X$.  We introduce an additional requirement, which is a tail bound on the following random variable $Z_P$: the number of clusters of the partition that meet any shortest-path $P$ whose length is not too large.

Joint work with Lior Kamma and Huy L. Nguyen

4/17/2013 Yaron Singer (Google / Harvard)

Adaptive Seeding in Social Networks

The rapid adoption of social networking technologies throughout the past decade is bringing special attention to algorithmic and data mining techniques designed for maximizing information cascades in social networks.  Despite the immense progress which has been made in the past decade, due to limited data access and the structure of social networks the application of state-of-the-art techniques often results in poor performance.

In this talk we will introduce a new framework we call adaptive seeding.  The framework is a two-stage model which leverages a phenomenon known as the “friendship paradox” in social networks in order to dramatically increase the spread of information cascades.  Our main result shows constant factor approximations are achievable for the most well-studied models of information spreading in social networks.  The result follows from new techniques and concepts that may be of independent interest for those interested in stochastic optimization and machine learning.

Joint work with Lior Seeman

4/10/2013 Yoram Moses (Technion, on sabbatical at Stanford)

Knowledge as a Window into Distributed Coordination

This talk will review the knowledge-based approach in distributed systems, show a few fundamental connections between knowledge and multi-party coordination, and illustrate how these can provide insight into the interplay between time and communication in enabling coordination. The talk will be self-contained, intended for a general CS audience. The latter part of the talk is based on joint work with Ido Ben Zvi.

3/13/2013 Anupam Datta (CMU)

We introduce quantitative usability and security models to guide the design of password management schemes — systematic strategies to help users create and remember multiple passwords. In the same way that security proofs in cryptography are based on complexity-theoretic assumptions (e.g., hardness of factoring and discrete logarithm), we quantify usability by introducing usability assumptions. In particular, password management relies on assumptions about human memory, e.g., that a user who follows a particular rehearsal schedule will successfully maintain the corresponding memory. These assumptions are informed by research in cognitive science and validated through empirical studies. Given rehearsal requirements and a user’s visitation schedule for each account, we use the total number of extra rehearsals that the user would have to do to remember all of his passwords as a measure of the usability of the password scheme. We also present a security model which accounts for the complexity of password management with multiple accounts and associated threats, including online, offline, and plaintext password leak attacks.

Observing that current password management schemes are either insecure or unusable, we present Shared Cues — a new scheme in which the underlying secret is strategically shared across accounts to ensure that most rehearsal requirements are satisfied naturally while simultaneously providing strong security. The construction uses the Chinese Remainder Theorem in a non-standard manner to achieve these competing goals.

Joint work with Jeremiah Blocki and Manuel Blum at CMU

2/20-3/6/2013: BREAK, no theory seminars are currently planned for these dates.

2/13/2013 Sergiu Hart (Hebrew University)

Dynamics and Equilibrium

An overview of a body of work on dynamical systems in multi-player environments. On the one hand, the natural informational restriction that each participant does not know the payoff functions of the other participants — “uncoupledness” — severely limits the possibilities to converge to Nash equilibria. On the other hand, there are simple adaptive heuristics — such as “regret matching” — that lead in the long run to correlated equilibria, a concept that embodies full rationality. Connections to behavioral economics, neurobiological studies, and engineering, are also mentioned.

1/16/2013 Konstantin Makarychev (MSR Redmond)
Notice Unusual Room: Telstar (usual building, SVC6)

Sorting Noisy Data with Partial Information

I will talk about semi-random models for the Minimum Feedback Arc Set Problem. In the Minimum Feedback Arc Set Problem, we are given a directed graph and our  goal is to remove as few edges as possible to make this graph acyclic. This is a classical optimization problem. The best known approximation algorithm due to Seymour gives O(log n loglog n) approximation in the worst case. I will discuss whether we can do better in the “real-life” than in the worst case. To this end, I will present two models that try to capture “real-life” instances of Minimum Feedback Arc Set. Then,  I will talk in more detail about one of the models. I will give an approximation algorithm that finds a solution of cost (1+epsilon) OPT + n polylog n, where OPT is the cost of the optimal solution.

Joint work with Yury Makarychev (TTIC) and Aravindan Vijayaraghavan (CMU).

1/9/2013 Shafi Goldwasser (MIT and Weizmann Institute)

Pseudo Deterministic Algorithms

We will present a new type of probabilistic algorithm, which we call pseudo-determinisc: they can not be distinguished from deterministic algorithms by a probabilistic polynomial time observer with black box access.

We will show a necessary and sufficient condition for the existence of a such an algorithm, and several examples of Bellagio algorithms which improve on deterministic solutions.

The notion of pseudo-deterministic computations extends beyond sequential polynomial time algorithms, to other domains where the use of randomization is essential such as distributed algorithms and sub-linear algorithms.  We will discuss these extensions.

Fast algorithms for maximizing submodular functions

There has been much progress recently on improved approximations for problems involving submodular objective functions, many interesting techniques have been developed. However, the resulting algorithms are often slow and impractical. In this work we develop general techniques to get very fast approximation algorithms for maximizing submodular functions subject to various constraints. These include speeding up greedy and continuous greedy based algorithms and a new potential function based local search algorithm to handle multiple constraints.

(Based on joint work with Jan Vondrak)

11/28/2012 Ilan Lobel (NYU)

Intertemporal Price Discrimination: Structure and Computation of Optimal Policies

We consider the question of how should a firm optimally set a sequence of prices in order to maximize its long-term average revenue given a continuous flow of strategic customers. In particular, customers arrive over time, are strategic in timing their purchases and are heterogeneous along two dimensions: their valuation for the firm’s product and their willingness to wait before purchasing or leaving.

The customers’ patience and valuation may be correlated in an arbitrary fashion. For this general formulation, we prove that the firm may restrict attention to short cyclic pricing policies, which have length twice the maximum willingness to wait of the customer population. We further establish results on the suboptimality of monotone pricing policies in general, and illustrate the structure of optimal policies. These are, in a typical scenario, characterized by nested sales, where the firm offers partial discounts throughout each cycle, offers a significant discount halfway through the cycle, with the largest discount offered at the end of the cycle. From a computational perspective, we exploit the structure of the underlying problem to develop a novel dynamic programming formulation for the problem that computes an optimal pricing policy in polynomial time (in the maximum willingness-to-wait). We further establish a form of equivalence between the problem of pricing for a stream of heterogeneous strategic customers and pricing for a pool of heterogeneous customers who may stockpile units of the product. Joint work with Omar Besbes (Columbia).

11/9/2012 Elchanan Mossel (U C Berkeley)

Some new proofs of Gaussian and discrete noise stability

I will discuss some new proofs of Borel’s result on Gaussian stability and of Majority is stablest and new applications that follow from these proofs  in hardness of approximation and social choice theory.

11/2/2012  Aravind Srinivasan (University of Maryland)

The Lovasz Local Lemma — constructive and nonconstructive

Abstract: The Lovasz Local Lemma is a powerful probabilistic tool. We start by reviewing the breakthrough by Moser and Tardos on its constructive aspects, connections to other fields, and extensions due to Haeupler, Saha, and the speaker. We will then outline some very recent further extensions, due to David Harris and the speaker, which are nonconstructive thus far.

10/24/2012 No Talk (FOCS)

10/17/2012 Sanjeev Arora (Princeton)

Is Machine Learning Tractable? — Three Vignettes

Please note unusual time (1-2PM at Titan)

Many tasks in machine learning (especially unsupervised learning) are provably intractable: NP-hard or worse. Nevertheless, researchers have developed heuristic algorithms to try to solve these tasks in practice. In most cases, these algorithms are heuristics with no  provable guarantees on their running time or on the quality of solutions they return.  Can we change this state of affairs?

This talk will suggest that the answer is yes, and describe three of our recent works as illustration. (a) A new algorithm for learning topic models. (It applies to Linear Dirichlet Allocations of Blei et al. and also to more general topic models. It provably works under some reasonable assumptions and in practice is up to 50 times faster than existing software like Mallet. It relies upon a new procedure for nonnegative matrix factorization.) (b) What classifiers are worth learning? (Can theory illuminate the contentious question of what binary classifier to learn: SVM, Decision tree, etc.) (c) Provable ICA with unknown gaussian noise. (An algorithm to provably learn a “manifold” with small number of parameters but exponentially many “interesting regions.”)

(Based upon joint works with Rong Ge, Ravi Kannan, Ankur Moitra, Sushant Sachdeva.)

10/10/2012 Grigory Yaroslavtsev (Penn State)

Learning and testing submodular functions

Submodular functions capture the law of diminishing returns and can be viewed as a generalization of convexity to functions over the Boolean cube. Such functions arise in different areas, such as combinatorial optimization, machine learning and economics. In this talk we will focus on positive results about learning such functions from examples and testing whether a given function is submodular with a small number of queries.

For the class submodular functions taking values in discrete integral range of size R we show a structural result, giving concise representation for this class. The representation can be described as a maximum over a collection of threshold functions, each expressed by an R-DNF formula. This leads to efficient PAC-learning algorithms for this class, as well as testing algorithms with running time independent of the size of the domain.

Joint work with Sofya Raskhodnikova and Rocco Servedio

10/5/2012, 11AM, Fred Cate (Indiana University Maurer School of Law)

Big Data in Healthcare: The Future of Healthcare Innovation and the Regulations that Will Kill It

Please note unusual day (Friday) and time (11AM)

Personal information is increasingly recognized as the most critical resource for healthcare treatment, research, and management. While healthcare providers generate large amounts of information associated with patient interactions, far more health information, including genetic and behavioral data, are now being generated directly by individuals and as a result of individuals’ interactions with home healthcare and mobile devices, social media sites, and personal health records. These data are critical to the transformation of healthcare and the evolution of truly personalized medicine, yet privacy law imposes an inexplicably restrictive and inconsistent approach to their use. For the past three years, a blue-ribbon panel of medical practitioners and researchers, ethicists, lawyers, technologists, and privacy experts, funded by the NIH, have worked to craft an alternative approach to protecting privacy while facilitating medical research, to try to eliminate the threats posed by privacy regulations to health and privacy today and to the future of medical innovation tomorrow.

Fred H. Cate is a Distinguished Professor and C. Ben Dutton Professor of Law at the Indiana University Maurer School of Law. He is managing director of the Center for Law, Ethics, and Applied Research in Health Information and director of the Center for Applied Cybersecurity Research (a National Center of Academic Excellence in both Information Assurance Research and Information Assurance Education).  A member of Microsoft’s Trustworthy Computing Academic Advisory Board, Cate serves on numerous government and industry advisory and oversight committees, and testifies frequently before congressional committees on information privacy and security issues. He is the author of more than 150 articles and books and is one of the founding editors of the Oxford University Press journal, International Data Privacy Law. He is the PI on the NIH grant “Protecting Privacy in Health Research.”

9/19/2012 Zvika Brakerski (Stanford)

Efficient Interactive Coding Against Adversarial Noise

We study the problem of constructing interactive protocols that are robust to noise, a problem that was originally considered in the seminal works of Schulman (FOCS ’92, STOC ’93), and has recently regained popularity. Robust interactive communication is the interactive analogue of error correcting codes: Given an interactive protocol which is designed to run on an error-free channel, construct a protocol that evaluates the same function (or, more generally, simulates the execution of the original protocol) over a noisy channel. As in (non-interactive) error correcting codes, the noise can be either stochastic, i.e. drawn from some distribution, or adversarial, i.e. arbitrary subject only to a global bound on the number of errors.

We show how to efficiently simulate any interactive protocol in the presence of constant-rate adversarial noise, while incurring only a constant blow-up in the communication complexity ($\cc$). Our simulator is randomized, and succeeds in simulating the original protocol with probability at least $1-2^{-\Omega(\cc)}$. Prior works could not achieve efficient simulation in the adversarial case.

Joint work with Yael Tauman Kalai

9/12/2012 Moritz Hardt (IBM Almaden)

Incoherence and privacy in spectral analysis of data

Matrix incoherence is a frequently observed property of large real-world matrices. Intuitively, the coherence of a matrix is low if the singular vectors of the matrix bear little resemblance to the individual rows of the matrix. We show that this property is quite useful in the design of differentially private approximate singular vector computation and low-rank approximation.

Our algorithms for these tasks turn out to be significantly more accurate under a low coherence assumption than what a well known worst-case lower bound would suggest. While not straightforward to analyze, our algorithms are highly efficient and easy to implement. We complement our theoretical results with several experiments on real and synthetic data.

Based on joint works with Aaron Roth

9/5/2012 Brendan Lucier (MSR-NE)

Stable Pricing and Partitions

In a combinatorial auction, a seller has m items to sell and n buyers willing to purchase, where each buyer has a value for each subset of the items.  In general such auctions are complex, with specification of bids and determination of optimal allocations having exponential complexity in n and/or m.  In some special cases (e.g. the “gross substitutes” condition) there exist ways to set prices on the items for sale so that a socially efficient outcome occurs when each buyer takes his most-preferred set.  Such a wonderful pricing outcome is known as a Walrasian Equilibrium (WE), but unfortunately a WE does not always exist in general.

In this talk I will present some new results (joint with Michal Feldman and Nick Gravin) in which we relax the concept of a pricing equilibrium to the combinatorial setting.  The essential feature of our relaxation is the ability for the seller to pre-partition the items prior to sale, then price the resulting bundles.  I will describe some of the properties of this notion and some of the algorithmic problems that arise and solutions we provide.  In particular, for general buyer values, we give a black-box reduction that converts an arbitrary allocation into such a “stable partition pricing” outcome with only a constant factor loss in social welfare.

8/29/2012 Noam Nisan (MSR SV)

Should Auctions Be Complex?

We consider the menu-size of an auction as a complexity measure and ask whether simple auctions suffice for obtaining high revenue.  For the case of one item and IID bidders, Myerson shows that the answer is “yes”:  the revenue-maximizing auction has a  single deterministically chosen reserve price.  For two (or more) items we show that the answer is “no”: complex auctions can yield infinitely more revenue than simple ones, even for a single bidder with an additive valuation.  However, when the bidder’s values for the two items are independently distributed,  the answer is “approximately yes”:  selling each of two items simply and separately yields at least half the revenue of any auction.

Joint work with Sergiu Hart

8/22/2012 Shiri Chechik (MSR SV)

Fully Dynamic Approximate Distance Oracles for Planar Graphs via Forbidden-Set Distance Labels

Distance oracle is a data structure that provides fast answers to distance queries. Recently, the problem of designing distance oracles capable of answering restricted distance queries, that is, estimating distances on a subgraph avoiding some forbidden vertices, has attracted a lot of attention. In this talk, we will consider forbidden set distance oracles for planar graphs. I’ll present an efficient compact distance oracle that is capable of handing any number of failures.

In addition, we will consider a closely related notion of fully dynamic distance oracles. In the dynamic distance oracle problem instead of getting the failures in the query phase, we rather need to handle an adversarial online sequence of update and query operations. Each query operation involves two vertices s and t whose distance needs to be estimated. Each update operation involves inserting/deleting a vertex/edge from the graph.

I’ll show that our forbidden set distance oracle can be tweaked to give fully dynamic distance oracle with improved bounds compared to the previously known fully dynamic distance oracle for planar graphs.

Based on a joint work with Ittai Abraham and Cyril Gavoille

8/15/2012 Raghu Meka (IAS)

Constructive discrepancy minimization by walking on the edges.

Minimizing the discrepancy of a set system is a fundamental problem in combinatorics. One of the cornerstones in this area is the celebrated six standard deviations result of Spencer (AMS 1985): In any system of n sets in a universe of size n, there always exists a coloring which achieves discrepancy 6\sqrt{n}. The original proof of Spencer was existential in nature, and did not give an efficient algorithm to find such a coloring. Recently, a breakthrough work of Bansal (FOCS 2010) gave an efficient algorithm which finds such a coloring. His algorithm was based on an SDP relaxation of the discrepancy problem and a clever rounding procedure.

In this work we give a new randomized algorithm to find a coloring as in Spencer’s result based on a restricted random walk we call “Edge-Walk”. Our algorithm and its analysis use only basic linear algebra and is “truly” constructive in that it does not appeal to the existential arguments, giving a new proof of Spencer’s theorem and the partial coloring lemma.

Joint work with Shachar Lovett.

8/8/2012 Rocco Servedio (Columbia)

Inverse Problems for Power Indices in Weighted Voting Games

Suppose we must design a weighted voting scheme to be used by n voters to choose between two candidates.  We want the i-th voter to have a certain prescribed amount of “influence” over the final outcome of the vote — for example, the voters may correspond to states with different populations, or shareholders who hold different numbers of shares in a company.  How can we design a weighted voting scheme that gives each voter the prescribed amount of influence?

Of course, in order to even hope to answer such a question we need a well-defined notion of the influence of a voter in a weighted voting scheme. Many such measures of influence have been studied in the voting theory literature; such measures are sometimes called “power indices.” In this talk we’ll consider two of the most popular power indices:  the “Banzhaf indices” (known in theoretical computer science as “Chow Parameters”) and the “Shapley-Shubik indices.” These are two quite different natural ways of of quantifying how much influence each voter has in a given weighted voting scheme.

As our main results, we’ll describe algorithms that solve the inverse problem of designing a weighted voting scheme for each of these power indices. Specifically,

(1) Given a vector of desired Banzhaf indices for the n voters, our first algorithm efficiently constructs a weighted voting scheme which has Banzhaf indices very close to the target indices (if any such weighted voting scheme exists).  Our result gives an almost doubly exponential (in terms of the closeness parameter) running time improvement over the only previous provably correct solution.

(2) Given a vector of desired Shapley-Shubik indices, our second algorithm efficiently constructs a weighted voting scheme which has Shapley-Shubik indices very close to the target indices (if any such weighted voting scheme exists).  This is the first algorithm for this problem with a poly(n) as opposed to exp(n) runtime.

A common algorithmic ingredient underlies these two results, but the structural results used to prove correctness are very different for the two indices.  Our results for Banzhaf indices are based on structural properties of linear threshold functions and geometric and linear-algebraic arguments about how hyperplanes interact with the Boolean hypercube.  Our results for Shapley-Shubik indices are based on anticoncentration bounds for sums of non-independent random variables.

No background in voting theory is required for the talk.

Based on joint works with Anindya De, Ilias Diakonikolas and Vitaly Feldman.

8/1/2012 Avi Wigderson (IAS Princeton)

Restriction Access, Population Recovery, and Partial Identification

We study several natural problems in which an unknown distribution over an unknown population of vectors needs to be recovered from partial or noisy samples. Such problems naturally arise in a variety of contexts in learning, clustering, statistics, data mining and database privacy, where loss and error may be introduced by nature, inaccurate measurements, or on purpose. We give fairly efficient algorithms to recover the data under fairly general assumptions, when loss and noise are close to the information theoretic limit (namely, nearly completely obliterate the original data).

Underlying one of our algorithms is a new structure we call a partial identification (PID) graph. While standard IDs are subsets of features (vector coordinates) that uniquely identify an individual in a population, partial IDs allow ambiguity (and “imposters”), and thus can be shorter. PID graphs capture this imposter-structure. PID graphs yield strategies for dimension reductions of recovery problems, and the re-assembly of this local pieces of statistical information to a global one. The combinatorial heart of this work is proving that every set of vectors admits partial IDs with “cheap” PID graphs (and hence efficient recovery). We further show how to find such near-optimal PIDs efficiently.

Time permitting, I will also describe our original motivation for studying these recovery problems above: a new learning model we call “restriction access”. This model aims at generalizing prevailing “black-box” access to functions when trying to learn the “device” (e.g.circuit, decision tree, polynomial…) which computes them. We propose a “grey-box” access that allows certain partial views of the device, obtained from random restrictions. Our recovery algorithms above allow positive learning results for the PAC-learning analog of our model, for such devices as decision trees and DNFs, which are currently beyond reach in the standard “black-box” version of PAC-learning.

Based on joint works with Zeev Dvir, Anup Rao and Amir Yehudayoff.

7/25/2012 Abhradeep Guha Thakurta (Pennsylvania State University)

Differentially Private Empirical Risk Minimization and High-dimensional Regression

In the recent past there have been several high-profile privacy breaches on machine learning based systems which satisfied various ad-hoc notions of privacy. Some of the examples being: attack on Amazon recommendation system by Calandrino et al. in 2011, attack on Facebook advertisement system by Korolova in 2011 etc. With these breaches in place, an obvious question that arises is “How can we design learning algorithms with rigorous privacy guarantees?”

In this talk, I will focus on designing convex empirical risk minimization (ERM) algorithms (a special class of learning algorithms) with differential privacy guarantees. In the recent past, differential privacy has emerged as one of the most commonly used rigorous notions of privacy.

My talk will be logically segregated into two parts:

Part a) Private ERM on offline data sets: In this part, I will discuss about various approaches for differentially private ERM when the complete data set is available at once (as opposed to the online setting, which I will consider in the next part). One of my main focuses in this part will be to discuss two of our new approaches towards private ERM in the offline setting: i)Improved objective perturbation algorithm (which is an improvement of the initial algorithm proposed by Chaudhuri et al. in 2008 and 2011) and ii) Online convex programming (OCP) based algorithm. Additionally, I will discuss about our first private ERM algorithms in high-dimensions (i.e., where the number of data elements is much lesser than the dimensionality of the underlying model parameter).

Part b) Private Online Learning: Online learning involves learning from private data in real-time, due to which the learned model as well as its predictions are continuously changing. We study the problem in the framework of online convex programming (OCP) while preserving differential privacy. For this problem, we provide a generic framework that can be used to convert any given OCP algorithm into its private variant while preserving privacy as well as sub-linear regret, provided that the given OCP algorithm satisfies the following two criteria:  1) linearly decreasing sensitivity, i.e., the effect of the new data points on the learned model decreases linearly, and 2) sub-linear regret. We instantiate our framework with two commonly used OCP algorithms: i) Generalized Infinitesimal Gradient Ascent (GIGA) and ii) Implicit Gradient Descent (IGD).

Joint work with Prateek Jain [MSR, India], Daniel Kifer [Penn State], Pravesh Kothari [University of Texas, Austin] and Adam Smith [Penn State].

7/18/2012 Alex Samorodnitsky (Hebrew University, Jerusalem)

Discrete tori and bounds for linear codes.

Let C be a linear subspace of the Hamming cube H. Let C’ be the dual code. Following Friedman and Tillich we try to estimate the rate of growth of metric balls in the discrete “torus” T = H/C’ and use this to upperbound the cardinality of T, and therefore of C.

A notion of discrete Ricci curvature of metric spaces, as defined by Ollivier, turns out to be useful in the cases where C’ has local structure (that is C is locally correctable / locally testable).

This approach leads to different (and, we would like to think, easier) proofs of some known upper bounds and to some occasional improvements in the bounds.

Joint work with Eran Iceland.

7/11/2012 Aviv Zohar (MSR SVC)

Critiques of Game Theory

Can game theorists predict social and political outcomes successfully? Should we listen when a game theorist argues that Israel should attack Iran to prevent it from obtaining nuclear weapons? How useful has game theory been in designing interactions? Do computers help somehow? In this talk I’d like to survey criticisms of Game Theory’s practical applicability. The talk will be non-technical and will assume only basic knowledge of concepts from Game Theory.

7/4/2012 No seminar (holiday)

6/27/2012 No seminar (intern-mentor baseball game)

6/20/2012 Piotr Indyk (MIT)

Faster Algorithms for Sparse Fourier Transform

The Fast Fourier Transform (FFT) is one of the most fundamental numerical algorithms. It computes the Discrete Fourier Transform (DFT) of an n- dimensional signal in O(n log n) time. The algorithm plays an important role in many areas.

In many applications (e.g., audio, image or video compression), most of the Fourier coefficients of a signal are “small” or equal to zero, i.e., the output of the transform is (approximately) sparse. In this case, there are algorithms that enable computing the non-zero coefficients faster than the FFT. However, in practice, the exponents in the runtimes of these algorithms and their complex structure have limited their applicability to very sparse signals.

In this talk, I will describe a new set of algorithms for sparse Fourier Transform. Their key feature is simplicity, which leads to efficient running times with low overhead, both in theory and in practice. One of those algorithms achieves a runtime of O(k log n), where k is the number of non-zero Fourier coefficients of the signal. This improves over the runtime of the FFT for any k = o(n).

Joint work with Haitham Hassanieh, Dina Katabi and Eric Price

6/13/2012 Guy Rothblum (MSR SVC)

How to Compute in the Presence of Leakage

We address the following problem: how to execute any algorithm, for an unbounded number of executions, in the presence of an attacker who gets to observe partial information on the internal state of the computation during executions. This general problem has been  addressed in the last few years with varying degrees of success. It is important for running cryptographic algorithms in the presence of side-channel attacks, as well as for running non-cryptographic algorithms, such as a proprietary search algorithm or a game, on a cloud server where parts of the execution’s internals might be observed.

In this work, we view algorithms as running on a leaky CPU. In each (sub)-computation run on the CPU, we allow the adversary to observe the output of an arbitrary and adaptively chosen length-bounded function on the CPU’s input, output, and randomness.

Our main result is a general compiler for transforming any algorithm into one that is secure in the presence of this family of partial observation attacks (while maintaining the algorithm’s functionality). This result is unconditional, it does not rely on any secure hardware components or cryptographic assumptions.

Joint work with Shafi Goldwasser

6/6/2012 Jasmin Fisher  (MSR Cambridge)

From Coding the Genome to Algorithms Decoding Life

The decade of genomic revolution following the human genome’s sequencing has produced significant medical advances, and yet again, revealed how complicated human biology is, and how much more remains to be understood. Biology is an extraordinary complicated puzzle; we may know some of its pieces but have no clue how they are assembled to orchestrate the symphony of life, which renders the comprehension and analysis of living systems a major challenge. Recent efforts to create executable models of complex biological phenomena – an approach we call Executable Biology – entail great promise for new scientific discoveries, shading new light on the puzzle of life. At the same time, this new wave of the future forces computer science to stretch far and beyond, and in ways never considered before, in order to deal with the enormous complexity observed in biology. This talk will focus on our recent success stories in using formal methods to model cell fate decisions during development and cancer, and on-going efforts to develop dedicated tools for biologists to model cellular processes in a visual-friendly way.

5/29/2012 Madhu Sudan (MSR New England)

TBA. Note Unusual Day and Time (Tuesday 11am-12pm)

5/23/2012 No Seminar (stoc week)

5/16/2012 Edith Cohen (AT&T)

Title: How to Get the Most out of Your Sampled Data

Random sampling is an  important tool for retaining the ability to query data under resource limitations. It is used to summarize data too large to store or manipulate and meet resource constraints on bandwidth or battery power.  Estimators that are applied to the sample provide fast approximate answers to queries posed over the original data and the value of the sample hinges on the quality of these estimators.

We are interested in queries, such as maximum or range, that span multiple data points.  Sum aggregates of these queries correspond to distinct counts and difference norms and are used for planning or change/anomaly detection over traffic logs and measurement data.  Unbiased estimators are particularly effective — While the estimate of each basic query inevitably has high variance, the relative error decreases with aggregation.

The sample may provide no information, exact value, or partial information on the queried value.  The Horvitz-Thompson estimator, known to minimize variance for sampling with “all or nothing” outcomes (which reveal the exact or no information on the queried value), is not optimal or altogether inapplicable to such queries.

We present a general principled methodology for the derivation of (Pareto) optimal nonnegative unbiased estimators over sampled data and aim to understand its potential.  We demonstrate significant improvement in estimation accuracy.

This work is joint with Haim Kaplan (Tel Aviv University).

5/9/2012 Andrew Drucker (MIT)

New Limits to Instance Compression for Hard Problems

Given an instance of a decision problem that is too difficult to solve outright, we may aim for the more limited goal of compressing that instance into a smaller, equivalent instance of the same or a different problem.  Studying the power and limits of instance compression involves an intriguing interplay between computational and information-theoretic ideas.

As a representative problem, say we are given a Boolean formula Psi over n variables, and of size m >> n, and we want to determine if Psi is satisfiable.  Can we efficiently reduce this question to an equivalent problem instance of size poly(n), independent of m?  Harnik and Naor (FOCS ’06) and Bodlaender et al. (ICALP ’08) showed that this question has important connections to cryptography and to fixed-parameter tractability theory.  Fortnow and Santhanam (STOC ’08) gave a negative answer for deterministic compression, assuming that NP is not contained in coNP/poly.

We will describe new and improved evidence against efficient instance compression schemes.  Our method applies to probabilistic compression for SAT, and also gives the first evidence against deterministic compression for a number of problems.  To prove our results, we exploit the information bottleneck of an instance compression scheme, using a new method to “disguise” information being fed into a compressive mapping.

5/2/2012 Matthew Weineberg (MIT)

Optimal Multi-Dimensional Mechanism Design: Reducing Revenue to Welfare Maximization

We provide a reduction from revenue maximization to welfare maximization in multi-dimensional Bayesian combinatorial auctions with arbitrary (possibly

combinatorial) feasibility constraints and independent additive bidders with arbitrary (possibly combinatorial) demand constraints, appropriately extending Myerson’s single-dimensional result [Myerson81] to this setting. We show that every feasible Bayesian auction can be implemented as a distribution over virtual VCG allocation rules. A virtual VCG allocation rule has the following simple form: Every bidder’s bid vector v_i is transformed into a virtual bid vector f_i(v_i), via a bidder-specific function. Then, the allocation maximizing virtual welfare is chosen. Using this characterization, we show how to find and run the revenue-optimal auction given only black box access to an implementation of the VCG allocation rule. We generalize this result to arbitrarily correlated bidders, introducing the notion of a second-order VCG allocation rule.

We obtain our reduction from revenue to welfare optimization via two algorithmic results on reduced form auctions in settings with arbitrary feasibility and demand constraints. First, we provide a separation oracle for determining feasibility of a reduced form auction. Second, we provide a geometric algorithm to decompose any feasible reduced form into a distribution over virtual VCG allocation rules. In addition, we show how to approximately execute both algorithms computationally efficiently given only black box access to an implementation of the VCG allocation rule, providing two fully polynomial-time randomized approximation schemes (FPRASs). With high probability, the separation oracle is correct on all points that are eps-away from the boundary of the set of feasible reduced forms (in the infinity-norm), and the decomposition algorithm returns a distribution over virtual VCG allocation rules whose reduced form is within eps (in the infinity-norm) of any given feasible reduced form that is eps-away from the boundary.

Our mechanisms run in time polynomial in the number of bidder types and not type profiles. This running time is always polynomial in the number of bidders, and scales with the cardinality of the support of each bidder’s value distribution. The running time can be improved to polynomial in both the number of bidders and number of items in item-symmetric settings by making use of results from [Daskalakis-Weinberg 12].

Joint work with Yang Cai and Costis Daskalakis.

4/25/2012 Or Meir. (Stanford).

Combinatorial Construction of Locally Testable Codes

An error correcting code is said to be locally testable if there is a test that can check whether a given string is a codeword of the code, or rather far from the code, by reading only a constant number of symbols of the string. Locally Testable Codes (LTCs) were first explicitly studied by Goldreich and Sudan (J. ACM 53(4)) and since then several constructions of LTCs were suggested.

While the best known construction of LTCs achieves very efficient parameters, it relies heavily on algebraic tools and on PCP machinery. We present a new and arguably simpler construction of LTCs that matches the parameters of the best known construction while not relying on either heavy algebra or PCP machinery. However, our construction is a probabilistic one.

4/18/2012 Shayan Oveis Gharan (Stanford).

Multi-way Spectral Partitioning and Higher-Order Cheeger Inequalities.

A basic fact in algebraic graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue zero in the Laplacian matrix of the graph. In particular, the graph is disconnected if and only if there are at least two eigenvalues equal to zero. Cheeger’s inequality and its variants provide an approximate version of the latter fact; they state that a graph has a sparse cut if and only if there are at least two eigenvalues that are close to zero.

In this talk I show an analogous characterization holds for higher multiplicities, i.e.,  there are k eigenvalues close to zero if and only if the vertex set can be partitioned into k subsets, each defining a sparse cut. Our result also provides a theoretical justification for clustering algorithms that use the bottom k eigenvectors to embed the vertices into R^k, and then apply geometric considerations to the embedding. Our techniques also yield a nearly optimal tradeoff between the expansion of sets of size~n/k, and the k-th smallest eigenvalue of the normalized Laplacian matrix.

Based on a joint work with James R. Lee, and Luca Trevisan.

4/11/2012 Jan Vondrak (IBM Almaden).

Hardness of randomized truthful mechanisms for combinatorial auctions.

The problem of combinatorial auctions is one of the basic questions in algorithmic mechanism design: how can we allocate m items to n agents with private valuations of different combinations of items, so that the agents are motivated to reveal their true valuations and the outcome is (approximately) optimal in terms of social welfare? While approximation algorithms exist for several non-trivial classes of valuations, they typically do not motivate agents to report truthfully. The classical VCG mechanism, although truthful, is not computationally efficient. Thus the main question is whether the requirements of truthfulness and computational efficiency can be combined, or whether they are incompatible.

We identify a class of explicit (succinctly represented) submodular valuations, for which it is known that combinatorial auctions without the requirement of truthfulness admit a (1-1/e)-approximation; however, we prove that unless NP \subset P/poly, there is no truthful (even truthful-in-expectation) mechanism for this class providing approximation better than polynomial in the number of agents. (Previous work by Dobzinski already ruled out deterministic and universally truthful mechanisms for submodular valuations given by a value oracle.)

Joint work with Shaddin Dughmi and Shahar Dobzinski.

4/4/2012 No Seminar.

3/28/2012 1:30-2:30 Justin Thaler (Harvard)

Practical Verified Computation with Streaming Interactive Proofs

A potential problem in outsourcing work to commercial cloud computing services is trust. If we store a large data set with a service provider, and ask them to perform a computation on that data set — for example, to compute the eigenvalues of a large graph, or to compute a linear program on a large matrix derived from a database — how can we know the computation was performed correctly? Obviously we don’t want to compute the result ourselves, and we might not even be able to store all the data locally. This leads to new problems in the streaming paradigm: we consider a streaming algorithm (modeling a user with limited memory and computational resources) that can be assisted by a powerful helper (the service provider). The goal of the service provider is to not only provide the user with answer, but to convince the user the answer is correct.

In this talk, I will give a unified overview of a recent line of work exploring the application of proof systems to problems that are streaming in nature. In all of these protocols, an honest service provider can always convince the data owner that the answer is correct, while a dishonest prover will be caught with high probability. The protocols I will discuss utilize and extend powerful ideas from communication complexity and the theory of interactive proofs, and I will argue that many are highly practical, achieving millions of updates per second and requiring little space and communication.

Joint work with Amit Chakrabarti, Graham Cormode, Andrew McGregor, Michael Mitzenmacher, and Ke Yi

3/21/2012 1:30-2:30 Mehrdad Nojoumian (University of Waterloo)

Secret Sharing Based on the Social Behaviors of Players

Initially, a mathematical model for “trust computation” in social networks is provided. Subsequently, the notion of a “social secret sharing scheme” is introduced in which shares are allocated based on a player’s reputation and the way she interacts with other parties. In other words, this scheme renews shares at each cycle without changing the secret, and allows trusted parties to gain more authority.

Finally, a novel “socio-rational secret sharing” scheme is proposed in which rational foresighted players have long-term interactions in a social context, i.e., players run secret sharing while founding and sustaining a trust network. To motivate this, consider a repeated game such as sealed-bid auctions. If we assume each party has a reputation value, we can then penalize (or reward) players who are selfish (or unselfish) from game to game. This social reinforcement stimulates players to be cooperative.

3/14/2012 1:30-2:30 Venkatesan Guruswami (Carnegie Mellon University)

Lasserre hierarchy, higher eigenvalues, and graph partitioning

Partitioning the vertices of a graph into two (roughly) equal parts to minimize the weight of edges cut is a fundamental optimization problem, arising in diverse applications. Despite intense research, there remains a huge gap in our understanding of the approximability of these problems: the best algorithms achieve a super-constant approximation factor, whereas even a factor 1.1 approximation is not known to be NP-hard.

We describe an approximation scheme for various graph partitioning problems such as sparsest cut, minimum bisection, and small set expansion. Specifically, we give an algorithm running in time n^{O_epsilon(r)} with approximation ratio (1+epsilon)/min(1,lambda_r), where lambda_r is the r’th smallest eigenvalue of the normalized graph Laplacian matrix. This perhaps indicates why even showing very weak hardness for these problems has been elusive, since the reduction must produce hard instances with slowly growing spectra.

Our algorithm is based on a rounding procedure for semidefinite programming relaxations from a strong class called the Lasserre hierarchy. The analysis uses bounds for low-rank approximations of a matrix in Frobenius norm using columns of the matrix.

Our methods apply more broadly to optimizing certain Quadratic Integer Programming problems with positive semidefinite objective functions and global linear constraints. This framework includes other notorious problems such as Unique Games, which we again show to be easy when the normalized Laplacian doesn’t have too many small eigenvalues.

Joint work with Ali Kemal Sinop.

3/7/2012 – Cancled (TechFest)

2/29/2012 1:30-2:30 Parikshit Gopalan (MSR-SVC)

The Short Code

The Long Code plays a crucial role in our understanding of the approximability of NP-hard problems. True to its name however, it is rather long. We construct a shorter code which enjoys many of the desirable properties of the Long code and can replace it in some scenarios.

The Short Code is derived from an explicit construction of a graph with several large eigenvalues which is nevertheless a good small-set expander. This answers a question raised by Arora, Barak and Steurer. We present a general recipe for constructing small-set expanders from certain locally testable codes.

Joint work with Boaz Barak, Johann Hastad, Raghu Meka, Prasad Raghavendra and David Steurer.

2/22/2012 1:30-2:30 Aleksander Madry (MSR New-England)

Online Algorithms and the K-server Conjecture

Traditionally, in the problems considered in optimization, one produces the solution only after the whole input is made available. However, in many real-world scenarios the input is revealed gradually, and one needs to make irrevocable decisions along the way while having only partial information on the whole input. This motivates us to develop models that allow us to address such scenarios.

In this talk, I will consider one of the most popular approaches to dealing with uncertainty in optimization: the online model and competitive analysis; and focus on a central problem in this area: the k-server problem. This problem captures many online scenarios – in particular, the widely studied caching problem – and is considered by many to be the “holy grail” problem of the field.

I will present a new randomized algorithm for the k-server problem that is the first online algorithm for this problem that achieves polylogarithmic competitiveness.

Based on joint work with Nikhil Bansal, Niv Buchbinder, and Joseph (Seffi) Naor.

2/15/2012 1:30-2:30 Dorothea Wagner (Karlsruhe Institute of Technology)

Algorithm Engineering for Graph Clustering

Graph clustering has become a central tool for the analysis of networks in general, with applications ranging from the field of social sciences to biology and to the growing field of complex systems. The general aim of graph clustering is to identify dense groups in networks. Countless formalizations thereof exist, among those the widespread measure modularity. However, the overwhelming majority of algorithms for graph clustering relies on heuristics, e.g., for some NP-hard optimization problem, and do not allow for any structural guarantee on their output. Moreover, most networks in the real world are not static but evolve over the time, and so do their group structures.

The lecture will focus on algorithmic aspects of graph clustering, especially on quality measures and algorithms that are based on the intuition of identifying as clusters dense subgraphs that are loosely connected among one another. We will discuss different quality measures, in particular the quality index modularity, and present an algorithm engineering approach for modularity maximization and related problems.

2/9/2012 10:30-11:30 Michael Kapralov (Stanford)

Algorithms for Bipartite Matching Problems with Connections to Sparsification and Streaming

The need to process massive modern data sets necessitates rethinking of some classical algorithmic solutions from the point of view of modern data processing architectures. Over the past years sparsification has emerged as an important primitive in the algorithmic toolkit for graph algorithms that allows one to obtain a small space representation that approximately preserves some useful properties of the graph. This talk is centered around two topics. First, we give new algorithms for some bipartite matching problems, which use both sparsification and random walks in novel ways. Second, we give efficient algorithms for constructing sparsifiers on modern computing platforms.

In the first part of the talk we consider the problem of finding perfect matchings in regular bipartite graphs, a classical problem with applications to edge-colorings, routing and scheduling. A sequence of improvements over the years have culminated in a linear-time algorithm. We use both sparsification and random walks to obtain efficient sublinear time algorithms for the problem. In particular, we give an algorithm that recovers a perfect matching in O(n log n) time, where n is the number of vertices in the graph, when the graph is given in adjacency array representation. The runtime is within O(log n) of output complexity, essentially closing the problem. Our approach also yields extremely efficient and easy to implement algorithms for edge-coloring bipartite multigraphs and computing the Birkhoff-von-Neumann decomposition of a doubly-stochastic matrix.

In the second part of the talk we describe an efficient algorithm for single pass graph sparsification in distributed stream processing systems such as Twitter’s recently introduced Storm. We also present a novel approach to obtaining spectral sparsifiers, based on a new notion of distance between nodes in a graph related to shortest path distance on random samples of the graph.

Finally, in the last part of the talk we introduce and study a notion of sparsification relevant to matching problems in general graphs, and show applications to the problem of approximating maximum matchings in a single pass in the streaming model.

1/26/2012 10:30-11:30 Gregory Valiant (UC Berkeley)

Algorithmic Solutions to Some Statistical Questions

I will discuss three classical statistical problems for which the computational perspective unlocks insights into the fundamental nature of these tasks, and suggests new approaches to coping with the increasing size of real-world datasets.

The first problem is recovering the parameters of a mixture of Gaussian distributions. Given data drawn from a single Gaussian distribution, the sample mean and covariance of the data trivially yield good estimates of the parameters of the true distribution; if, however, some of the data points are drawn according to one Gaussian, and the rest of the data points are drawn according to a different Gaussian, how can one recover the parameters of each Gaussian component? This problem was first proposed by Pearson in the 1890′s, and, in the last decade, was revisited by computer scientists. In a pair of papers with Adam Kalai and Ankur Moitra, we established that both the sample complexity, and computational complexity of this problem are polynomial in the relevant parameters (the dimension, and the inverse of the desired accuracy).

The second problem, investigated in a series of papers with Paul Valiant, considers the tasks of estimating a broad class of statistical properties, which includes entropy, L_k distances between pairs of distributions, and support size. There are several implications of our results, including resolving the sample complexity of the distinct elements problem’ (i.e. given a data table with n rows, how many random rows must one query to accurately estimate the number of distinct rows?). We show that on the order of n/log n rows is both necessary, and sufficient, improving significantly on both the prior upper and lower bounds for this problem.

Finally I’ll describe some new bounds for the problem of learning noisy juntas (and parities). Roughly, this problem captures the task of determining the relevant’ variables—for example, given a large table with columns representing the expression of many different genes, and one final column representing the incidence of some medical condition, how can one efficiently find the (possibly small) subset of genes that is relevant to predicting the condition?

1/25/2012 1:30-2:30 Virginia Vassilevska Williams (UC Berkeley)

Multiplying Matrices Faster than Coppersmith-Winograd

In 1987 Coppersmith and Winograd presented an algorithm to multiply two n by n matrices using O(n^{2.3755}) arithmetic operations. This algorithm has remained the theoretically fastest approach for matrix multiplication for 24 years. We have recently been able to design an algorithm that multiplies n by n matrices and uses at most O(n^{2.3727}) arithmetic operations, thus improving the Coppersmith-Winograd running time.

The improvement is based on a recursive application of the original Coppersmith-Winograd construction, together with a general theorem that reduces the analysis of the algorithm running time to solving a nonlinear constraint program. The final analysis is then done by numerically solving this program. To fully optimize the running time we utilize an idea from independent work by Stothers who claimed an O(n^{2.3737}) runtime in his Ph.D. thesis.

The aim of the talk will be to give some intuition and to highlight the main new ideas needed to obtain the improvement.

1/24/2012 10:30-11:30 Roy Schwartz (Technion Israel Institute of Technology)

Submodular Maximization

The study of combinatorial problems with a submodular objective function has attracted much attention in recent years, and is partly motivated by the importance of such problems to economics, algorithmic game theory and combinatorial optimization. In addition to the fact that it is common for utility functions in economics and algorithmic game theory to be submodular, such functions also play a major role in combinatorics, graph theory and combinatorial optimization. A partial list of well known problems captured by submodular maximization includes: Max-Cut, Max-DiCut, Max-k-Cover, Generalized-Assignment, several variants of Max-SAT and some welfare and scheduling problems.

Classical works on submodular maximization problems are mostly combinatorial in nature.

Recently, however, many results based on continuous algorithmic tools have emerged. The main bottleneck in the continuous approach is how to approximately solve a non-convex relaxation for the submodular problem at hand. A simple and elegant method, called “continuous greedy”, successfully tackles this issue for monotone submodular objective functions, however, only much more complex tools are known to work for general non-monotone submodular objectives. We present a new unified continuous greedy algorithm which finds approximate fractional solutions for both the non-monotone and monotone cases, and improves on the approximation ratio for various applications. Some notable immediate implications are information-theoretic tight approximations for Submodular Max-SAT and Submodular-Welfare with k players, for any number of players k, and an improved (1/e)-approximation for maximizing a non-monotone submodular function subject to a matroid or O(1)-knapsack constraints.

We show that continuous methods can be further used to obtain improved results in other settings. Perhaps the most basic submodular maximization problem is the problem of Unconstrained Submodular Maximization, which captures some well studied problems, such as: Max-Cut, Max-DiCut, and some variants of maximum facility location and Max-SAT. Exploiting some symmetry properties of the problem, we present a simple information-theoretic tight (1/2)-approximation algorithm, which unlike previous known algorithms keeps a fractional inner state, i.e., it is based on a continuous approach. We note that our algorithm can be further simplified to obtain a purely combinatorial algorithm which runs only in linear time.

1/18/2012 1:30-2:30 Paul Ohm (University of Colorado Law School)

Computer Science and the Law

Today more than ever, computer science shapes law and law shapes computer science. Computer scientists pave the way for new computing and networking platforms and applications that then set the stage for new forms of collaboration and conflict. These create opportunities for lawyers and lawmakers to respond. The relationship works in the reverse order, too, when lawyers and lawmakers enact laws in ways that constrain or (less often) expand what computer scientists are allowed to do. This interdisciplinary interplay has taken place in many different specific conflicts, from network neutrality to the crypto wars and from battles over copyright to information privacy, but there is value in looking at these more generally, examining the messy but necessary relationship between computer science and law (and policy too).

In this talk, Paul Ohm, a law professor at the University of Colorado, will examine the relationship between computer science and law and policy. He will draw from his experiences as an undergraduate computer science major, professional systems administrator, Department of Justice computer crimes prosecutor, and leading scholar in cyberlaw and information privacy, to talk about whether and how computer science can influence law and policy and vice versa. He will draw from specific examples including debates over anonymization, domain name seizure, and deep packet inspection. This is intended to be a dynamic and interactive session, one in which the audience will help shape the direction of discussion.

1/12/2012 10:30-11:30 Shiri Chechik (Weizmann Institute of Science)

Compact Routing with Failures

Routing is one of the most fundamental problems in distributed networks. A routing scheme is a mechanism that allows delivering messages between the nodes of the graph.

In this talk I’ll discuss a natural extension of compact routing schemes – routing in the presence of failures. Suppose that some of the links crash from time to time and it is still required to deliver messages between the nodes of the graph, if possible. I’ll present a compact routing scheme capable of handling multiple edge failures.

1/11/2012 1:30-2:30 Balasubramanian Sivan (University of Wisconsin-Madison)

Bayesian Multi-Parameter Scheduling

We study the makespan minimization problem with unrelated selfish machines. Specifically, our goal is to schedule a given set of jobs on n machines; the machines are strategic agents who hold the private information of the run-time of each job on them. The goal is to design a mechanism that minimizes makespan — the time taken for the last job to complete. In the strategic setting, strong impossibility results are known that show that no truthful (anonymous) mechanism can achieve better than a factor n approximation. We show that under mild Bayesian assumptions it is possible to circumvent such negative results and obtain a constant approximation.

Joint work with Shuchi Chawla, Jason Hartline and David Malec.

1/10/2012 10:30-11:30 Christian Sommer (MIT)

Exact and Approximate Shortest-Path Queries

We discuss the problem of efficiently computing a shortest path between two nodes of a network — a problem with numerous applications. The shortest-path query problem in particular occurs in transportation (route planning and navigation or also logistics and traffic simulations), in packet routing, in social networks, and in many other scenarios. Furthermore, shortest-path problems occur as subproblems in various optimization problems.

Strategies for computing answers to shortest-path queries may involve the use of pre-computed data structures (also called distance oracles) in order to improve the query time. Designing a shortest-path-query processing method raises questions such as: How can these data structures be computed efficiently? What amount of storage is necessary? How much improvement of the query time is possible? How good is the approximation quality (also termed stretch) of the query result? And, in particular, what are the tradeoffs between pre-computation time, storage, query time, and approximation quality?

The talk provides answers to these questions for static networks. In particular, we consider the tradeoff between storage and query time, both from a theoretical and from an experimental perspective. We focus on two application scenarios: First, we discuss shortest-path query methods for planar graphs, motivated by route planning in road networks. Second, we discuss distance oracles and shortest-path query methods for complex networks, motivated by small-world phenomena in social networks and Internet routing. We also outline which methods and techniques can or cannot be extended to more general networks.

Joint work with Takuya Akiba, Wei Chen, Ken-ichi Kawarabayashi, Philip Klein, Shay Mozes, Shang-Hua Teng, Mikkel Thorup, Elad Verbin, Yajun Wang, Wei Yu, and others.

12/14/2011 1:30-2:30 Dan Spielman (Yale)

Algorithms, Graph Theory and the Solution of Laplacian Linear Equations

We survey several fascinating concepts and algorithms in graph theory that arise in the design of fast algorithms for solving linear equations in the Laplacian matrices of graphs. We will begin by explaining why linear equations in these matrices are so interesting.

The problem of solving linear equations in these matrices motivates a new notion of what it means for one graph to approximate another. This leads to a problem of graph sparsification–the approximation of a graph by a sparser graph. Our algorithms for solving Laplacian linear equations will exploit surprisingly strong approximations of graphs by sparse graphs, and even by trees.

We will survey the roles that spectral graph theory, random matrix theory, graph sparsification, low-stretch spanning trees and local clustering algorithm play in the design of fast algorithms for solving Laplacian linear equations.

12/13/2011 1:30-2:30 Dan Spielman (Yale)

Fitting a Graph to Vectors

We ask “What is the right graph to fit to a set of vectors?”

We would like to associate one vertex with each vector, and choose the edges in a natural way.

We propose one solution that provides good answers to standard Machine Learning problems such as classification and regression, that has interesting combinatorial properties, and that we can compute efficiently.

Joint work with Jonathan Kelner and Samuel Daitch.

12/7/2011 1:30-2:30 Salil Vadhan (Harvard)

Computational Entropy

Shannon’s notion of entropy measures the amount of “randomness” in a process. However, to an algorithm with bounded resources, the amount of randomness can appear to be very different from the Shannon entropy. Indeed, various measures of “computational entropy” have been very useful in computational complexity and the foundations of cryptography.

In this talk, I will describe two new measures of computational entropy (“next-bit pseudoentropy” and “inaccessible entropy”) that have enabled much simpler and more efficient constructions of cryptographic primitives from one-way functions. In particular, I will present ideas underlying a construction of pseudorandom generators of seed length O(n^3) from a one-way function on n bits, improving the seed length of O(n^8) in the classic construction of Hastad, Impagliazzo, Levin, and Luby.

Joint works with Iftach Haitner, Thomas Holenstein, Omer Reingold, Hoeteck Wee, and Colin Jia Zheng.

12/6/2011 1:30-2:30 Aleksandar Nikolov (Rutgers)

Optimal Private Halfspace Counting via Discrepancy

In the range counting problem we are given a set $P$ of $n$ points in $d$-dimensional Euclidean space, an integer weight $x_p$ for each point $p$ in $P$, and a collection ${\cal R}$ of ranges, i.e. subsets of $P$. Given a query range, the task is to output the sum of weights of the points belonging to that range. Range counting is a fundamental problem in computational geometry.

We study $(\epsilon, \delta)$-differentially private algorithms for range counting. Our main results are for range spaces given by halfspaces, i.e.~the halfspace counting problem. We present an $(\epsilon, \delta)$-differentially private algorithm for halfspace counting in $d$ dimensions which achieves $O(n^{1-1/d})$ average squared error. We also show a matching lower bound of $\Omega(n^{1-1/d})$ for any $(\eps, \delta)$-differentially private algorithm.

Both bounds are obtained using discrepancy theory. Our lower bound approach also yields a lower bound of $\Omega((\log n)^{d-1})$ average squared error for $(\epsilon, \delta)$-differentially private orthogonal range counting, the first known lower bound for this problem. Our upper bound methods yield $(\epsilon, \delta)$-differentially private algorithms for range counting with polynomially bounded shatter function range spaces.

Joint work with S. Muthukrishnan.

11/30/2011 1:30-2:30 Cynthia Dwork (MSR Silicon Valley)

Lipschitz Mappings, Differential Privacy, and Fairness Through Awareness

We study fairness in classification, where individuals are classified, e.g., admitted (or not) to a university, and the goal is to prevent discrimination against individuals based on their membership in some group, while maintaining utility for the classifier (the university). We present a framework for fair classification comprising (1) a (hypothetical) task-specific metric for determining the degree to which individuals are similar with respect to the classification task at hand; (2) an algorithm for maximizing utility subject to the fairness constraint that similar individuals are treated similarly; and (3) an adaptation for achieving the complementary goal of “fair affirmative action,” which guarantees statistical parity (the demographics of the set of individuals receiving any classification are the same as the demographics of the underlying population), while treating similar individuals as similarly as possible.  Our approach handles arbitrary classifiers, with arbitrary utilities. We also establish a connection to differential privacy, where similar databases give rise to similar output distributions.

Joint work with Moritz Hardt, Toni Pitassi, Omer Reingold, and Richard Zemel.

11/16/2011 1:30-2:30 Renato Paes Leme (Cornell)

Polyhedral Clinching Auctions and the Adwords Polytope

A central problem in mechanism design is how to deal with budget-constrained agents and the goal is to produce auctions that are incentive compatible, individually rational, budget feasible and Pareto-optimal. Variations of Ausubel’s clinching auction have produced successful results for multi-unit auctions(Dobzinski et al) and certain matching markets (Fiat et al). In this paper, we extend the Ausubel’s clinching auction to the setting where the allocation is a general polymatroid given to us by a separation oracle. We also show that the clinching step can be calculated efficiently using submodular minimization. Moreover, we show that polymatroids are the most general setting under clinching auctions can be applied. Many settings of interest to sponsored search can be expressed as polymatroids. In particular, we define the AdWords polytope, which can be of independent interest.

Furthermore, for the case where only one player is budget constrained, we define an auction for any generic environment satisfying Pareto-optimality, individual rationality, budget feasibility and Pareto optimality. The technique here involves approximating a convex set by smooth surfaces, designing an auction for the smooth environments and taking its limit.

For the case of two players with budget constraints and a general polyhedral (but not polymatroidal) environment, we show an impossibility result. As a byproduct, we get an impossibility result for multi-unit auctions with decreasing marginal utilities. It was conjectured by Ausubel that a variation of the clinching auction with budgets would work for this setting. This conjecture was later reinforced in Dobzinski, Lavi and Nisan. We solve the problem in a negative way. We do so by a characterization of Pareto optimal truthful auctions for polyhedral environment.

This is a joint work with Vahab Mirrokni and Gagan Goel.

11/9/2011 1:30-2:30 Moshe Babaioff (MSR Silicon Valley)

Peaches, Lemons, and Cookies: Designing Auction Markets with Dispersed Information

This paper studies the role of information asymmetries in second price, common value auctions. Motivated by information structures that arise commonly in applications such as online advertising, we seek to understand what types of information asymmetries lead to substantial reductions in revenue for the auctioneer. One application of our results concerns online advertising auctions in the presence of “cookies”, which allow individual advertisers to recognize advertising opportunities for users who, for example, are customers of their websites. Cookies create substantial information asymmetries both ex ante and at the interim stage, when advertisers form their beliefs. The paper proceeds by first introducing a new refinement, which we call “tremble robust equilibrium” (TRE), which overcomes the problem of multiplicity of equilibria in many domains of interest.

Second, we consider a special information structure, where only one bidder has access to superior information, and show that the seller’s revenue in the unique TRE is equal to the expected value of the object conditional on the lowest possible signal, no matter how unlikely it is that this signal is realized. Thus, if cookies identify especially good users, revenue may not be affected much, but if cookies can (even occasionally) be used to identify very poor users, the revenue consequences are severe. In the third part of the paper, we study the case where multiple bidders may be informed, providing additional characterizations of the impact of information structure on revenue. Finally, we consider richer market designs that ensure greater revenue for the auctioneer, for example by auctioning the right to participate in the mechanism.

This is joint work with Ittai Abraham, Susan Athey and Michael Grubb.

11/3/2011 1:30-2:30 Karthik Chandrasekaran (Georgia Tech)

Discrete entropy and the complexity of random integer programming

We consider integer feasibility of random polytopes specified by m random tangential hyperplanes to a ball of radius R centered around an arbitrary point in n-dimensional space. We show that with high probability, the random polytope defined by m=O(n) such constraints contains an integer point provided the radius R is larger than a universal constant.

For the random polytope with m constraints in n-dimensional space, where n < m < 2^O(sqrt(n)), a ball of radius about Omega(sqrt(log (2m/n))) suffices. Moreover, if the polytope contains a ball of radius Omega(log (2m/n)), then we can find an integer solution with high probability (over the input) in randomized polynomial time. Our work provides a connection between integer programming and discrepancy of set systems – in particular, we use the entropy technique from Spencer’s classical result on discrepancy of set systems and build on Bansal’s recent algorithm for finding low-discrepancy solutions efficiently.

This is joint work with Santosh Vempala.

10/28/2011 1:30-2:30 Mihai Patrascu (AT&T Labs Research)

Hashing for Linear Probing

Hash tables are ubiquitous data structures solving the dictionary problem, and they often show up in inner loops, making performance critical.

A hash table algorithm relies crucially on a hash function, which quasirandomly maps a large domain (the input keys) to a small domain (the memory space available). Many “hash tables” (in effect, algorithms for dealing with collisions) have been proposed, the best known being collision chaining, linear probing and cuckoo hashing.

Among these, linear probing is ideally suited for modern computer architectures, which tend to favor linear scans. However, linear probing is quite sensitive to the quality of the hash function and, traditionally, good performance was only guaranteed by using highly independent (but slow) hash functions.

Our finding is that tabulation hashing, despite its low degree of independence, can actually guarantee very robust performance in linear probing. This function is both easy to implement and extremely fast on current hardware (faster than 2 multiplications), offering an ideal solution both in theory and in practice.

10/20/2011 1:30-2:30 Roy Schwartz (Technion)

Continuous Methods for Submodular Maximization

The study of combinatorial problems with a submodular objective function has attracted much attention in recent years, and is partly motivated by the importance of such problems to economics, algorithmic game theory and combinatorial optimization. Classical works on these problems are mostly combinatorial in nature. Recently, however, many results based on continuous algorithmic tools have emerged.

We present several new techniques and algorithmic tools which are based on the continuous approach, yielding improved approximations for various applications and in some cases information-theoretic tight approximations.

1. The main bottleneck in the continuous approach is how to approximately solve a non-convex relaxation for the submodular problem at hand. A simple and elegant method, called “continuous greedy”, successfully tackles this issue for monotone submodular objective functions, however, only much more complex tools are known to work for general non-monotone submodular objectives. We present a new unified continuous greedy algorithm which finds approximate fractional solutions for both the non-monotone and monotone cases, and improves on the approximation ratio for various applications. Some notable immediate implications are information-theoretic tight approximations for Submodular Max-SAT and Submodular-Welfare with $k$ players, for {\em any} number of players $k$, and an improved $1/e$-approximation for maximizing a non-monotone submodular function subject to a matroid or $O(1)$-knapsack constraints.

2. Consider the Unconstrained Submodular Maximization problem in which we are given a non-negative (and possibly non-monotone) submodular function $f$ over a domain $N$, and the objective is to find a subset $S\subseteq N$ maximizing $f(S)$. This is considered one of the basic submodular optimization problems, generalizing well known problems such as Max-CUT, Max-DICUT and variants of maximum facility location and Max-SAT. We present the first rounding based algorithm for this problem, providing an improved approximation of roughly $0.45$ (a hardness of $0.5+\varepsilon$ for every constant $\varepsilon >0$ was given by Feige et al.). To achieve this goal we present a new algorithmic tool, which given a suboptimal solution $S$ whose value is small in comparison to $OPT$ but is “structurally” similar to $OPT$, improves the value of $S$ solely on this information. When two coupled executions of the unified continuous greedy algorithm are carefully combined with the above algorithmic tool, one can achieve the stated approximation of $0.45$.

Joint work with Moran Feldman and Seffi Naor.

10/19/2011 1:30-2:30 Aranyak Mehta (Google)

Online Matching and Ad Allocation

The spectacular success of search and display advertising and its huge growth potential has attracted the attention of researchers from many aspects of computer science. A core problem in this area is that of Ad allocation, an inherently algorithmic and game theoretic question – that of matching ad slots to advertisers, online, under demand and supply constraints. Put very simply: the better the matching, the more efficient the market.

The seminal algorithmic work on online matching, by Karp, Vazirani and Vazirani, was done over two decades ago, well before this motivation existed. In this talk, I will present an overview of several key algorithmic papers in this area, starting with its purely academic beginnings, to the general problem motivated by the application. The theory behind these algorithms involves new combinatorial, probabilistic and linear programming techniques. Besides the analytical results, I will also touch upon how these algorithmic ideas can be applied in practice.

10/11/2011 1:30-2:30 Lorenzo Orecchia (UC Berkeley)

A \tilde{O}(m)-time Spectral Algorithm for Balanced Cut

In the Balanced Cut problem, on input an undirected graph G with m edges, a balance parameter b and a target conductance value \gamma, we are asked to decide whether G has any b-balanced cut of conductance at most \gamma.

Approximation algorithms for Balanced Cut are a fundamental primitive in the design of recursive graph algorithms for a variety of combinatorial and numerical problems. In many of these practical applications, it is of crucial importance for the underlying Balanced-Cut algorithm to run in time as close to linear as possible and have an efficient implementation. For this reason, researchers have focused on spectral methods that guarantee speed and ease of implementation, albeit at the loss of approximation quality on some graphs.

The simplest spectral algorithm for this problem computes the graph’s slowest-mixing eigenvector, removes any unbalanced low-conductance cut it finds and recurses on the rest of the graph. This algorithm achieves an approximation guarantee that is asymptotically optimal for spectral algorithms, but unfortunately, it may need \Omega(n) recursive calls and runs in worst-case quadratic time.

In recent work with Nisheeth Vishnoi and Sushant Sachdeva, we give a spectral algorithm that achieves the same approximation guarantee, by designing a more principled recursion that allows our algorithm to remove unbalanced sparse cuts in O(\log n) stages and to run in time \tilde{O}(m). The main idea behind this improvement is the use of certain random walks as a regularized, more robust analogue of the graph’s slowest-mixing eigenvector. Our second novel contribution is a method to compute the required random-walk vectors in time \tilde{O}(m) that combines ideas in Approximation theory, Lanczos methods, and the linear equation solver by Spielman and Teng.

Our algorithm is thus the first spectral algorithm for Balanced Cut that runs in time \tilde{O}(m) and achieves the asymptotically optimal approximation guarantee for spectral methods, i.e. is able to distinguish between conductance \gamma and \Omega(\sqrt{\gamma}).

10/5/2011 1:30-2:30 Arnab Bhattacharyya (Princeton)

Tight lower bounds for 2-query locally correctable codes over finite fields

A Locally Correctable Code (LCC) is an error correcting code that has a probabilistic self-correcting algorithm that, with high probability, can correct any coordinate of the codeword by looking at only a few other coordinates, even if a fraction of the coordinates are corrupted. LCCs are a stronger form of LDCs (Locally Decodable Codes) which have received a lot of attention recently due to their many applications and surprising constructions.

In this work, we show a separation between 2-query LDCs and LCCs over finite fields of prime order. Specifically, we prove a lower bound of the form p^Ω(δd) on the length of linear 2-query LCCs over F_p, that encode messages of length d. Our bound improves over the known bound of 2^Ω(δd) which is tight for LDCs. Our proof makes use of tools from additive combinatorics which have played an important role in several recent results in Theoretical Computer Science.

We also obtain, as corollaries of our main theorem, new results in incidence geometry over finite fields. The first is an improvement to the Sylvester-Gallai theorem over finite fields and the second is a new analog of Beck’s theorem over finite fields.

Joint work with Zeev Dvir, Shubhangi Saraf, and Amir Shpilka.

Delocalization Properties of Eigenvectors of Random Graphs

A lot is known about the spectrum and the distribution of eigenvalues of G(n,p) random graphs. However many elementary questions regarding the eigenvectors remain open: for instance, do they ‘behave’ like random vectors in $\R^n$? In particular, can we say that each coordinate (in the normalized eigenvector) will be only $C/\sqrt{n}$ with high probability? Does an eigenvector have a ‘significant’ mass on a $\delta n$ fraction of the coordinates w.h.p.?

We use recent techniques due to Erdos, Schlein and Yau, and Tao and Vu to answer questions of this nature. Using these results, we answer an open question of Dekel, Lee and Linial on the number of ‘nodal domains’ in the eigenvectors of G(n,p) random graphs, when $p$ is reasonably large’ (earlier such results were not known even when $p=1/2$).

This is joint work with Sanjeev Arora.

8/31/2011 1:30-2:30 Shahar Dobzinski (Cornell)

(Approximating) Optimal Auctions with Correlated Bidders

We consider the problem of designing a revenue-maximizing auction for a single item, when the values of the bidders are drawn from a correlated distribution. We show that one can find in poly time a deterministic revenue-maximizing auction that guarantees at least 3/5 of the revenue of the best truthful-in-expectation auction. The proof consists of three steps:

(1) Showing that the optimal truthful-in-expectation auction for a constant number of bidders can be computed in polynomial time.

(2) A “derandomization” algorithm that implements every 2-player truthful-in-expectation mechanism as a universally truthful mechanism.

(3) An analysis of three new auctions that have complementary properties.

Joint work with Hu Fu and Bobby Kleinberg.

8/24/2011 1:30-2:30 Yevgeniy Dodis (NYU)

Leftover Hash Lemma, Revisited

The famous Leftover Hash Lemma (LHL) states that (almost) universal hash functions are good randomness extractors. Despite its numerous applications, LHL-based extractors suffer from the following two drawbacks:

(1) Large Entropy Loss: to extract v bits from distribution X of min-entropy m which are e-close to uniform, one must set v<= m – 2*log(1/e), meaning that the entropy loss L = m-v>= 2*log(1/e).

(2) Large Seed Length: the seed length n of universal hash function required by the LHL must be linear in the length of the source.

Quite surprisingly, we show that both limitations of the LHL — large entropy loss and large seed — can often be overcome (or, at least, mitigated) in various quite general scenarios. First, we show that entropy loss could be reduced to L=log(1/e) for the setting of deriving secret keys for most cryptographic applications, including signatures/MACs, CPA/CCA-secure encryption, etc. Specifically, the security of these schemes gracefully degrades from e to at most e + sqrt(e * 2^{-L}). (Notice that, unlike standard LHL, this bound is meaningful even for negative entropy loss, when we extract more bits than the the min-entropy we have!) Second, we study the soundness of the natural *expand-then-extract* approach, where one uses a pseudorandom generator (PRG) to expand a short “input seed” S into a longer “output seed” S’, and then use the resulting S’ as the seed required by the LHL (or, more generally, any randomness extractor). Unfortunately, we show that, in general, expand-then-extract approach is not sound if the Decisional Diffie-Hellman assumption is true.

Despite that, we show that it is sound either: (1) when extracting a “small” (logarithmic in the security of the PRG) number of bits; or (2) in *minicrypt*. Implication (2) suggests that the sample-then-extract approach is likely secure when used with “practical” PRGs, despite lacking a reductionist proof of security!

The paper can be found at http://eprint.iacr.org/2011/088.

8/23/2011 1:30-2:30 Amos Fiat (Tel-Aviv University)

Beyond Myopic Best Response (For Cournot Competition)

A Nash Equilibrium is a joint strategy profile at which each agent myopically plays a best response to the other agents’ strategies, ignoring the possibility that deviating from the equilibrium could lead to an avalanche of successive changes by other agents. However, such changes could potentially be beneficial to the agent, creating incentive to act non-myopically, so as to take advantage of others’ responses.

To study this phenomenon, we consider a non-myopic Cournot competition, where each firm selects whether it wants to maximize profit (as in the classical Cournot competition) or to maximize revenue (by masquerading as a firm with zero production costs).

The key observation is that profit may actually be higher when acting to maximize revenue, (1) which will depress market prices, (2) which will reduce the production of other firms, (3) which will gain market share for the revenue maximizing firm, (4) which will, overall, increase profits for the revenue maximizing firm. Implicit in this line of thought is that one might take other firms’ responses into account when choosing a market strategy.
The Nash Equilibria of the non-myopic Cournot competition capture this action/response issue appropriately, and this work is a step towards understanding the impact of such strategic manipulative play in markets. We study the properties of Nash Equilibria of non-myopic Cournot competition with linear demand functions and show existence of pure Nash Equilibria, that simple best response dynamics will produce such an equilibrium, and that for some natural dynamics this convergence is within linear time. This is in contrast to the well known fact that best response dynamics need not converge in the standard myopic Cournot competition.

Furthermore, we compare the outcome of the non-myopic Cournot competition with that of the standard myopic standard Cournot competition. Not surprisingly, perhaps, prices in the non-myopic game are lower and the firms, in total, produce more and have a lower aggregate utility.

Joint work with Elias Koutsoupias, Katrina Ligett, Yishay Mansour, and Svetlana Olonetsky.

8/17/2011 1:30-2:30 Rocco Servedio (Columbia)

Learning and Testing k-Model Distributions

A k-modal probability distribution over the domain {1,…,N} is one whose  histogram has at most k “peaks” and “valleys”. Such distributions are a natural generalization of the well-studied class of monotone increasing (or monotone decreasing) probability distributions.

We study the problem of learning an unknown k-modal distribution from samples. We also study a related problem in property testing: given access to samples from an unknown k-modal distribution p, determine whether p is identical to q or p is “far” from q. Here q is a k-modal distribution which may be given explicitly or may be available via sample access.

We give algorithms for these problems that are provably close to the best possible in terms of sample and time complexity. An interesting feature of our approach is that our learning algorithms use ingredients from property testing and vice versa.

Joint work with Costis Daskalakis and Ilias Diakonikolas.

8/10/2011 1:30-2:30 Vasilis Gkatzelis (NYU)

Inner Product Spaces for Minsum Coordination Mechanisms

In this work we study the machine scheduling problem of minimizing the weighted sum of completion times of jobs on unrelated machines. We begin by studying the selfish scheduling setting in which each job is controlled by a selfish agent who can strategically choose the machine that will process its job, aiming to minimize its completion time. In order to reduce the inefficiency caused by selfishness, we use local scheduling policies (coordination mechanisms) and analyze their approximation ratio at equilibrium points. Finally, using the intuition acquired from these coordination mechanisms, we develop a simple local search constant-factor approximation algorithm imitating best response dynamics for an appropriately chosen local scheduling policy.

Joint work with: R. Cole, J. Correa, V. Mirrokni, and N. Olver.

8/3/2011 1:30-2:30 Adel Javanmard (Stanford)

Localization from Incomplete Noisy Distance Measurements

We consider the problem of positioning a cloud of points in the Euclidean space R^d, using noisy measurements of a subset of pairwise distances. This task has applications in various areas, such as sensor network localization and reconstruction of protein conformations from NMR measurements. Also, it is closely related to dimensionality reduction problems and manifold learning, where the goal is to learn the underlying global geometry of a data set using local (or partial) metric information. Here we propose a reconstruction algorithm based on semidefinite programming. For a random geometric graph model and uniformly bounded noise, we provide a precise characterization of the algorithm’s performance: In the noiseless case, we find a radius r0 beyond which the algorithm reconstructs the exact positions (up to rigid transformations). In the presence of noise, we obtain upper and lower bounds on the reconstruction error that match up to a factor that depends only on the dimension d, and the average degree of the nodes in the graph.

This is joint work with Andrea Montanari.

7/27/2011 1:30-2:30 Jon Kleinberg (Cornell)

Which Networks Are Least Susceptible to Cascading Failures?

Perhaps the most basic model of contagion in a network draws its motivation from epidemic disease: when a node is affected, it has a given probability of affecting its neighbors as well. In recent prior work with Blume, Easley, Kleinberg, and Tardos, we considered how strategic agents should form links when there is a danger that failures can spread through the resulting network according to such a process.

This type of probabilistic contagion, however, represents just a small portion of a much broader space of “threshold cascade models”. This more general class of threshold models has a simple formulation: each node v picks a threshold t(v) according to an underlying distribution, and it fails if at any point in time it has at least t(v) failed neighbors. The expressive power of this framework lies in the way it can capture a range of fundamentally different types of failure processes, including those where exposure to failed nodes increases one’s chance of failing in the future. Despite the simplicity of the formulation, however, it has been very challenging to analyze the failure processes that arise from arbitrary thresholds; even qualitative questions concerning which graphs are the most resilient to cascading failures in these models have been difficult to resolve.

Here we consider the full space of threshold cascade models, and develop a set of new techniques for comparing arbitrary networks with respect to their failure resilience under different distributions of thresholds. We find that the space has a surprisingly rich structure: small shifts in the behavior of the thresholds can favor clustered clique-like graph structures, branching tree-like ones, or even intermediate hybrids.

Joint work with Larry Blume, David Easley, Bobby Kleinberg, and Eva Tardos (to appear at FOCS 2011).

7/20/2011 1:30-2:30 Sigal Oren (Cornell)

Mechanisms for (Mis)allocating Scientific Credit

Scientific communities confer many forms of credit — both implicit and explicit — on their successful members, and it has long been argued that the motivation provided by these forms of credit helps to shape a community’s collective attention toward different lines of research. The allocation of scientific credit, however, has also been the focus of long-documented pathologies: certain research questions are said to command too much credit, at the expense of other equally important questions; and certain researchers (in a version of Robert Merton’s Matthew Effect) seem to receive a disproportionate share of the credit, even when the contributions of others are similar.

Here we show that the presence of each of these pathologies can in fact increase the collective productivity of a community. We consider a model for the allocation of credit, in which individuals can choose among projects of varying levels of importance and difficulty, and they compete to receive credit with others who choose the same project. Under the most natural mechanism for allocating credit, in which it is divided among those who succeed at a project in proportion to the project’s importance, the resulting selection of projects by self-interested, credit-maximizing individuals will in general be socially sub-optimal. However, we show that there exist ways of allocating credit out of proportion to the true importance of the projects, as well as mechanisms that assign credit out of proportion to the relative contributions of the individuals, that lead credit-maximizing individuals to collectively achieve social optimality. These results therefore suggest how well-known forms of misallocation of scientific credit can in fact serve to channel self-interested behavior into socially optimal outcomes.

This is joint work with Jon Kleinberg.

7/13/2011 1:30-2:30 Elette Boyle (MIT)

Leakage-Resilient Coin Tossing

The ability to collectively toss a common coin among n parties in the presence of faults is an important primitive in the arsenal of randomized distributed protocols. In the case of dishonest majority, it was shown to be impossible to achieve less than 1/r bias in O(r) rounds (Cleve STOC ’86). In the case of honest majority, in contrast, unconditionally secure O(1)-round protocols for generating common unbiased coins follow from general completeness theorems on multi-party secure protocols in the secure channels model (e.g., BGW, CCD STOC ’88).

However, in the protocols with honest majority, parties must generate and hold local secret values which are assumed to be perfectly hidden from malicious parties: an assumption which is crucial to proving the resulting common coin is unbiased. This assumption unfortunately does not seem to hold in practice, as attackers can launch side-channel attacks on the local state of honest parties and leak information on their secrets.

In this work, we present an O(1)-round protocol for collectively generating an unbiased common coin, in the presence of leakage on the local state of the honest parties. We tolerate t ≤ ( 1/3 − ϵ)n computationally-unbounded Byzantine faults and in addition a Ω(1)-fraction leakage on each (honest) party’s secret state. Our results hold in the memory leakage model (of Akavia, Goldwasser, Vaikuntanathan ’08) adapted to the distributed setting.

This is joint work with Shafi Goldwasser and Yael Tauman Kalai.

7/6/2011 1:30-2:30 Ohad Shamir (MSR New-England)

Information Trade-offs in Learning

When originally formulated in the 1980’s, the classic PAC model of learning focused on how one can learn with a small amount of high-quality data. In contrast, much of machine learning today is done on huge amounts of low-quality data. While in some sense the “total” amount of information provided remains the same, the question is how one can trade-off between the data size and the amount of information provided by any individual example. In this talk, I will discuss two concrete settings where this trade-off occurs. The first deals with learning linear predictors, where we can only obtain a few attributes from any individual example. The second deals with multi-armed-bandits problems, where one can obtain varying amounts of side-information on actions not chosen. The resulting algorithms are theoretically-grounded and completely practical.

Based on joint works with Nicolò Cesa-Bianchi, Shai Shalev-Shwartz and Shie Mannor.

6/22/2011 1:30-2:30 Huy L. Nguyen (Princeton)

Near linear lower bound for dimension reduction in L1

Given a set of n points in L1, how many dimensions are needed to represent all pairwise distances within a specific distortion ? This dimension-distortion tradeoff question is well understood for the L2 norm, where O((log n)/epsilon^2) dimensions suffice to achieve 1+epsilon distortion. In sharp contrast, there is a significant gap between upper and lower bounds for dimension reduction in L1. A recent result shows that distortion 1+epsilon can be achieved with n/epsilon^2 dimensions. On the other hand, the only lower bounds known are that distortion delta requires n^{\Omega(1/delta^2)} dimension and that distortion 1+epsilon requires n^{1/2-O(epsilon*log(1/ epsilon))} dimensions. In this work, we show the first near linear lower bounds for dimension reduction in L1. In particular, we show that 1+epsilon distortion requires at least n^{1-O(1/log(1/epsilon))} dimensions.

Our proofs are combinatorial, but inspired by linear programming. In fact, our techniques lead to a simple combinatorial argument that is equivalent to the LP based proof of Brinkman-Charikar for lower bounds on dimension reduction in L1.

This is joint work with Alexandr Andoni, Moses Charikar, and Ofer Neiman.

6/15/2011 1:30-2:30 Giuseppe F. Italiano (University of Rome “Tor Vergata”)

Finding Strong Bridges and Strong Articulation Points in Linear Time

Given a directed graph $G$, an edge is a strong bridge if its removal increases the number of strongly connected components of $G$. Similarly, we say that a vertex is a strong articulation point if its removal increases the number of strongly connected components of $G$. In this paper, we present linear-time algorithms for computing all the strong bridges and all the strong articulation points of directed graphs, solving an open problem posed in [BFL05].

Joint work with Luigi Laura and Federico Santaroni.

6/14/2011 1:30-2:30 Robert Kleinberg (Cornell)

Network Formation in the Presence of Contagious Risk

There are a number of domains where agents must collectively form a network in the face of the following trade-off: each agent receives benefits from the direct links it forms to others, but these links expose it to the risk of being hit by a cascading failure that might spread over multi- step paths. Financial contagion, epidemic disease, and the exposure of covert organizations to discovery are all settings in which such issues have been articulated.

Here we formulate the problem in terms of strategic network formation, and provide asymptotically tight bounds on the welfare of both optimal and stable networks. We find that socially optimal networks are, in a precise sense, situated just beyond a phase transition in the behavior of the cascading failures, and that stable graphs lie slightly further beyond this phase transition, at a point where most of the available welfare has been lost. Our analysis enables us to explore such issues as the trade-offs between clustered and anonymous market structures, and it exposes a fundamental sense in which very small amounts of “over-linking” in networks with contagious risk can have strong consequences for the welfare of the participants.

Joint work with Larry Blume, David Easley, Jon Kleinberg, and Eva Tardos.

6/9/2011 2:30-3:30 Rasmus Pagh (IT University of Copenhagen)

A New Data Layout For Set Intersection on GPUs

Set intersection is the core in a variety of problems, e.g. frequent itemset mining and sparse boolean matrix multiplication. It is well-known that large speed gains can, for some computational problems, be obtained by using a graphics processing unit (GPU) as a massively parallel computing device. However, GPUs require highly regular control flow and memory access patterns, and for this reason previous GPU methods for intersecting sets have used a simple bitmap representation. This representation requires excessive space on sparse data sets. In this paper we present a new data layout, BATMAP, that is particularly well suited for parallel processing, and is compact even for sparse data. We also describe experiments on the data structure, compared against CPU alternatives.

Joint work with Rasmus Resen Amossen.

6/1/2011 1:30-2:30 Vinod Vaikuntanathan (MSR Redmond)

New Paradigms for Efficient Fully Homomorphic Encryption

We present a fully homomorphic encryption scheme that is based solely on the standard learning with errors (LWE) assumption. Applying known results on LWE, the security of our scheme is based on the classical worst-case hardness of short vector problems on arbitrary lattices. As icing on the cake, our scheme is quite efficient, and has very short ciphertexts.

Our construction introduces a new paradigm and two new techniques for the construction of homomorphic encryption, and improves on previous works in two aspects.

1) We show that “somewhat homomorphic” encryption can be based on LWE, using a new re-linearization technique. In contrast, all previous schemes relied on complexity assumptions related to ideals in various rings.

2) More importantly, we deviate from the “squashing paradigm” used in all previous works. We introduce a new dimension reduction technique, which shortens the ciphertexts and reduces the decryption complexity of our scheme, without introducing additional assumptions. In contrast, all previous works required an additional, very strong assumption (namely, the sparse subset sum assumption).

A by-product of our work is a new type of fully homomorphic identity-based encryption scheme.

Joint work with Zvika Brakerski (Weizmann).

5/25/2011 1:30-2:30 Amin Saberi (Stanford)

A Randomized Rounding Approach to the Traveling Salesman Problem

For some positive constant c, we give a 3/2-c approximation algorithm for the following problem: given a graph G(V; E), find the shortest tour that visits every vertex at least once. This is a special case of the metric traveling salesman problem when the underlying metric is defined by shortest path distances in G. The result improves on the 3/2-approximation algorithm due to Christodes.

Joint work with M. Singh and S. Oveis Gharan.

5/18/2011 1:30-2:30 Gil Segev (MSR Silicon Valley)

Public-Key Cryptographic Primitives Provably as Secure as Subset Sum

We present a public-key encryption scheme whose security is equivalent to the hardness of solving random instances of the subset sum problem. The subset sum assumption required for the security of our scheme is weaker than that of existing subset-sum based encryption schemes, namely the lattice-based schemes of Ajtai and Dwork (STOC ’97), Regev (STOC ’03, STOC ’05), and Peikert (STOC ’09). Our proof of security is simple and direct.

Joint work with Vadim Lyubashevsky and Adriana Palacio.

5/11/2011 1:30-2:30 Mukund Sundararajan (Google)

We study the attribution problem, that is, the problem of attributing a change in the value of a characteristic function to its independent variables. We make three contributions. First, we propose a formalization of the problem based on a standard cost-sharing model. Second, in our most important technical contribution, we show that there is a unique path attribution method that satisfies Affine Scale Invariance and Anonymity if and only if the characteristic function is multilinear. We term this the Aumann-Shapley-Shubik method. Third, we study multilinear characteristic functions in detail; we describe a computationally efficient implementation of the Aumann-Shapley-Shubik method and discuss practical applications to portfolio analysis, e-commerce, and sports statistics.

5/4/2011 1:30-2:30 Paul Valiant (UC Berkeley)

Central Limit Theorems and Tight Lower Bounds for Entropy Estimation

In joint work with Gregory Valiant, we have been investigating a new approach to estimating symmetric properties of distributions, including the standard and fundamental properties of entropy and support size. In a previous talk, Greg introduced the first explicit sublinear-sample estimators for these problems, which estimate these quantities to constant additive error using O(n/log n) samples. In this independent but complementary talk, we show that this result is in fact optimal up to constant factors. The analysis makes crucial use of two new multivariate central limit theorems that appear quite natural and general. The first is proven directly via Stein’s method; the second is proven in terms of the first using a recent generalization of Newton’s inequalities. The talk will include a high level overview of these techniques, and their application both in our context and more generally.

4/27/2011 1:30-2:30 Mihai Budiu and others (MSR Silicon Valley)

DryadLINQ and Theory Challenges

4/20/2011 1:30-2:30 Gregory Valiant (UC Berkeley)

Estimating the Unseen: A Sublinear-Sample Estimator of Distributions

In joint work with Paul Valiant, we introduce a new approach to characterizing the unobserved portion of a distribution, which provides sublinear-sample additive estimators for a class of properties that includes entropy and distribution support size (the distinct elements’ problem). Together with our new lower bounds—which Paul will discuss in a separate talk—this settles the longstanding question of the sample complexities of these estimation problems, up to constant factors. Our algorithm estimates these properties up to an arbitrarily small additive constant, using O(n log n) samples, where n is a bound on the support size (or in the case of estimating the support size, 1/n is a lower bound on the probability of any element of the domain). Previously, no explicit sublinear-sample algorithms for either of these problems were known.

3/30/2011 1:30-2:30 Yaron Singer (UC Berkeley)

Budget Feasible Mechanism Design

In this talk we will discuss the budget feasibility framework where the goal is to design incentive compatible mechanisms under a budget constraint on the mechanisms’ payments. Such a challenge typically arises in markets where the mechanism designer wishes to procure items or services from strategic agents.

While in many cases the budget limitation can render mechanisms with poor performance in terms of the utility of the buyer, there are broad classes of utility functions for which desirable approximation guarantees are achievable. We will present some of the positive results for submoudular, subaddtive and cases of non-monotone utilities, and discuss computational and strategic intricacies that arise in this setting.

We will also highlight the relevance of this framework to privacy, crowdsourcing and social networks. In particular, we will show the framework’s application to the influence maximization problem in social networks and give some evidence that suggests that beyond provable guarantees, the mechanisms perform well in practice.

3/16/2011 1:30-2:30 Jason Hartline (Northwestern University)

The Theory of Crowdsourcing

Crowdsourcing contests have been popularized by the Netflix challenge and websites like TopCoder and Taskcn. What is crowdsourcing? Imagine you are designing a new web service, you have it all coded up, but the site looks bad because you haven’t got any graphic design skills. You could hire an artist to design your logo, or you could post the design task as a competition to crowdsourcing website Taskcn with a monetary reward of $100. Contestants on Taskcn would then compete to produce the best logo. You then select your favorite logo and award that contestant the$100 prize.

In this talk, I discuss the theory of crowdsourcing contests. First, I will show how to model crowdsourcing contests using auction theory. Second, I will discuss how to solve for contestant strategies. I.e., suppose you were entering such a programming contest on TopCoder, how much work should you do on your entry to optimize your gains from winning less the cost of doing the work? Finally, I will discuss inefficiency from the fact that the effort of losing contestants is wasted (e.g., every contestant has to do work to design a logo, but you only value your favorite logo). I will show that this wasted effort is at most half of the total amount of effort. A consequence is that crowdsourcing is approximately as efficient a means of procurement as conventional methods (e.g., auctions or negotiations).

Joint work with Shuchi Chawla and Balu Sivan.

2/23/2011 1:30-2:30

Yael Tauman Kalai (MSR New-England) Leaky Pseudo Entropy Functions

Pseudo-random functions (PRFs), introduced by Goldreich, Goldwasser, and Micali (FOCS 1984), are functions that look truly random! These functions are associated with a short random seed s, and the guarantee is that no efficient adversary can tell the difference between getting oracle access to a random PRF function f_s, and getting oracle access to a truly random function.

The question we ask in this work is: Can we generate randomness (or even entropy) from a short random seed s that is partially leaked? Unfortunately, as deterministic extractors do not exist, leaky PRFs do not exist, even if a single bit about the secret seed s is leaked. Thus, we consider the following relaxation: Instead of requiring that for each input x, the value f_s(x) looks random, we require that it looks like it has high min-entropy, even given oracle access to f_s everywhere except at point x. We call such a function family a pseudo-entropy function (PEF) family. We construct such a leakage-resilient PEF family under standard cryptographic assumptions (such as DDH).