enter search term and/or author name
We study the following simple Bayesian auction setting: m items are sold to n selfish bidders in m independent second-price auctions. Each bidder has a private valuation function that specifies his or her complex...
A Combinatorial, Primal-Dual Approach to Semidefinite Programs
Sanjeev Arora, Satyen Kale
Article No.: 12
Semidefinite programs (SDPs) have been used in many recent approximation algorithms. We develop a general primal-dual approach to solve SDPs using a generalization of the well-known multiplicative weights update rule to symmetric matrices. For a...
We address the problem of Byzantine agreement, to bring processors to agreement on a bit in the presence of a strong adversary. This adversary has full information of the state of all processors, the ability to control message scheduling in...
Graph databases have received much attention as of late due to numerous applications in which data is naturally viewed as a graph; these include social networks, RDF and the Semantic Web, biological databases, and many others. There are many...
Almost Optimal Local Graph Clustering Using Evolving Sets
Reid Andersen, Shayan Oveis Gharan, Yuval Peres, Luca Trevisan
Article No.: 15
Spectral partitioning is a simple, nearly linear time algorithm to find sparse cuts, and the Cheeger inequalities provide a worst-case guarantee for the quality of the approximation found by the algorithm. A local graph partitioning...
A New Kind of Tradeoffs in Propositional Proof Complexity
Article No.: 16
We exhibit an unusually strong tradeoff in propositional proof complexity that significantly deviates from the established pattern of almost all results of this kind. Namely, restrictions on one resource (width, in our case) imply an increase in...
The question of what can be computed, and how efficiently, is at the core of computer science. Not surprisingly, in distributed systems and networking research, an equally fundamental question is what can be computed in a distributed...
Computational Complexity of Quantum Satisfiability
Christian Herrmann, Martin Ziegler
Article No.: 19
We connect both discrete and algebraic complexity theory with the satisfiability problem in certain non-Boolean lattices.
Specifically, quantum logic was introduced in 1936 by Garrett Birkhoff and John von Neumann as a framework for...