IEEE FOCS 2010
TechTalks from event: IEEE FOCS 2010
51st Annual IEEE Symposium on Foundations of Computer Science

Pure and BayesNash Price of Anarchy for Generalized Second Price AuctionGeneralized Second Price Auction, also knows as Ad Word auctions, and its variants has been the main mechanism used by search companies to auction positions for sponsored search links. In this paper we study the social welfare of the Nash equilibria of this game. It is known that socially optimal Nash equilibria exists (i.e., that the Price of Stability for this game is 1). This paper is the first to prove bounds on the price of anarchy. Our main result is to show that under some mild assumptions the price of anarchy is small. For pure Nash equilibria we bound the price of anarchy by 1.618, assuming all bidders are playing undominated strategies. For mixed Nash equilibria we prove a bound of 4 under the same assumption. We also extend the result to the Bayesian setting when bidders valuations are also random, and prove a bound of 8 for this case. Our proof exhibits a combinatorial structure of Nash equilibria and use this structure to bound the price of anarchy. While establishing the structure is simple in the case of pure and mixed Nash equilibria, the extension to the Bayesian setting requires the use of novel combinatorial techniques that can be of independent interest.

Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts / Frugal Mechanism Design via Spectral TechniquesWe study truthful mechanisms for hiring a team of agents in three classes of set systems: Vertex Cover auctions, kflow auctions, and cut auctions. For Vertex Cover auctions, the vertices are owned by selfish and rational agents, and the auctioneer wants to purchase a vertex cover from them. For kflow auctions, the edges are owned by the agents, and the auctioneer wants to purchase k edgedisjoint st paths, for given s and t. In the same setting, for cut auctions, the auctioneer wants to purchase an st cut. Only the agents know their costs, and the auctioneer needs to select a feasible set and payments based on bids made by the agents.
We present constantcompetitive truthful mechanisms for all three set systems. That is, the maximum overpayment of the mechanism is within a constant factor of the maximum overpayment of any truthful mechanism, for every set system in the class. The mechanism for Vertex Cover is based on scaling each bid by a multiplier derived from the dominant eigenvector of a certain matrix. The mechanism for kflows prunes the graph to be minimally (k+1)connected, and then applies the Vertex Cover mechanism. Similarly, the mechanism for cuts contracts the graph until all st paths have length exactly 2, and then applies the Vertex Cover mechanism.

Budget Feasible MechanismsWe study a novel class of mechanism design problems in which the outcomes are constrained by the payments. This basic class of mechanism design problems captures many common economic situations, and yet it has not been studied, to our knowledge, in the past. We focus on the case of procurement auctions in which sellers have private costs, and the auctioneer aims to maximize a utility function on subsets of items, under the constraint that the sum of the payments provided by the mechanism does not exceed a given budget. Standard mechanism design ideas such as the VCG mechanism and its variants are not applicable here. We show that, for general functions, the budget constraint can render mechanisms arbitrarily bad in terms of the utility of the buyer. However, our main result shows that for the important class of submodular functions, a bounded approximation ratio is achievable. Better approximation results are obtained for subclasses of the submodular functions. We explore the space of budget feasible mechanisms in other domains and give a characterization under more restricted conditions.

BlackBox Randomized Reductions in Algorithmic Mechanism DesignWe give the first blackbox reduction from arbitrary approximation algorithms to truthful approximation mechanisms for a nontrivial class of multiparameter problems. Specifically, we prove that every packing problem that admits an FPTAS also admits a truthfulinexpectation randomized mechanism that is an FPTAS. Our reduction makes novel use of smoothed analysis, by employing small perturbations as a tool in algorithmic mechanism design. To argue that our perturbation schemes are incentivecompatible, we develop a ?duality? between linear perturbations of the objective function of an optimization problem and of its feasible set. Viewed from the dual perspective, our mechanisms are maximalindistributionalrange and hence truthful in expectation.

Boosting and Differential PrivacyBoosting is a general method for improving the accuracy of learning algorithms. We use boosting to construct {em privacypreserving synopses} of the input database. These are data structures that yield, for a given set $Q$ of queries over an input database, reasonably accurate estimates of the responses to every query in~$Q$. Given a {em base synopsis generator} that takes a distribution on $Q$ and produces a ``weak'' synopsis that yields ``good'' answers for a majority of the weight in $Q$, our {em Boosting for Queries} algorithm obtains a synopsis that is good for all of~$Q$. We ensure privacy for the rows of the database, but the boosting is performed on the {em queries}.
We provide an (inefficient) base synopsis generator for sets of {em arbitrary} lowsensitivity queries (queries whose answers do not vary much under the addition or deletion of a single row). This yields the first privacypreserving synopsis generator for arbitrary lowsensitivity queries.
Boosting is an iterative method. In our Boosting for Queries algorithm, each iteration incurs a certain privacy loss. In analyzing the cumulative privacy loss over many iterations, we obtain a bound on the {em expected} privacy loss from a single $eps$dfp{} mechanism. Combining this with {em evolution of confidence} arguments from the literature, we get a fresh perspective  and stronger bounds  on the expected cumulative privacy loss due to multiple mechanisms, each providing $eps$differential privacy or one of its relaxations, and each operating on (potentially) different, adaptively chosen, databases. snote{changed ``the first bounds'' to ``stronger bounds'', to deflect possible claims that such guarantees are folklore/obvious for $(keps,kdelta)$ type results}
Finally, we can also view the input database as a training set in a learning algorithm, where each row corresponds to an element in the training set. Given the power and prevalence of boosting, it is natural t

A Multiplicative Weights Mechanism for Interactive PrivacyPreserving Data AnalysisWe consider statistical data analysis with online queries. In this setting a trusted curator maintains a database of sensitive information about individual participants, and releases privacypreserving answers to online queries as they arrive. Our primary contribution is a new differentially private multiplicative weights mechanism for answering a large number of counting queries that arrive online and may be adaptively chosen. This mechanism yields two main results.
First, it is the first {em efficient} mechanism for answering large numbers of online queries with worstcase accuracy guarantees (accuracy on every input database). The error is emph{optimal} in its dependence on the number of participants and depends only logarithmically on the number of queries being answered. The running time is nearly {em linear} in the size of the data universe. Previous mechanisms for answering many counting queries all run in super cubic time, even for the (easier) offline setting where all queries are known in advance.
Second, while continuing to guarantee worstcase privacy for {em any} input database, we obtain exponential improvements in running time for a broad class of databases. When the input database is drawn from a {em smooth} distribution that does not place too much weight on any single data item, accuracy remains as above and the running time becomes {em polylogarithmic} in the data universe size. To the best of our knowledge, this is the first example of a polylogarithmic time mechanism for answering large numbers of general queries (indeed, for worstcase accuracy guarantees, there are known hardness results). Our main technical contributions are a new application of multiplicative weights techniques to the differential privacy setting, a new privacy analysis for multiplicative weights algorithms, and a general technique for reducing data dimensionality for databases drawn from smooth distributions.

Impossibility of Differentially Private Universally Optimal MechanismsThe notion of {em a universally utilitymaximizing privacy mechanism} was recently introduced by Ghosh, Roughgarden, and Sundararajan~[STOC 2009]. These are mechanisms that guarantee optimal utility to a large class of information consumers {em simultaneously}, while preserving {em Differential Privacy} [Dwork, McSherry, Nissim, and Smith, TCC 2006]. Ghosh et al. have demonstrated, quite surprisingly, a case where such a universallyoptimal differentiallyprivate mechanisms exists, when the information consumers are Bayesian. This result was recently extended by Gupte and Sundararajan~[PODS 2010] to riskaverse consumers.
Both positive results deal with mechanisms (approximately) computing, a {em single count query} (i.e., the number of individuals satisfying a specific property in a given population), and the starting point of our work is a trial at extending these results to similar settings, such as sum queries with nonbinary individual values, histograms, and two (or more) count queries. We show, however, that universallyoptimal mechanisms do not exist for all these queries , both for Bayesian and riskaverse consumers.
For the Bayesian case, we go further, and give a characterization of those functions that admit universallyoptimal mechanisms, showing that a universallyoptimal mechanism exists, essentially, only for a (single) count query. At the heart of our proof is a representation of a query function $f$ by its {em privacy constraint graph} $G_f$ whose edges correspond to values resulting by applying $f$ to neighboring databases.

The Limits of TwoParty Differential PrivacyWe study differential privacy in a distributed setting where two parties would like to perform analysis of their joint data while preserving privacy for both datasets. Our results imply almost tight lower bounds on the accuracy of such data analyses, both for specific natural functions (such as Hamming distance) and in general. Our bounds expose a sharp contrast between the twoparty setting and the simpler clientserver setting (where privacy guarantees are onesided). In addition, those bounds demonstrate a dramatic gap between the accuracy that can be obtained by differentially private data analysis versus the accuracy obtainable when privacy is relaxed to a computational variant of differential privacy.
The first proof technique we develop demonstrates a connection between differential privacy and deterministic extraction from SanthaVazirani sources. A second connection we expose indicates that the ability to approximate a function by a lowerror differentiallyprivate protocol is strongly related to the ability to approximate it by a low communication protocol (the connection goes in both ways).

Deciding firstorder properties for sparse graphsWe present a lineartime algorithm for deciding firstorder logic (FOL) properties in classes of graphs with bounded expansion. Many natural classes of graphs have bounded expansion; for instance, graphs of bounded treewidth, all proper minorclosed classes of graphs, graphs of bounded degree, graphs with no subgraph isomorphic to a subdivision of a fixed graph, and graphs that can be drawn in a fixed surface in such a way that each edge crosses at most a constant number of other edges. We also develop an almost lineartime algorithm for deciding FOL properties in classes of graphs with locally bounded expansion; those include classes of graphs with locally bounded treewidth or locally excluding a minor.
More generally, we design a dynamic data structure for graphs belonging to a class $cal G$ of graphs of bounded expansion. After a lineartime initialization the data structure allows us to test an FOL property in constant time, and the data structure can be updated in constant time after addition/deletion of an edge, provided the list of possible edges to be added is known in advance and their addition results in a graph in $cal G$. In addition, we design dynamic data structure for testing $Sigma_1$properties or the existence of short paths between prescribed vertices in such classes of graphs. All our results hold for relational structures.

Logspace Versions of the Theorems of Bodlaender and CourcelleBodlaender's Theorem states that for every $k$ there is a lineartime algorithm that decides whether an input graph has tree width~$k$ and, if so, computes a width$k$ tree composition. Courcelle's Theorem builds on Bodlaender's Theorem and states that for every monadic secondorder formula $phi$ and for every $k$ there is a lineartime algorithm that decides whether a given logical structure $mathcal A$ of tree width at most $k$ satisfies $phi$. We prove that both theorems still hold when ``linear time'' is replaced by ``logarithmic space.'' The transfer of the powerful theoretical framework of monadic secondorder logic and bounded tree width to logarithmic space allows us to settle a number of both old and recent open problems in the logspace world.
 All Talks
 Geometric complexity theory (GCT)
 How to Grow Your Lower Bounds
 How To Think About Mechanism Design
 Constructive Algorithms for Discrepancy Minimization
 Bounded Independence Fools Degree2 Threshold Functions
 The Coin Problem, and Pseudorandomness for Branching Programs / Pseudorandom Generators for Regular Branching Programs
 Settling the Polynomial Learnability of Mixtures of Gaussians
 Polynomial Learning of Distribution Families
 Agnostically learning under permutation invariant distributions
 Learning Convex Concepts from Gaussian Distributions with PCA
 Determinant Sums for Undirected Hamiltonicity
 Fighting Perebor: New and Improved Algorithms for Formula and QBF Satisfiability
 The Monotone Complexity of kCLIQUE on Random Graphs
 The Complexity of Distributions
 Hardness of Finding Independent Sets in Almost 3Colorable Graphs
 Approximation Algorithms for the EdgeDisjoint Paths Problem via Raecke Decompositions
 Computational Transition at the Uniqueness Threshold
 Avner Magen Memorial Talk
 Clustering with Spectral Norm and the kmeans Algorithm
 Stability yields a PTAS for kMedian and kMeans Clustering
 The Geometry of Manipulation  a Quantitative Proof of the GibbardSatterthwaite Theorem
 Efficient volume sampling for row/column subset selection
 Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
 New Constructive Aspects of the Lovasz Local Lemma
 The Geometry of Scheduling
 Sublinear Time Optimization for Machine Learning
 Estimating the longest increasing sequence in sublinear time
 Testing Properties of Sparse Images
 A Unified Framework for Testing LinearInvariant Properties
 Optimal Testing of ReedMuller Codes
 Subexponential Algorithms for Unique Games and Related problems
 Nevanlinna Prize Talk. Laplacian Gems
 Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures
 MinimumCost Network Design with (Dis)economies of Scale
 One Tree Suffices: A Simultaneous O(1)Approximation for SingleSink BuyatBulk
 Min stCut Oracle for Planar Graphs with NearLinear Preprocessing Time
 Subcubic Equivalences Between Path, Matrix, and Triangle Problems
 Replacement Paths via Fast Matrix Multiplication
 AllPairs Shortest Paths in O(n2) Time With High Probability
 Approximating Maximum Weight Matching in Nearlinear Time
 Pure and BayesNash Price of Anarchy for Generalized Second Price Auction
 Frugal and Truthful Auctions for Vertex Covers, Flows, and Cuts / Frugal Mechanism Design via Spectral Techniques
 Budget Feasible Mechanisms
 BlackBox Randomized Reductions in Algorithmic Mechanism Design
 Boosting and Differential Privacy
 A Multiplicative Weights Mechanism for Interactive PrivacyPreserving Data Analysis
 Impossibility of Differentially Private Universally Optimal Mechanisms
 The Limits of TwoParty Differential Privacy
 Deciding firstorder properties for sparse graphs
 Logspace Versions of the Theorems of Bodlaender and Courcelle
 A separator theorem in minorclosed classes
 Optimal stochastic planarization
 Solving linear systems through nested dissection
 Approaching optimality for solving SDD linear systems
 Fast approximation algorithms for cutbased graph problems
 Metric Extension Operators, Vertex Sparsifiers and Lipschitz Extendability
 Vertex Sparsifiers and Abstract Rounding Algorithms
 A nonlinear lower bound for planar epsilonnets
 The subexponential upper bound for online chain partitioning
 Improved Bounds for Geometric Permutations
 On the Queue Number of Planar Graphs
 Holographic Algorithms with Matchgates Capture Precisely Tractable Planar #CSP
 A Decidable Dichotomy Theorem on Directed Graph Homomorphisms with Nonnegative Weights
 Overcoming the Hole In The Bucket: PublicKey Cryptography Resilient to Continual Memory Leakage
 Cryptography Against Continuous Memory Attacks
 On the Insecurity of Parallel Repetition for Leakage Resilience
 BlackBox, RoundEfficient Secure Computation via NonMalleability Assumption
 From Standard to Adaptive Hardness And Composable Security With No SetUp
 On the Computational Complexity of Coin Flipping
 Sequential Rationality in Cryptographic Protocols
 A Fourieranalytic approach to ReedMuller decoding
 Pseudorandom generators for CC0[p] and the Fourier spectrum of lowdegree polynomials over finite fields
 Matching Vector Codes / Local list decoding with a constant number of queries
 Codes for Computationally Simple Channels: Explicit Constructions with Optimal Rate
 A lower bound for dynamic approximate membership data structures
 Lower Bounds for Near Neighbor Search via Metric Expansion
 Distance Oracles Beyond the Thorup?Zwick Bound