Noam Nisan

According to our database1, Noam Nisan authored at least 162 papers between 1988 and 2019.

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

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
The query complexity of correlated equilibria.
Games and Economic Behavior, 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
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

The menu-size complexity of revenue approximation.
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

Smooth Boolean Functions are Easy: Efficient Algorithms for Low-Sensitivity Functions.
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 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
A Stable Marriage Requires Communication.
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

Public Projects, Boolean Functions, and the Borders of Border's Theorem.
Proceedings of the Sixteenth ACM Conference on Economics and Computation, 2015

Welfare Maximization with Limited Interaction.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 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

Economic efficiency requires interaction.
Proceedings of the Symposium on Theory of Computing, 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. Economic Theory, 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

Approximate revenue maximization with multiple items.
Proceedings of the 13th ACM Conference on Electronic Commerce, 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 Exchanges, 2011

A Quantitative Version of the Gibbard-Satterthwaite Theorem for Three Alternatives.
SIAM J. Comput., 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

Multi-unit auctions: beyond roberts.
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
Informational limitations of ascending combinatorial auctions.
J. Economic Theory, 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.
Social Choice and Welfare, 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

Google's Auction for TV Ads.
Proceedings of the Algorithms, 2009

2008
Theory research at Google.
SIGACT News, 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

Multi-unit Auctions with Budget Limits.
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
Auctions with Severely Bounded Communication.
J. Artif. Intell. Res., 2007

Limitations of VCG-based mechanisms.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Mechanisms for multi-unit auctions.
Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC-2007), 2007

2006
The communication requirements of efficient allocations and supporting prices.
J. Economic Theory, 2006

A Note on the computational hardness of evolutionary stable strategies.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Approximations by Computationally-Efficient VCG-Based Mechanisms.
Electronic Colloquium on Computational Complexity (ECCC), 2006

Mixed Strategies in Combinatorial Agency.
Proceedings of the Internet and Network Economics, Second International Workshop, 2006

Truthful randomized mechanisms for combinatorial auctions.
Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 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

Approximation algorithms for combinatorial auctions with complement-free bidders.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Online ascending auctions for gradually expiring items.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 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
Fairplay - Secure Two-Party Computation System.
Proceedings of the 13th USENIX Security Symposium, August 9-13, 2004, San Diego, CA, USA, 2004

Compact name-independent routing with minimum stretch.
Proceedings of the SPAA 2004: Proceedings of the Sixteenth Annual ACM Symposium on Parallelism in Algorithms and Architectures, 2004

Mechanisms for a spatially distributed market.
Proceedings of the Proceedings 5th ACM Conference on Electronic Commerce (EC-2004), 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

Truthful Approximation Mechanisms for Restricted Combinatorial Auctions.
Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, July 28, 2002

2001
Algorithmic Mechanism Design.
Games and Economic Behavior, 2001

Errata for: "On randomized one-round communication complexity".
Computational Complexity, 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

Combinatorial auctions with decreasing marginal utilities.
Proceedings of the Proceedings 3rd ACM Conference on Electronic Commerce (EC-2001), 2001

Concurrent auctions across the supply chain.
Proceedings of the Proceedings 3rd ACM Conference on Electronic Commerce (EC-2001), 2001

2000
The POPCORN market. Online markets for computational resources.
Decision Support Systems, 2000

Computationally feasible VCG mechanisms.
Proceedings of the 2nd ACM Conference on Electronic Commerce (EC-00), 2000

Bidding and allocation in combinatorial auctions.
Proceedings of the 2nd ACM Conference on Electronic Commerce (EC-00), 2000

Competitive analysis of incentive compatible on-line 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

Extracting Randomness: A Survey and New Constructions.
J. Comput. Syst. Sci., 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

Quantum Circuits with Mixed States.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 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
Electronic Colloquium on Computational Complexity (ECCC), 1997

Lower Bounds on Arithmetic Circuits Via Partial Derivatives.
Computational Complexity, 1997

Pointer Jumping Requires Concurrent Read.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 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
Amortized Communication Complexity.
SIAM J. Comput., 1995

On Yao's XOR-Lemma
Electronic Colloquium on Computational Complexity (ECCC), 1995

On Constructing 1-1 One-Way Functions
Electronic Colloquium on Computational Complexity (ECCC), 1995

On Rank vs. Communication Complexity.
Combinatorica, 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

Symmetric logspace is closed under complement.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

On data structures and asymmetric communication complexity.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

On randomized one-round communication complexity.
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

Symmetric Logspace is Closed Under Complement
Electronic Colloquium on Computational Complexity (ECCC), 1994

On the Degree of Boolean Functions as Real Polynomials.
Computational Complexity, 1994

RL <= SC.
Computational Complexity, 1994

Trade-offs between communication throughput and parallel time.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Pseudorandomness for network algorithms.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Neighborhood Preserving Hashing and Approximate Queries.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

On Rank vs. Communication Complexity
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

Products and Help Bits in Decision Trees
Proceedings of the 35th Annual Symposium on Foundations of Computer Science, 1994

1993
On Dice and Coins: Models of Computation for Random Generation
Inf. Comput., June, 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.
Computational Complexity, 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.
Combinatorica, 1992

On the Degree of Boolean Functions as Real Polynomials
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

RL ⊆ SC
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Approximations of General Independent Distributions
Proceedings of the 24th Annual ACM Symposium on Theory of Computing, 1992

Fast Connected Components Algorithms for the EREW PRAM.
Proceedings of the 4th Annual ACM Symposium on Parallel Algorithms and Architectures, 1992

Undirected Connectivity in O(log ^1.5 n) Space
Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Fractional Covers and Communication Complexity.
Proceedings of the Seventh Annual Structure in Complexity Theory Conference, 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.
Combinatorica, 1991

Rounds in Communication Complexity Revisited
Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 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.
Combinatorica, 1990

Psuedorandom Generators for Space-Bounded Computation
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

The Computational Complexity of Universal Hashing
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Approximate Inclusion-Exclusion
Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Algebraic Methods for Interactive Proof Systems
Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

On Read-Once vs. Multiple Access to Randomness in Logspace.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

The Computational Complexity of Universal Hashing.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 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. Discrete Math., 1989

CREW PRAMs and Decision Trees
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract)
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

On Dice and Coins: Models of Computation for Random Generation.
Proceedings of the Automata, Languages and Programming, 16th International Colloquium, 1989

Constant Depth Circuits, Fourier Transform, and Learnability
Proceedings of the 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October, 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...