2025
Does Your Blockchain Need Multidimensional Transaction Fees?
CoRR, April, 2025
On the Welfare of EIP-1559 with Patient Bidders.
CoRR, February, 2025
2024
Learning to Maximize Gains From Trade in Small Markets.
Proceedings of the 25th ACM Conference on Economics and Computation, 2024
2023
Serial Monopoly on Blockchains.
CoRR, 2023
Asynchronous Proportional Response Dynamics in Markets with Adversarial Scheduling.
CoRR, 2023
Asynchronous Proportional Response Dynamics: Convergence in Markets with Adversarial Scheduling.
Proceedings of the Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, 2023
2022
The menu-size complexity of revenue approximation.
Games Econ. Behav., 2022
Monotonic Mechanisms for Selling Multiple Goods.
CoRR, 2022
Auctions between Regret-Minimizing Agents.
Proceedings of the WWW '22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25, 2022
Complexity of Public Goods Games on Graphs.
Proceedings of the Algorithmic Game Theory - 15th International Symposium, 2022
How and Why to Manipulate Your Own Agent: On the Incentives of Users of Learning Agents.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022
The Query Complexity of Cake Cutting.
Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022
2021
Competitive Equilibrium with Indivisible Goods and Generic Budgets.
Math. Oper. Res., 2021
How and Why to Manipulate Your Own Agent.
CoRR, 2021
Beyond Pigouvian Taxes: A Worst Case Analysis.
Proceedings of the Web and Internet Economics - 17th International Conference, 2021
Bipartite perfect matching as a real polynomial.
Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021
The Demand Query Model for Bipartite Matching.
Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021
2020
On the Effectiveness of Tracking and Testing in SEIR Models.
CoRR, 2020
Designing Committees for Mitigating Biases.
Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020
2019
Selling multiple correlated goods: Revenue maximization and menu-size complexity.
J. Econ. Theory, 2019
A stable marriage requires communication.
Games Econ. Behav., 2019
Economic efficiency requires interaction.
Games Econ. Behav., 2019
Competitive Equilibrium with Generic Budgets: Beyond Additive.
CoRR, 2019
Matching for the Israeli "Mechinot" Gap-Year Programs: Handling Rich Diversity Requirements.
CoRR, 2019
The communication complexity of local search.
Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019
Fair Allocation through Competitive Equilibrium from Generic Incomes.
Proceedings of the Conference on Fairness, Accountability, and Transparency, 2019
Matching for the Israeli: Handling Rich Diversity Requirements.
Proceedings of the 2019 ACM Conference on Economics and Computation, 2019
Communication Complexity of Cake Cutting.
Proceedings of the 2019 ACM Conference on Economics and Computation, 2019
2018
Public Projects, Boolean Functions, and the Borders of Border's Theorem.
ACM Trans. Economics and Comput., 2018
The query complexity of correlated equilibria.
Games Econ. Behav., 2018
Optimal Deterministic Mechanisms for an Additive Buyer.
Proceedings of the 2018 ACM Conference on Economics and Computation, 2018
Universal Growth in Production Economies.
Proceedings of the Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, 2018
2017
Approximate revenue maximization with multiple items.
J. Econ. Theory, 2017
Competitive Equilibria with Indivisible Goods and Generic Budgets.
CoRR, 2017
An Experimental Evaluation of Regret-Based Econometrics.
Proceedings of the 26th International Conference on World Wide Web, 2017
ERA: A Framework for Economic Resource Allocation for the Cloud.
Proceedings of the 26th International Conference on World Wide Web Companion, 2017
Efficient empirical revenue maximization in single-parameter auction environments.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017
A "Quantal Regret" Method for Structural Econometrics in Repeated Games.
Proceedings of the 2017 ACM Conference on Economics and Computation, 2017
Selling Complementary Goods: Dynamics, Efficiency and Revenue.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017
2016
ACM Trans. Economics and Comput., 2016
Correlated and Coarse Equilibria of Single-Item Auctions.
Proceedings of the Web and Internet Economics - 12th International Conference, 2016
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016
Knuth Prize Lecture: Complexity of Communication in Markets.
Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016
2015
Online ascending auctions for gradually expiring items.
J. Econ. Theory, 2015
Multi-unit auctions: Beyond Roberts.
J. Econ. Theory, 2015
Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions.
Electron. Colloquium Comput. Complex., 2015
Welfare Maximization with Limited Interaction.
Electron. Colloquium Comput. Complex., 2015
2014
An experimental evaluation of bidders' behavior in ad auctions.
Proceedings of the 23rd International World Wide Web Conference, 2014
Price competition in online combinatorial markets.
Proceedings of the 23rd International World Wide Web Conference, 2014
Sampling and Representation Complexity of Revenue Maximization.
Proceedings of the Web and Internet Economics - 10th International Conference, 2014
On the efficiency of the walrasian mechanism.
Proceedings of the ACM Conference on Economics and Computation, 2014
2013
Introduction to the Special Issue on Algorithmic Game Theory.
ACM Trans. Economics and Comput., 2013
Electronic Markets and Auctions (Dagstuhl Seminar 13461).
Dagstuhl Reports, 2013
The menu-size complexity of auctions.
Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013
Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013
2012
Truthful randomized mechanisms for combinatorial auctions.
J. Comput. Syst. Sci., 2012
Multi-unit auctions with budget limits.
Games Econ. Behav., 2012
Doubleclick Ad Exchange Auction
CoRR, 2012
Incentive Compatible Two Player Cake Cutting.
Proceedings of the Internet and Network Economics - 8th International Workshop, 2012
The AND-OR Game: Equilibrium Characterization - (Working Paper).
Proceedings of the Internet and Network Economics - 8th International Workshop, 2012
Sketching valuation functions.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012
Fair allocation without trade.
Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 2012
2011
When is it best to best-respond?
SIGecom Exch., 2011
A Quantitative Version of the Gibbard-Satterthwaite Theorem for Three Alternatives.
SIAM J. Comput., 2011
Limitations of VCG-based mechanisms.
Comb., 2011
Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011
Non-price equilibria in markets of discrete goods.
Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011
Incentive-compatible distributed greedy protocols.
Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011
Best-Response Mechanisms.
Proceedings of the Innovations in Computer Science, 2011
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
On Constructing 1-1 One-Way Functions.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
2010
Approximation Algorithms for Combinatorial Auctions with Complement-Free Bidders.
Math. Oper. Res., 2010
Informational limitations of ascending combinatorial auctions.
J. Econ. Theory, 2010
Mechanisms for Multi-Unit Auctions.
J. Artif. Intell. Res., 2010
Mixed Strategies in Combinatorial Agency.
J. Artif. Intell. Res., 2010
Google's Auction for TV Ads.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010
2009
On the Computational Power of Demand Queries.
SIAM J. Comput., 2009
Two simplified proofs for Roberts' theorem.
Soc. Choice Welf., 2009
Mechanisms for a spatially distributed market.
Games Econ. Behav., 2009
A synthesis course in hardware architecture, compilers, and software engineering.
Proceedings of the 40th SIGCSE Technical Symposium on Computer Science Education, 2009
A Modular Approach to Roberts' Theorem.
Proceedings of the Algorithmic Game Theory, Second International Symposium, 2009
Free-Riding and Free-Labor in Combinatorial Agency.
Proceedings of the Algorithmic Game Theory, Second International Symposium, 2009
Google's Auction for TV Ads.
,
,
,
,
,
,
,
,
,
,
Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009
2008
Compact name-independent routing with minimum stretch.
ACM Trans. Algorithms, 2008
Theory research at Google.
,
,
,
,
,
,
,
,
,
,
,
SIGACT News, 2008
Truthful approximation mechanisms for restricted combinatorial auctions.
Games Econ. Behav., 2008
Asynchronous Best-Reply Dynamics.
Proceedings of the Internet and Network Economics, 4th International Workshop, 2008
Elections Can be Manipulated Often.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
FairplayMP: a system for secure multi-party computation.
Proceedings of the 2008 ACM Conference on Computer and Communications Security, 2008
The Elements of Computing Systems - Building a Modern Computer from First Principles.
MIT Press, ISBN: 978-0-262-64068-8, 2008
2007
Computationally Feasible VCG Mechanisms.
J. Artif. Intell. Res., 2007
Auctions with Severely Bounded Communication.
J. Artif. Intell. Res., 2007
2006
The communication requirements of efficient allocations and supporting prices.
J. Econ. Theory, 2006
Combinatorial auctions with decreasing marginal utilities.
Games Econ. Behav., 2006
A Note on the computational hardness of evolutionary stable strategies.
Electron. Colloquium Comput. Complex., 2006
Approximations by Computationally-Efficient VCG-Based Mechanisms.
Electron. Colloquium Comput. Complex., 2006
Proceedings of the Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), 2006
2005
Exponential communication inefficiency of demand queries.
Proceedings of the 10th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2005), 2005
On the computational power of iterative auctions.
Proceedings of the Proceedings 6th ACM Conference on Electronic Commerce (EC-2005), 2005
The Elements of Computing Systems - Building a Modern Computer from First Principles.
MIT Press, ISBN: 978-0-262-14087-4, 2005
2004
Competitive analysis of incentive compatible on-line auctions.
Theor. Comput. Sci., 2004
Concurrent Auctions Across The Supply Chain.
J. Artif. Intell. Res., 2004
Fairplay - Secure Two-Party Computation System.
Proceedings of the 13th USENIX Security Symposium, August 9-13, 2004, San Diego, CA, USA, 2004
2003
Incentive compatible multi unit combinatorial auctions.
Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2003), 2003
Towards a Characterization of Truthful Combinatorial Auctions.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003
Multi-player and Multi-round Auctions with Severely Bounded Communication.
Proceedings of the Algorithms, 2003
2002
The Communication Complexity of Approximate Set Packing and Covering.
Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002
Auctions with Severely Bounded Communication.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002
2001
Neighborhood Preserving Hashing and Approximate Queries.
SIAM J. Discret. Math., 2001
Algorithmic Mechanism Design.
Games Econ. Behav., 2001
Errata for: "On randomized one-round communication complexity".
Comput. Complex., 2001
On-Line Markets for Distributed Object Services: The MAJIC System.
Proceedings of the 3rd USENIX Symposium on Internet Technologies and Systems, 2001
An efficient approximate allocation algorithm for combinatorial auctions.
Proceedings of the Proceedings 3rd ACM Conference on Electronic Commerce (EC-2001), 2001
2000
The POPCORN market. Online markets for computational resources.
Decis. Support Syst., 2000
Bidding and allocation in combinatorial auctions.
Proceedings of the 2nd ACM Conference on Electronic Commerce (EC-00), 2000
1999
Products and Help Bits in Decision Trees.
SIAM J. Comput., 1999
Fast Connected Components Algorithms for the EREW PRAM.
SIAM J. Comput., 1999
Extracting Randomness: A Survey and New Constructions.
J. Comput. Syst. Sci., 1999
Trade-offs between Communication Throughput and Parallel Time.
J. Complex., 1999
On Randomized One-Round Communication Complexity.
Comput. Complex., 1999
Algorithmic Mechanism Design (Extended Abstract).
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999
Algorithms for Selfish Agents.
Proceedings of the STACS 99, 1999
1998
Efficient approximation of product distributions.
Random Struct. Algorithms, 1998
On Data Structures and Asymmetric Communication Complexity.
J. Comput. Syst. Sci., 1998
Quantum Circuits with Mixed States.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998
The POPCORN market - an online market for computational resources.
Proceedings of the First International Conference on Information and Computation Economies, 1998
Globally Distributed Computation over the Internet - The POPCORN Project.
Proceedings of the 18th International Conference on Distributed Computing Systems, 1998
1997
Pointer Jumping Requires Concurrent Read
Electron. Colloquium Comput. Complex., 1997
Lower Bounds on Arithmetic Circuits Via Partial Derivatives.
Comput. Complex., 1997
Communication complexity.
Cambridge University Press, ISBN: 978-0-521-56067-2, 1997
1996
Randomness is Linear in Space.
J. Comput. Syst. Sci., 1996
Extracting Randomness: How and Why A survey.
Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996
1995
Fractional Covers and Communication Complexity.
SIAM J. Discret. Math., 1995
Amortized Communication Complexity.
SIAM J. Comput., 1995
Electron. Colloquium Comput. Complex., 1995
On Constructing 1-1 One-Way Functions
Electron. Colloquium Comput. Complex., 1995
Symmetric Logspace is Closed Under Complement.
Chic. J. Theor. Comput. Sci., 1995
On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995
Lower Bounds for Arithmetic Circuits via Partial Serivatives (Preliminary Version).
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995
1994
J. Comput. Syst. Sci., 1994
On Rank vs. Communication Complexity
Electron. Colloquium Comput. Complex., 1994
On the Degree of Boolean Functions as Real Polynomials.
Comput. Complex., 1994
Pseudorandomness for network algorithms.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994
1993
On Dice and Coins: Models of Computation for Random Generation
Inf. Comput., June, 1993
On Read-Once vs. Multiple Access to Randomness in Logspace.
Theor. Comput. Sci., 1993
The Computational Complexity of Universal Hashing.
Theor. Comput. Sci., 1993
Rounds in Communication Complexity Revisited.
SIAM J. Comput., 1993
The Effect of Random Restrictions on Formula Size.
Random Struct. Algorithms, 1993
Probabilistic Analysis of Network Flow Algorithms.
Math. Oper. Res., 1993
Constant Depth Circuits, Fourier Transform, and Learnability.
J. ACM, 1993
BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs.
Comput. Complex., 1993
More deterministic simulation in logspace.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993
A parallel approximation algorithm for positive linear programming.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993
1992
Multiparty Protocols, Pseudorandom Generators for Logspace, and Time-Space Trade-Offs.
J. Comput. Syst. Sci., 1992
Algebraic Methods for Interactive Proof Systems.
J. ACM, 1992
Pseudorandom generators for space-bounded computation.
Comb., 1992
Approximations of General Independent Distributions
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992
Undirected Connectivity in O(log ^1.5 n) Space
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992
Using hard problems to create pseudorandom generators.
ACM Distinguished Dissertations, MIT Press, ISBN: 978-0-262-14051-5, 1992
1991
CREW PRAMs and Decision Trees.
SIAM J. Comput., 1991
Pseudorandom bits for constant depth circuits.
Comb., 1991
Lower Bounds for Non-Commutative Computation (Extended Abstract)
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991
BPP has Subexponential Time Simulation unless EXPTIME has Pubishable Proofs.
Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991
1990
Approximate inclusion-exclusion.
Comb., 1990
Psuedorandom Generators for Space-Bounded Computation
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990
Lower Bounds on Random-Self-Reducibility.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990
1989
Parallel Algorithms for Zero-One Supply-Demand Problems.
SIAM J. Discret. Math., 1989
Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989
Hardness vs. Randomness - A Survey (abstract).
Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989
1988
Hardness vs. Randomness (Extended Abstract)
Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988