| Publication | Date of Publication | Type |
|---|
| Knuth prize lecture: complexity of communication in markets | 2025-08-06 | Paper |
| Welfare maximization with limited interaction | 2025-08-05 | Paper |
scientific article; zbMATH DE number 7788374 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
Bipartite perfect matching as a real polynomial
Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing | 2023-11-14 | Paper |
Bipartite perfect matching as a real polynomial
Israel Journal of Mathematics | 2023-10-23 | Paper |
Complexity of public goods games on graphs
Algorithmic Game Theory | 2023-07-28 | Paper |
The menu-size complexity of revenue approximation
Games and Economic Behavior | 2022-07-15 | Paper |
Beyond Pigouvian taxes: a worst case analysis
(available as arXiv preprint) | 2022-07-06 | Paper |
| Mathematical logic through Python | 2022-07-05 | Paper |
Competitive equilibrium with indivisible goods and generic budgets
Mathematics of Operations Research | 2021-06-03 | Paper |
Selling complementary goods: dynamics, efficiency and revenue
(available as arXiv preprint) | 2020-05-27 | Paper |
The communication complexity of local search
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing | 2020-01-30 | Paper |
Economic efficiency requires interaction
Games and Economic Behavior | 2019-12-12 | Paper |
A stable marriage requires communication
Games and Economic Behavior | 2019-12-12 | Paper |
Selling multiple correlated goods: revenue maximization and menu-size complexity
Journal of Economic Theory | 2019-09-12 | Paper |
| Sketching valuation functions | 2019-05-10 | Paper |
Compact name-independent routing with minimum stretch
ACM Transactions on Algorithms | 2018-11-05 | Paper |
The query complexity of correlated equilibria
Games and Economic Behavior | 2018-07-12 | Paper |
Networks of complements
(available as arXiv preprint) | 2017-12-19 | Paper |
Approximate revenue maximization with multiple items
Journal of Economic Theory | 2017-11-07 | Paper |
A Stable Marriage Requires Communication
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Efficient empirical revenue maximization in single-parameter auction environments
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
The menu-size complexity of revenue approximation
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing | 2017-08-17 | Paper |
Correlated and Coarse Equilibria of Single-Item Auctions
Web and Internet Economics | 2017-02-10 | Paper |
Algorithmic mechanism design (extended abstract)
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Pseudorandomness for network algorithms
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
Trade-offs between communication throughput and parallel time
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science | 2016-04-15 | Paper |
Economic efficiency requires interaction
Proceedings of the forty-sixth annual ACM symposium on Theory of computing | 2015-06-26 | Paper |
A parallel approximation algorithm for positive linear programming
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
More deterministic simulation in logspace
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
Multi-unit auctions: beyond Roberts
Journal of Economic Theory | 2015-02-13 | Paper |
Online ascending auctions for gradually expiring items
Journal of Economic Theory | 2015-02-13 | Paper |
Sampling and Representation Complexity of Revenue Maximization
Web and Internet Economics | 2015-01-07 | Paper |
Truthful randomized mechanisms for combinatorial auctions
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
| Online ascending auctions for gradually expiring items | 2014-10-13 | Paper |
Limitations of VCG-based mechanisms
Combinatorica | 2014-06-13 | Paper |
| scientific article; zbMATH DE number 6297743 (Why is no real title available?) | 2014-05-22 | Paper |
Combinatorial agency
Journal of Economic Theory | 2012-05-14 | Paper |
Truthful randomized mechanisms for combinatorial auctions
Journal of Computer and System Sciences | 2012-05-11 | Paper |
Multi-unit auctions with budget limits
Games and Economic Behavior | 2012-03-19 | Paper |
A Quantitative Version of the Gibbard–Satterthwaite Theorem for Three Alternatives
SIAM Journal on Computing | 2011-10-18 | Paper |
On Yao's XOR-lemma
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
On constructing 1-1 one-way functions
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | Paper |
Approximation algorithms for combinatorial auctions with complement-free bidders
Mathematics of Operations Research | 2011-04-27 | Paper |
On the computational power of demand queries
SIAM Journal on Computing | 2010-09-06 | Paper |
Approximation algorithms for combinatorial auctions with complement-free bidders
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Mixed strategies in combinatorial agency
Journal of Artificial Intelligence Research | 2010-08-06 | Paper |
Informational limitations of ascending combinatorial auctions
Journal of Economic Theory | 2010-05-21 | Paper |
Mechanisms for multi-unit auctions
Journal of Artificial Intelligence Research | 2010-03-15 | Paper |
Algorithms - ESA 2003
Lecture Notes in Computer Science | 2010-03-03 | Paper |
A modular approach to Roberts' theorem
Algorithmic Game Theory | 2009-12-01 | Paper |
Free-riding and free-labor in combinatorial agency
Algorithmic Game Theory | 2009-12-01 | Paper |
Two simplified proofs for Roberts' theorem
Social Choice and Welfare | 2009-10-19 | Paper |
Mechanisms for a spatially distributed market
Games and Economic Behavior | 2009-07-15 | Paper |
Computationally feasible VCG mechanisms
(available as arXiv preprint) | 2009-04-28 | Paper |
scientific article; zbMATH DE number 5547873 (Why is no real title available?)
(available as arXiv preprint) | 2009-04-28 | Paper |
Truthful approximation mechanisms for restricted combinatorial auctions
Games and Economic Behavior | 2009-01-26 | Paper |
| Limitations of VCG-based mechanisms | 2009-01-05 | Paper |
| scientific article; zbMATH DE number 5343724 (Why is no real title available?) | 2008-09-12 | Paper |
| Combinatorial auctions | 2008-09-12 | Paper |
Weak Monotonicity Characterizes Deterministic Dominant-Strategy Implementation
Econometrica | 2007-02-05 | Paper |
Combinatorial auctions with decreasing marginal utilities
Games and Economic Behavior | 2006-09-28 | Paper |
The communication requirements of efficient allocations and supporting prices
Journal of Economic Theory | 2006-07-20 | Paper |
scientific article; zbMATH DE number 2243363 (Why is no real title available?)
(available as arXiv preprint) | 2006-01-04 | Paper |
Competitive analysis of incentive compatible on-line auctions
Theoretical Computer Science | 2004-10-27 | Paper |
| scientific article; zbMATH DE number 2086678 (Why is no real title available?) | 2004-08-11 | Paper |
Errata for: ``On randomized one-round communication complexity''
Computational Complexity | 2003-08-26 | Paper |
scientific article; zbMATH DE number 1775384 (Why is no real title available?)
(available as arXiv preprint) | 2002-08-01 | Paper |
Neighborhood preserving hashing and approximate queries
SIAM Journal on Discrete Mathematics | 2002-04-23 | Paper |
| scientific article; zbMATH DE number 1263186 (Why is no real title available?) | 2001-08-27 | Paper |
| scientific article; zbMATH DE number 1559570 (Why is no real title available?) | 2001-02-28 | Paper |
Algorithmic mechanism design
Games and Economic Behavior | 2001-01-01 | Paper |
Extracting randomness: A survey and new constructions
Journal of Computer and System Sciences | 2000-02-17 | Paper |
| Efficient approximation of product distributions | 1999-12-19 | Paper |
scientific article; zbMATH DE number 1332655 (Why is no real title available?)
Chicago Journal of Theoretical Computer Science | 1999-09-07 | Paper |
On randomized one-round communication complexity
Computational Complexity | 1999-09-01 | Paper |
| scientific article; zbMATH DE number 1261803 (Why is no real title available?) | 1999-08-31 | Paper |
| scientific article; zbMATH DE number 1263189 (Why is no real title available?) | 1999-06-29 | Paper |
Trade-offs between communication throughput and parallel time
Journal of Complexity | 1999-05-11 | Paper |
| scientific article; zbMATH DE number 1256637 (Why is no real title available?) | 1999-04-22 | Paper |
| scientific article; zbMATH DE number 1263236 (Why is no real title available?) | 1999-03-16 | Paper |
Products and Help Bits in Decision Trees
SIAM Journal on Computing | 1999-02-22 | Paper |
Fast Connected Components Algorithms for the EREW PRAM
SIAM Journal on Computing | 1999-02-22 | Paper |
On data structures and asymmetric communication complexity
Journal of Computer and System Sciences | 1999-01-06 | Paper |
Lower bounds on arithmetic circuits via partial derivatives
Computational Complexity | 1998-06-11 | Paper |
| scientific article; zbMATH DE number 1003256 (Why is no real title available?) | 1997-04-23 | Paper |
On rank vs. communication complexity
Combinatorica | 1996-09-15 | Paper |
Randomness is linear in space
Journal of Computer and System Sciences | 1996-07-16 | Paper |
| Communication Complexity | 1996-04-24 | Paper |
Amortized Communication Complexity
SIAM Journal on Computing | 1996-01-28 | Paper |
Fractional Covers and Communication Complexity
SIAM Journal on Discrete Mathematics | 1995-07-10 | Paper |
On the degree of Boolean functions as real polynomials
Computational Complexity | 1995-04-06 | Paper |
| scientific article; zbMATH DE number 1263251 (Why is no real title available?) | 1995-01-01 | Paper |
Hardness vs randomness
Journal of Computer and System Sciences | 1994-11-06 | Paper |
Algebraic methods for interactive proof systems
Journal of the ACM | 1994-08-21 | Paper |
\(\text{RL}\subseteq \text{SC}\)
Computational Complexity | 1994-06-19 | Paper |
BPP has subexponential time simulations unless EXPTIME has publishable proofs
Computational Complexity | 1994-05-08 | Paper |
| scientific article; zbMATH DE number 524134 (Why is no real title available?) | 1994-03-24 | Paper |
Constant depth circuits, Fourier transform, and learnability
Journal of the ACM | 1993-12-09 | Paper |
On dice and coins: Models of computation for random generation
Information and Computation | 1993-08-30 | Paper |
The effect of random restrictions on formula size
Random Structures & Algorithms | 1993-06-29 | Paper |
Probabilistic Analysis of Network Flow Algorithms
Mathematics of Operations Research | 1993-06-29 | Paper |
The computational complexity of universal hashing
Theoretical Computer Science | 1993-05-16 | Paper |
Rounds in Communication Complexity Revisited
SIAM Journal on Computing | 1993-05-16 | Paper |
On read-once vs. multiple access to randomness in logspace
Theoretical Computer Science | 1993-05-16 | Paper |
Pseudorandom generators for space-bounded computation
Combinatorica | 1993-03-10 | Paper |
Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
Journal of Computer and System Sciences | 1993-01-17 | Paper |
CREW PRAM<scp>s</scp> and Decision Trees
SIAM Journal on Computing | 1992-06-27 | Paper |
Approximate inclusion-exclusion
Combinatorica | 1992-06-25 | Paper |
Pseudorandom bits for constant depth circuits
Combinatorica | 1991-01-01 | Paper |
| scientific article; zbMATH DE number 4117876 (Why is no real title available?) | 1989-01-01 | Paper |
On the cover time of random walks on graphs
Journal of Theoretical Probability | 1989-01-01 | Paper |
Parallel Algorithms for Zero-One Supply-Demand Problems
SIAM Journal on Discrete Mathematics | 1989-01-01 | Paper |
