enter search term and/or author name
We show that the sparsest cut in graphs with n vertices and m edges can be approximated within O(log2 n) factor in Õ(m + n3/2) time using polylogarithmic single commodity max-flow...
Unbalanced expanders and randomness extractors from Parvaresh--Vardy codes
Venkatesan Guruswami, Christopher Umans, Salil Vadhan
Article No.: 20
We give an improved explicit construction of highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree (which is polylogarithmic in the number of vertices). Both the degree and the number of right-hand vertices are...
On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs
Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore
Article No.: 21
Understanding the graph structure of the Internet is a crucial step for building accurate network models and designing efficient algorithms for Internet applications. Yet, obtaining this graph structure can be a surprisingly difficult task, as...
Empirical hardness models: Methodology and a case study on combinatorial auctions
Kevin Leyton-Brown, Eugene Nudelman, Yoav Shoham
Article No.: 22
Is it possible to predict how long an algorithm will take to solve a previously-unseen instance of an NP-complete problem? If so, what uses can be found for models that make such predictions? This article provides answers to these...
Quantifying inefficiency in cost-sharing mechanisms
Tim Roughgarden, Mukund Sundararajan
Article No.: 23
In a cost-sharing problem, several participants with unknown preferences vie to receive some good or service, and each possible outcome has a known cost. A cost-sharing mechanism is a protocol that decides which participants are allocated a good...
The complexity of obstruction-free implementations
Hagit Attiya, Rachid Guerraoui, Danny Hendler, Petr Kuznetsov
Article No.: 24
Obstruction-free implementations of concurrent objects are optimized for the common case where there is no step contention, and were recently advocated as a solution to the costs associated with synchronization without locks. In this...