Noam Nisan
According to our database^{1},
Noam Nisan
authored at least 188 papers
between 1988 and 2019.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at id.loc.gov

at dnb.info

at isni.org
On csauthors.net:
Bibliography
2019
Fair Allocation through Competitive Equilibrium from Generic Incomes.
Proceedings of the Conference on Fairness, Accountability, and Transparency, 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 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
Approximate revenue maximization with multiple items.
J. Economic Theory, 2017
An Experimental Evaluation of RegretBased 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 singleparameter auction environments.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017
The menusize 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 ANDOR Game.
ACM Trans. Economics and Comput., 2016
Correlated and Coarse Equilibria of SingleItem Auctions.
Proceedings of the Web and Internet Economics  12th International Conference, 2016
Smooth Boolean Functions are Easy: Efficient Algorithms for LowSensitivity 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
Online ascending auctions for gradually expiring items.
J. Economic Theory, 2015
Multiunit auctions: Beyond Roberts.
J. Economic Theory, 2015
Smooth Boolean functions are easy: efficient algorithms for lowsensitivity functions.
Electronic Colloquium on Computational Complexity (ECCC), 2015
Welfare Maximization with Limited Interaction.
Electronic Colloquium on Computational Complexity (ECCC), 2015
A Stable Marriage Requires Communication.
Proceedings of the TwentySixth Annual ACMSIAM 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 menusize 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
Truthful randomized mechanisms for combinatorial auctions.
J. Comput. Syst. Sci., 2012
Multiunit auctions with budget limits.
Games and Economic Behavior, 2012
Incentive Compatible Two Player Cake Cutting.
Proceedings of the Internet and Network Economics  8th International Workshop, 2012
The ANDOR Game: Equilibrium Characterization  (Working Paper).
Proceedings of the Internet and Network Economics  8th International Workshop, 2012
Sketching valuation functions.
Proceedings of the TwentyThird Annual ACMSIAM 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 bestrespond?
SIGecom Exchanges, 2011
A Quantitative Version of the GibbardSatterthwaite Theorem for Three Alternatives.
SIAM J. Comput., 2011
Limitations of VCGbased mechanisms.
Combinatorica, 2011
Bestresponse auctions.
Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC2011), 2011
Nonprice equilibria in markets of discrete goods.
Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC2011), 2011
Multiunit auctions: beyond roberts.
Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC2011), 2011
Incentivecompatible distributed greedy protocols.
Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011
BestResponse Mechanisms.
Proceedings of the Innovations in Computer Science, 2011
On Yao's XORLemma.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011
On Constructing 11 OneWay 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 ComplementFree Bidders.
Math. Oper. Res., 2010
Informational limitations of ascending combinatorial auctions.
J. Economic Theory, 2010
Mechanisms for MultiUnit 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 TwentyFirst Annual ACMSIAM 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
Mechanisms for a spatially distributed market.
Games and Economic Behavior, 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
FreeRiding and FreeLabor 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
Compact nameindependent routing with minimum stretch.
ACM Trans. Algorithms, 2008
Theory research at Google.
SIGACT News, 2008
Truthful approximation mechanisms for restricted combinatorial auctions.
Games and Economic Behavior, 2008
Asynchronous BestReply 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
Multiunit Auctions with Budget Limits.
Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008
FairplayMP: a system for secure multiparty 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: 9780262640688, 2008
2007
Computationally Feasible VCG Mechanisms.
J. Artif. Intell. Res., 2007
Auctions with Severely Bounded Communication.
J. Artif. Intell. Res., 2007
Limitations of VCGbased mechanisms.
Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007
Mechanisms for multiunit auctions.
Proceedings of the Proceedings 8th ACM Conference on Electronic Commerce (EC2007), 2007
2006
The communication requirements of efficient allocations and supporting prices.
J. Economic Theory, 2006
Combinatorial auctions with decreasing marginal utilities.
Games and Economic Behavior, 2006
A Note on the computational hardness of evolutionary stable strategies.
Electronic Colloquium on Computational Complexity (ECCC), 2006
Approximations by ComputationallyEfficient VCGBased 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 (EC2006), 2006
2005
Exponential communication inefficiency of demand queries.
Proceedings of the 10th Conference on Theoretical Aspects of Rationality and Knowledge (TARK2005), 2005
Approximation algorithms for combinatorial auctions with complementfree 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 ACMSIAM Symposium on Discrete Algorithms, 2005
On the computational power of iterative auctions.
Proceedings of the Proceedings 6th ACM Conference on Electronic Commerce (EC2005), 2005
The Elements of Computing Systems  Building a Modern Computer from First Principles.
MIT Press, ISBN: 9780262140874, 2005
2004
Competitive analysis of incentive compatible online auctions.
Theor. Comput. Sci., 2004
Concurrent Auctions Across The Supply Chain.
J. Artif. Intell. Res., 2004
Fairplay  Secure TwoParty Computation System.
Proceedings of the 13th USENIX Security Symposium, August 913, 2004, San Diego, CA, USA, 2004
Compact nameindependent 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 (EC2004), 2004
2003
Incentive compatible multi unit combinatorial auctions.
Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK2003), 2003
Towards a Characterization of Truthful Combinatorial Auctions.
Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003
Multiplayer and Multiround 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
Neighborhood Preserving Hashing and Approximate Queries.
SIAM J. Discrete Math., 2001
Algorithmic Mechanism Design.
Games and Economic Behavior, 2001
Errata for: "On randomized oneround communication complexity".
Computational Complexity, 2001
OnLine 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 (EC2001), 2001
Combinatorial auctions with decreasing marginal utilities.
Proceedings of the Proceedings 3rd ACM Conference on Electronic Commerce (EC2001), 2001
Concurrent auctions across the supply chain.
Proceedings of the Proceedings 3rd ACM Conference on Electronic Commerce (EC2001), 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 (EC00), 2000
Bidding and allocation in combinatorial auctions.
Proceedings of the 2nd ACM Conference on Electronic Commerce (EC00), 2000
Competitive analysis of incentive compatible online auctions.
Proceedings of the 2nd ACM Conference on Electronic Commerce (EC00), 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
Tradeoffs between Communication Throughput and Parallel Time.
J. Complexity, 1999
On Randomized OneRound Communication Complexity.
Computational Complexity, 1999
Algorithmic Mechanism Design (Extended Abstract).
Proceedings of the ThirtyFirst 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
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 TwentyNinth Annual ACM Symposium on the Theory of Computing, 1997
Communication complexity.
Cambridge University Press, ISBN: 9780521560672, 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. Discrete Math., 1995
Amortized Communication Complexity.
SIAM J. Comput., 1995
On Yao's XORLemma
Electronic Colloquium on Computational Complexity (ECCC), 1995
On Constructing 11 OneWay Functions
Electronic Colloquium on Computational Complexity (ECCC), 1995
On Rank vs. Communication Complexity.
Combinatorica, 1995
Symmetric Logspace is Closed Under Complement.
Chicago J. Theor. Comput. Sci., 1995
On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern.
Proceedings of the TwentySeventh Annual ACM Symposium on Theory of Computing, 1995
Symmetric logspace is closed under complement.
Proceedings of the TwentySeventh Annual ACM Symposium on Theory of Computing, 1995
On data structures and asymmetric communication complexity.
Proceedings of the TwentySeventh Annual ACM Symposium on Theory of Computing, 1995
On randomized oneround communication complexity.
Proceedings of the TwentySeventh 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 Rank vs. Communication Complexity
Electronic Colloquium on Computational Complexity (ECCC), 1994
On the Degree of Boolean Functions as Real Polynomials.
Computational Complexity, 1994
RL <= SC.
Computational Complexity, 1994
Tradeoffs between communication throughput and parallel time.
Proceedings of the TwentySixth Annual ACM Symposium on Theory of Computing, 1994
Pseudorandomness for network algorithms.
Proceedings of the TwentySixth Annual ACM Symposium on Theory of Computing, 1994
Neighborhood Preserving Hashing and Approximate Queries.
Proceedings of the Fifth Annual ACMSIAM Symposium on Discrete Algorithms. 2325 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
On ReadOnce 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.
Computational Complexity, 1993
More deterministic simulation in logspace.
Proceedings of the TwentyFifth Annual ACM Symposium on Theory of Computing, 1993
A parallel approximation algorithm for positive linear programming.
Proceedings of the TwentyFifth Annual ACM Symposium on Theory of Computing, 1993
1992
Multiparty Protocols, Pseudorandom Generators for Logspace, and TimeSpace TradeOffs.
J. Comput. Syst. Sci., 1992
Algebraic Methods for Interactive Proof Systems.
J. ACM, 1992
Pseudorandom generators for spacebounded 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: 9780262140515, 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 NonCommutative 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 inclusionexclusion.
Combinatorica, 1990
Psuedorandom Generators for SpaceBounded 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 InclusionExclusion
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 ReadOnce 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 RandomSelfReducibility.
Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990
1989
Parallel Algorithms for ZeroOne SupplyDemand 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 Logspacehard 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