Noam Nisan

Amitai Frey

CoRR, 2024

2023

Serial Monopoly on Blockchains.

[BibT_eX]

[DOI]

CoRR, 2023

Asynchronous Proportional Response Dynamics in Markets with Adversarial Scheduling.

[BibT_eX]

[DOI]

Menahem Levy

CoRR, 2023

Asynchronous Proportional Response Dynamics: Convergence in Markets with Adversarial Scheduling.

[BibT_eX]

[DOI]

Menahem Levy

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.

[BibT_eX]

[DOI]

Games Econ. Behav., 2022

Monotonic Mechanisms for Selling Multiple Goods.

[BibT_eX]

[DOI]

Ran Ben Moshe

CoRR, 2022

Finding a Hidden Edge.

[BibT_eX]

[DOI]

Ron Kupfer

CoRR, 2022

Auctions between Regret-Minimizing Agents.

[BibT_eX]

[DOI]

Proceedings of the WWW '22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25, 2022

Complexity of Public Goods Games on Graphs.

[BibT_eX]

[DOI]

Matan Gilboa

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.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

Simina Brânzei

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.

[BibT_eX]

[DOI]

Math. Oper. Res., 2021

How and Why to Manipulate Your Own Agent.

[BibT_eX]

[DOI]

CoRR, 2021

Beyond Pigouvian Taxes: A Worst Case Analysis.

[BibT_eX]

[DOI]

Ruty Mundel

Proceedings of the Web and Internet Economics - 17th International Conference, 2021

Bipartite perfect matching as a real polynomial.

[BibT_eX]

[DOI]

Gal Beniamini

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

The Demand Query Model for Bipartite Matching.

[BibT_eX]

[DOI]

Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms, 2021

2020

On the Effectiveness of Tracking and Testing in SEIR Models.

[BibT_eX]

[DOI]

CoRR, 2020

Designing Committees for Mitigating Biases.

[BibT_eX]

[DOI]

Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, 2020

2019

Selling multiple correlated goods: Revenue maximization and menu-size complexity.

[BibT_eX]

[DOI]

J. Econ. Theory, 2019

A stable marriage requires communication.

[BibT_eX]

[DOI]

Rafail Ostrovsky

Will Rosenbaum

Games Econ. Behav., 2019

Economic efficiency requires interaction.

[BibT_eX]

[DOI]

Sigal Oren

Games Econ. Behav., 2019

Competitive Equilibrium with Generic Budgets: Beyond Additive.

[BibT_eX]

[DOI]

CoRR, 2019

Matching for the Israeli "Mechinot" Gap-Year Programs: Handling Rich Diversity Requirements.

[BibT_eX]

[DOI]

Lior Kovalio

Assaf Romm

CoRR, 2019

The communication complexity of local search.

[BibT_eX]

[DOI]

Yakov Babichenko

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

Fair Allocation through Competitive Equilibrium from Generic Incomes.

[BibT_eX]

[DOI]

Proceedings of the Conference on Fairness, Accountability, and Transparency, 2019

Matching for the Israeli: Handling Rich Diversity Requirements.

[BibT_eX]

[DOI]

Lior Kovalio

Assaf Romm

Proceedings of the 2019 ACM Conference on Economics and Computation, 2019

Communication Complexity of Cake Cutting.

[BibT_eX]

[DOI]

Simina Brânzei

Proceedings of the 2019 ACM Conference on Economics and Computation, 2019

2018

Public Projects, Boolean Functions, and the Borders of Border's Theorem.

[BibT_eX]

[DOI]

Parikshit Gopalan

Tim Roughgarden

ACM Trans. Economics and Comput., 2018

The query complexity of correlated equilibria.

[BibT_eX]

[DOI]

Games Econ. Behav., 2018

Optimal Deterministic Mechanisms for an Additive Buyer.

[BibT_eX]

[DOI]

Aviad Rubinstein

Proceedings of the 2018 ACM Conference on Economics and Computation, 2018

Universal Growth in Production Economies.

[BibT_eX]

[DOI]

Simina Brânzei

Ruta Mehta

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.

[BibT_eX]

[DOI]

J. Econ. Theory, 2017

Competitive Equilibria with Indivisible Goods and Generic Budgets.

[BibT_eX]

[DOI]

CoRR, 2017

An Experimental Evaluation of Regret-Based Econometrics.

[BibT_eX]

[DOI]

Gali Noti

Proceedings of the 26th International Conference on World Wide Web, 2017

ERA: A Framework for Economic Resource Allocation for the Cloud.

[BibT_eX]

[DOI]

Proceedings of the 26th International Conference on World Wide Web Companion, 2017

Efficient empirical revenue maximization in single-parameter auction environments.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

A "Quantal Regret" Method for Structural Econometrics in Repeated Games.

[BibT_eX]

[DOI]

Gali Noti

Proceedings of the 2017 ACM Conference on Economics and Computation, 2017

Selling Complementary Goods: Dynamics, Efficiency and Revenue.

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016

The AND-OR Game.

[BibT_eX]

[DOI]

ACM Trans. Economics and Comput., 2016

Correlated and Coarse Equilibria of Single-Item Auctions.

[BibT_eX]

[DOI]

Brendan Lucier

Proceedings of the Web and Internet Economics - 12th International Conference, 2016

Networks of Complements.

[BibT_eX]

[DOI]

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Knuth Prize Lecture: Complexity of Communication in Markets.

[BibT_eX]

[DOI]

Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science, 2016

2015

Online ascending auctions for gradually expiring items.

[BibT_eX]

[DOI]

J. Econ. Theory, 2015

Multi-unit auctions: Beyond Roberts.

[BibT_eX]

[DOI]

J. Econ. Theory, 2015

Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Welfare Maximization with Limited Interaction.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

2014

An experimental evaluation of bidders' behavior in ad auctions.

[BibT_eX]

[DOI]

Gali Noti

Ilan Yaniv

Proceedings of the 23rd International World Wide Web Conference, 2014

Price competition in online combinatorial markets.

[BibT_eX]

[DOI]

Renato Paes Leme

Proceedings of the 23rd International World Wide Web Conference, 2014

Sampling and Representation Complexity of Revenue Maximization.

[BibT_eX]

[DOI]

Shaddin Dughmi

Li Han

Proceedings of the Web and Internet Economics - 10th International Conference, 2014

On the efficiency of the walrasian mechanism.

[BibT_eX]

[DOI]

Proceedings of the ACM Conference on Economics and Computation, 2014

2013

Introduction to the Special Issue on Algorithmic Game Theory.

[BibT_eX]

[DOI]

ACM Trans. Economics and Comput., 2013

Electronic Markets and Auctions (Dagstuhl Seminar 13461).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2013

The menu-size complexity of auctions.

[BibT_eX]

[DOI]

Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

Bertrand networks.

[BibT_eX]

[DOI]

Brendan Lucier

Proceedings of the fourteenth ACM Conference on Electronic Commerce, 2013

2012

Combinatorial agency.

[BibT_eX]

[DOI]

J. Econ. Theory, 2012

Truthful randomized mechanisms for combinatorial auctions.

[BibT_eX]

[DOI]

Michael Schapira

J. Comput. Syst. Sci., 2012

Multi-unit auctions with budget limits.

[BibT_eX]

[DOI]

Games Econ. Behav., 2012

Doubleclick Ad Exchange Auction

[BibT_eX]

[DOI]

S. Muthukrishnan

CoRR, 2012

Incentive Compatible Two Player Cake Cutting.

[BibT_eX]

[DOI]

Avishay Maya

Proceedings of the Internet and Network Economics - 8th International Workshop, 2012

The AND-OR Game: Equilibrium Characterization - (Working Paper).

[BibT_eX]

[DOI]

Proceedings of the Internet and Network Economics - 8th International Workshop, 2012

Sketching valuation functions.

[BibT_eX]

[DOI]

Ashwinkumar Badanidiyuru

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Fair allocation without trade.

[BibT_eX]

[DOI]

Avital Gutman

Proceedings of the International Conference on Autonomous Agents and Multiagent Systems, 2012

2011

When is it best to best-respond?

[BibT_eX]

[DOI]

SIGecom Exch., 2011

A Quantitative Version of the Gibbard-Satterthwaite Theorem for Three Alternatives.

[BibT_eX]

[DOI]

SIAM J. Comput., 2011

Limitations of VCG-based mechanisms.

[BibT_eX]

[DOI]

Comb., 2011

Best-response auctions.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

Non-price equilibria in markets of discrete goods.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 12th ACM Conference on Electronic Commerce (EC-2011), 2011

Incentive-compatible distributed greedy protocols.

[BibT_eX]

[DOI]

Proceedings of the 30th Annual ACM Symposium on Principles of Distributed Computing, 2011

Best-Response Mechanisms.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 2011

On Yao's XOR-Lemma.

[BibT_eX]

[DOI]

Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

On Constructing 1-1 One-Way Functions.

[BibT_eX]

[DOI]

Leonid A. Levin

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.

[BibT_eX]

[DOI]

Michael Schapira

Math. Oper. Res., 2010

Informational limitations of ascending combinatorial auctions.

[BibT_eX]

[DOI]

J. Econ. Theory, 2010

Mechanisms for Multi-Unit Auctions.

[BibT_eX]

[DOI]

J. Artif. Intell. Res., 2010

Mixed Strategies in Combinatorial Agency.

[BibT_eX]

[DOI]

J. Artif. Intell. Res., 2010

Google's Auction for TV Ads.

[BibT_eX]

[DOI]

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009

On the Computational Power of Demand Queries.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

Two simplified proofs for Roberts' theorem.

[BibT_eX]

[DOI]

Ahuva Mu'alem

Soc. Choice Welf., 2009

Mechanisms for a spatially distributed market.

[BibT_eX]

[DOI]

Elan Pavlov

Games Econ. Behav., 2009

A synthesis course in hardware architecture, compilers, and software engineering.

[BibT_eX]

[DOI]

Shimon Schocken

Michal Armoni

Proceedings of the 40th SIGCSE Technical Symposium on Computer Science Education, 2009

A Modular Approach to Roberts' Theorem.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory, Second International Symposium, 2009

Free-Riding and Free-Labor in Combinatorial Agency.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory, Second International Symposium, 2009

Google's Auction for TV Ads.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th Internatilonal Colloquium, 2009

2008

Compact name-independent routing with minimum stretch.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2008

Theory research at Google.

[BibT_eX]

[DOI]

Monika Rauch Henzinger

Anastasios Sidiropoulos

SIGACT News, 2008

Truthful approximation mechanisms for restricted combinatorial auctions.

[BibT_eX]

[DOI]

Ahuva Mu'alem

Games Econ. Behav., 2008

Asynchronous Best-Reply Dynamics.

[BibT_eX]

[DOI]

Michael Schapira

Aviv Zohar

Proceedings of the Internet and Network Economics, 4th International Workshop, 2008

Elections Can be Manipulated Often.

[BibT_eX]

[DOI]

Ehud Friedgut

Gil Kalai

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

FairplayMP: a system for secure multi-party computation.

[BibT_eX]

[DOI]

Assaf Ben-David

Benny Pinkas

Proceedings of the 2008 ACM Conference on Computer and Communications Security, 2008

The Elements of Computing Systems - Building a Modern Computer from First Principles.

[BibT_eX]

[DOI]

Shimon Schocken

MIT Press, ISBN: 978-0-262-64068-8, 2008

2007

Computationally Feasible VCG Mechanisms.

[BibT_eX]

[DOI]

Amir Ronen

J. Artif. Intell. Res., 2007

Auctions with Severely Bounded Communication.

[BibT_eX]

[DOI]

J. Artif. Intell. Res., 2007

2006

The communication requirements of efficient allocations and supporting prices.

[BibT_eX]

[DOI]

J. Econ. Theory, 2006

Combinatorial auctions with decreasing marginal utilities.

[BibT_eX]

[DOI]

Benny Lehmann

Daniel Lehmann

Games Econ. Behav., 2006

A Note on the computational hardness of evolutionary stable strategies.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Approximations by Computationally-Efficient VCG-Based Mechanisms.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Combinatorial agency.

[BibT_eX]

[DOI]

Proceedings of the Proceedings 7th ACM Conference on Electronic Commerce (EC-2006), 2006

2005

Exponential communication inefficiency of demand queries.

[BibT_eX]

[DOI]

Proceedings of the 10th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2005), 2005

On the computational power of iterative auctions.

[BibT_eX]

[DOI]

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.

[BibT_eX]

Shimon Schocken

MIT Press, ISBN: 978-0-262-14087-4, 2005

2004

Competitive analysis of incentive compatible on-line auctions.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2004

Concurrent Auctions Across The Supply Chain.

[BibT_eX]

[DOI]

J. Artif. Intell. Res., 2004

Fairplay - Secure Two-Party Computation System.

[BibT_eX]

[DOI]

Proceedings of the 13th USENIX Security Symposium, August 9-13, 2004, San Diego, CA, USA, 2004

2003

Incentive compatible multi unit combinatorial auctions.

[BibT_eX]

[DOI]

Yair Bartal

Rica Gonen

Proceedings of the 9th Conference on Theoretical Aspects of Rationality and Knowledge (TARK-2003), 2003

Towards a Characterization of Truthful Combinatorial Auctions.

[BibT_eX]

[DOI]

Ahuva Mu'alem

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

Multi-player and Multi-round Auctions with Severely Bounded Communication.

[BibT_eX]

[DOI]

Proceedings of the Algorithms, 2003

2002

The Communication Complexity of Approximate Set Packing and Covering.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

Auctions with Severely Bounded Communication.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001

Neighborhood Preserving Hashing and Approximate Queries.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2001

Algorithmic Mechanism Design.

[BibT_eX]

[DOI]

Amir Ronen

Games Econ. Behav., 2001

Errata for: "On randomized one-round communication complexity".

[BibT_eX]

[DOI]

Ilan Kremer

Dana Ron

Comput. Complex., 2001

On-Line Markets for Distributed Object Services: The MAJIC System.

[BibT_eX]

[DOI]

Lior Levy

Proceedings of the 3rd USENIX Symposium on Internet Technologies and Systems, 2001

An efficient approximate allocation algorithm for combinatorial auctions.

[BibT_eX]

[DOI]

Edo Zurel

Proceedings of the Proceedings 3rd ACM Conference on Electronic Commerce (EC-2001), 2001

2000

The POPCORN market. Online markets for computational resources.

[BibT_eX]

[DOI]

Ori Regev

Decis. Support Syst., 2000

Bidding and allocation in combinatorial auctions.

[BibT_eX]

[DOI]

Proceedings of the 2nd ACM Conference on Electronic Commerce (EC-00), 2000

1999

Products and Help Bits in Decision Trees.

[BibT_eX]

[DOI]

Steven Rudich

Michael E. Saks

SIAM J. Comput., 1999

Fast Connected Components Algorithms for the EREW PRAM.

[BibT_eX]

[DOI]

David R. Karger

Michal Parnas

SIAM J. Comput., 1999

Extracting Randomness: A Survey and New Constructions.

[BibT_eX]

[DOI]

Amnon Ta-Shma

J. Comput. Syst. Sci., 1999

Trade-offs between Communication Throughput and Parallel Time.

[BibT_eX]

[DOI]

Uzi Vishkin

J. Complex., 1999

On Randomized One-Round Communication Complexity.

[BibT_eX]

[DOI]

Ilan Kremer

Dana Ron

Comput. Complex., 1999

Algorithmic Mechanism Design (Extended Abstract).

[BibT_eX]

[DOI]

Amir Ronen

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Algorithms for Selfish Agents.

[BibT_eX]

[DOI]

Proceedings of the STACS 99, 1999

1998

Efficient approximation of product distributions.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 1998

On Data Structures and Asymmetric Communication Complexity.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1998

Quantum Circuits with Mixed States.

[BibT_eX]

[DOI]

Dorit Aharonov

Alexei Y. Kitaev

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

The POPCORN market - an online market for computational resources.

[BibT_eX]

[DOI]

Ori Regev

Proceedings of the First International Conference on Information and Computation Economies, 1998

Globally Distributed Computation over the Internet - The POPCORN Project.

[BibT_eX]

[DOI]

Proceedings of the 18th International Conference on Distributed Computing Systems, 1998

1997

Pointer Jumping Requires Concurrent Read

[BibT_eX]

[DOI]

Ziv Bar-Yossef

Electron. Colloquium Comput. Complex., 1997

Lower Bounds on Arithmetic Circuits Via Partial Derivatives.

[BibT_eX]

[DOI]

Comput. Complex., 1997

Communication complexity.

[BibT_eX]

Eyal Kushilevitz

Cambridge University Press, ISBN: 978-0-521-56067-2, 1997

1996

Randomness is Linear in Space.

[BibT_eX]

[DOI]

David Zuckerman

J. Comput. Syst. Sci., 1996

Extracting Randomness: How and Why A survey.

[BibT_eX]

[DOI]

Proceedings of the Eleveth Annual IEEE Conference on Computational Complexity, 1996

1995

Fractional Covers and Communication Complexity.

[BibT_eX]

[DOI]

Mauricio Karchmer

Eyal Kushilevitz

SIAM J. Discret. Math., 1995

Amortized Communication Complexity.

[BibT_eX]

[DOI]

SIAM J. Comput., 1995

On Yao's XOR-Lemma

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1995

On Constructing 1-1 One-Way Functions

[BibT_eX]

[DOI]

Leonid A. Levin

Electron. Colloquium Comput. Complex., 1995

On Rank vs. Communication Complexity.

[BibT_eX]

[DOI]

Comb., 1995

Symmetric Logspace is Closed Under Complement.

[BibT_eX]

[DOI]

Amnon Ta-Shma

Chic. J. Theor. Comput. Sci., 1995

On the complexity of bilinear forms: dedicated to the memory of Jacques Morgenstern.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Lower Bounds for Arithmetic Circuits via Partial Serivatives (Preliminary Version).

[BibT_eX]

[DOI]

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

Hardness vs Randomness.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1994

On the Degree of Boolean Functions as Real Polynomials.

[BibT_eX]

[DOI]

Mario Szegedy

Comput. Complex., 1994

RL <= SC.

[BibT_eX]

[DOI]

Comput. Complex., 1994

Pseudorandomness for network algorithms.

[BibT_eX]

[DOI]

Russell Impagliazzo

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

1993

On Dice and Coins: Models of Computation for Random Generation

[BibT_eX]

[DOI]

Inf. Comput., June, 1993

On Read-Once vs. Multiple Access to Randomness in Logspace.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1993

The Computational Complexity of Universal Hashing.

[BibT_eX]

[DOI]

Prasoon Tiwari

Theor. Comput. Sci., 1993

Rounds in Communication Complexity Revisited.

[BibT_eX]

[DOI]

SIAM J. Comput., 1993

The Effect of Random Restrictions on Formula Size.

[BibT_eX]

[DOI]

Russell Impagliazzo

Random Struct. Algorithms, 1993

Probabilistic Analysis of Network Flow Algorithms.

[BibT_eX]

[DOI]

Richard M. Karp

Rajeev Motwani

Math. Oper. Res., 1993

Constant Depth Circuits, Fourier Transform, and Learnability.

[BibT_eX]

[DOI]

Nathan Linial

J. ACM, 1993

BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs.

[BibT_eX]

[DOI]

Comput. Complex., 1993

More deterministic simulation in logspace.

[BibT_eX]

[DOI]

David Zuckerman

Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

A parallel approximation algorithm for positive linear programming.

[BibT_eX]

[DOI]

Michael Luby

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.

[BibT_eX]

[DOI]

László Babai

Mario Szegedy

J. Comput. Syst. Sci., 1992

Algebraic Methods for Interactive Proof Systems.

[BibT_eX]

[DOI]

J. ACM, 1992

Pseudorandom generators for space-bounded computation.

[BibT_eX]

[DOI]

Comb., 1992

Approximations of General Independent Distributions

[BibT_eX]

[DOI]

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

Undirected Connectivity in O(log ^1.5 n) Space

[BibT_eX]

[DOI]

Endre Szemerédi

Proceedings of the 33rd Annual Symposium on Foundations of Computer Science, 1992

Using hard problems to create pseudorandom generators.

[BibT_eX]

ACM Distinguished Dissertations, MIT Press, ISBN: 978-0-262-14051-5, 1992

1991

CREW PRAMs and Decision Trees.

[BibT_eX]

[DOI]

SIAM J. Comput., 1991

Pseudorandom bits for constant depth circuits.

[BibT_eX]

[DOI]

Comb., 1991

Lower Bounds for Non-Commutative Computation (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

BPP has Subexponential Time Simulation unless EXPTIME has Pubishable Proofs.

[BibT_eX]

[DOI]

László Babai

Proceedings of the Sixth Annual Structure in Complexity Theory Conference, Chicago, Illinois, USA, June 30, 1991

1990

Approximate inclusion-exclusion.

[BibT_eX]

[DOI]

Nathan Linial

Comb., 1990

Psuedorandom Generators for Space-Bounded Computation

[BibT_eX]

[DOI]

Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990

Lower Bounds on Random-Self-Reducibility.

[BibT_eX]

[DOI]

Joan Feigenbaum

Sampath Kannan

Proceedings of the Proceedings: Fifth Annual Structure in Complexity Theory Conference, 1990

1989

Parallel Algorithms for Zero-One Supply-Demand Problems.

[BibT_eX]

[DOI]

Danny Soroker

SIAM J. Discret. Math., 1989

Multiparty Protocols and Logspace-hard Pseudorandom Sequences (Extended Abstract)

[BibT_eX]

[DOI]

László Babai

Mario Szegedy

Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

Hardness vs. Randomness - A Survey (abstract).

[BibT_eX]

[DOI]

Proceedings of the Proceedings: Fourth Annual Structure in Complexity Theory Conference, 1989

1988

Hardness vs. Randomness (Extended Abstract)

[BibT_eX]

[DOI]