Noam Nisan

Orcid: 0000-0003-3106-6304

Affiliations:
  • Hebrew University of Jerusalem, Israel


According to our database1, Noam Nisan authored at least 171 papers between 1988 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Learning to Maximize Gains From Trade in Small Markets.
CoRR, 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

Finding a Hidden Edge.
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
The AND-OR Game.
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

Networks of Complements.
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

Bertrand networks.
Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

2012
Combinatorial agency.
J. Econ. Theory, 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

Best-response auctions.
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

On Yao's XOR-Lemma.
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

Combinatorial agency.
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

On Yao's XOR-Lemma
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
Hardness vs Randomness.
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

RL <= SC.
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


  Loading...