Peter Bro Miltersen

Troels Bjerre Lund

ACM Trans. Economics and Comput., 2017

2016

Special Section on the Forty-Fifth Annual ACM Symposium on the Theory of Computing (STOC 2013).

[BibT_eX]

[DOI]

James Aspnes

Yuval Ishai

SIAM J. Comput., 2016

Envy-Free Pricing in Multi-unit Markets.

[BibT_eX]

[DOI]

CoRR, 2016

2015

Characterization and Computation of Equilibria for Indivisible Goods.

[BibT_eX]

[DOI]

Hadi Hosseini

Proceedings of the Algorithmic Game Theory - 8th International Symposium, 2015

A Dictatorship Theorem for Cake Cutting.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

2014

The Complexity of Solving Reachability Games Using Value and Strategy Iteration.

[BibT_eX]

[DOI]

Rasmus Ibsen-Jensen

Theory Comput. Syst., 2014

Truthful Approximations to Range Voting.

[BibT_eX]

[DOI]

Aris Filos-Ratsikas

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

Semi-algebraic geometry in computational game theory - a consumer's perspective (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), 2014

The Complexity of Approximating a Trembling Hand Perfect Equilibrium of a Multi-player Game in Strategic Form.

[BibT_eX]

[DOI]

Kousha Etessami

Proceedings of the Algorithmic Game Theory - 7th International Symposium, 2014

2013

Strategy Iteration Is Strongly Polynomial for 2-Player Turn-Based Stochastic Games with a Constant Discount Factor.

[BibT_eX]

[DOI]

Søren Kristoffer Stiil Frederiksen

Uri Zwick

J. ACM, 2013

Efficient Multiparty Protocols via Log-Depth Threshold Formulae.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Monomial Strategies for Concurrent Reachability Games and Other Stochastic Games.

[BibT_eX]

[DOI]

Søren Kristoffer Stiil Frederiksen

Proceedings of the Reachability Problems - 7th International Workshop, 2013

Approximating the Value of a Concurrent Reachability Game in the Polynomial Time Hierarchy.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Computation - 24th International Symposium, 2013

Efficient Multiparty Protocols via Log-Depth Threshold Formulae - (Extended Abstract).

[BibT_eX]

[DOI]

Proceedings of the Advances in Cryptology - CRYPTO 2013, 2013

A Faster Algorithm for Solving One-Clock Priced Timed Games.

[BibT_eX]

[DOI]

Rasmus Ibsen-Jensen

Proceedings of the CONCUR 2013 - Concurrency Theory - 24th International Conference, 2013

Equilibrium analysis in cake cutting.

[BibT_eX]

[DOI]

Proceedings of the International conference on Autonomous Agents and Multi-Agent Systems, 2013

2012

Deterministic Graphical Games Revisited.

[BibT_eX]

[DOI]

Daniel Andersson

J. Log. Comput., 2012

Secret Sharing and Secure Computing from Monotone Formulae.

[BibT_eX]

[DOI]

Ivan Bjerre Damgård

Jonas Kölker

IACR Cryptol. ePrint Arch., 2012

Equilibria of Chinese Auctions

[BibT_eX]

[DOI]

CoRR, 2012

Exact Algorithms for Solving Stochastic Games

[BibT_eX]

[DOI]

CoRR, 2012

Send mixed signals: earn more, work less.

[BibT_eX]

[DOI]

Or Sheffet

Proceedings of the 13th ACM Conference on Electronic Commerce, 2012

Recent Results on Howard's Algorithm.

[BibT_eX]

[DOI]

Proceedings of the Mathematical and Engineering Methods in Computer Science, 2012

Solving Simple Stochastic Games with Few Coin Toss Positions.

[BibT_eX]

[DOI]

Rasmus Ibsen-Jensen

Proceedings of the Algorithms - ESA 2012, 2012

2011

Exact algorithms for solving stochastic games: extended abstract.

[BibT_eX]

[DOI]

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010

The Computational Complexity of Trembling Hand Perfection and Other Equilibrium Refinements.

[BibT_eX]

[DOI]

Proceedings of the Algorithmic Game Theory - Third International Symposium, 2010

10171 Abstracts Collection - Equilibrium Computation.

[BibT_eX]

[DOI]

Proceedings of the Equilibrium Computation, 25.04. - 30.04.2010, 2010

2009

Winning Concurrent Reachability Games Requires Doubly-Exponential Patience.

[BibT_eX]

[DOI]

Michal Koucký

Proceedings of the 24th Annual IEEE Symposium on Logic in Computer Science, 2009

Hilbert's Thirteenth Problem and Circuit Complexity.

[BibT_eX]

[DOI]

Oded Lachish

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

The Complexity of Solving Stochastic Games on Graphs.

[BibT_eX]

[DOI]

Daniel Andersson

Proceedings of the Algorithms and Computation, 20th International Symposium, 2009

Privacy-Enhancing Auctions Using Rational Cryptography.

[BibT_eX]

[DOI]

Jesper Buus Nielsen

Nikos Triandopoulos

Proceedings of the Advances in Cryptology, 2009

Existence and computation of equilibria of first-price auctions with integral valuations and bids.

[BibT_eX]

[DOI]

Guillaume Escamocher

Rocio Santillan R.

Proceedings of the 8th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2009), 2009

2008

Privacy-Enhancing First-Price Auctions Using Rational Cryptography.

[BibT_eX]

[DOI]

Jesper Buus Nielsen

Nikos Triandopoulos

IACR Cryptol. ePrint Arch., 2008

Trembling hand perfection is NP-hard

[BibT_eX]

[DOI]

CoRR, 2008

On the computational complexity of solving stochastic mean-payoff games

[BibT_eX]

[DOI]

Vladimir Gurvich

CoRR, 2008

Special Issue: "Conference on Computational Complexity 2007" Guest Editor's Foreword.

[BibT_eX]

[DOI]

Comput. Complex., 2008

Approximability and Parameterized Complexity of Minmax Values.

[BibT_eX]

[DOI]

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

Fast algorithms for finding proper strategies in game trees.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

08381 Executive Summary - Computational Complexity of Discrete Problems.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity of Discrete Problems, 14.09. - 19.09.2008, 2008

08381 Abstracts Collection - Computational Complexity of Discrete Problems.

[BibT_eX]

[DOI]

Proceedings of the Computational Complexity of Discrete Problems, 14.09. - 19.09.2008, 2008

On Range of Skill.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, 2008

2007

The cell probe complexity of succinct data structures.

[BibT_eX]

[DOI]

Anna Gál

Theor. Comput. Sci., 2007

The Computational Complexity of One-Dimensional Sandpiles.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2007

Simple Recursive Games

[BibT_eX]

[DOI]

Daniel Andersson

CoRR, 2007

07471 Abstracts Collection - Equilibrium Computation.

[BibT_eX]

[DOI]

P. Jean-Jacques Herings

Proceedings of the Equilibrium Computation, 18.11. - 23.11.2007, 2007

Finding Equilibria in Games of No Chance.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

A near-optimal strategy for a heads-up no-limit Texas Hold'em poker tournament.

[BibT_eX]

[DOI]

Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS 2007), 2007

2006

Finding small OBDDs for incompletely specified truth tables is hard

[BibT_eX]

[DOI]

Jesper Torp Kristensen

Electron. Colloquium Comput. Complex., 2006

Circuits on cylinders.

[BibT_eX]

[DOI]

V. Vinay

Comput. Complex., 2006

Computing sequential equilibria for two-player games.

[BibT_eX]

[DOI]

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Computing Proper Equilibria of Zero-Sum Games.

[BibT_eX]

[DOI]

Proceedings of the Computers and Games, 5th International Conference, 2006

2005

On converting CNF to DNF.

[BibT_eX]

[DOI]

Jaikumar Radhakrishnan

Ingo Wegener

Theor. Comput. Sci., 2005

Reviewing bounds on the circuit size of the hardest functions.

[BibT_eX]

[DOI]

Johan Kjeldgaard-Pedersen

Inf. Process. Lett., 2005

On the Complexity of Numerical Analysis

[BibT_eX]

[DOI]

Eric Allender

Peter Bürgisser

Electron. Colloquium Comput. Complex., 2005

Derandomizing Arthur-Merlin Games using Hitting Sets.

[BibT_eX]

[DOI]

N. V. Vinodchandran

Comput. Complex., 2005

Lower bounds on the size of selection and rank indexes.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

2004

Some Meet-in-the-Middle Circuit Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 2004, 2004

2002

Are Bitvectors Optimal?

[BibT_eX]

[DOI]

Harry Buhrman

Jaikumar Radhakrishnan

Srinivasan Venkatesh

SIAM J. Comput., 2002

2001

Deterministic Dictionaries.

[BibT_eX]

[DOI]

Torben Hagerup

Rasmus Pagh

J. Algorithms, 2001

Lower Bounds for Dynamic Algebraic Problems.

[BibT_eX]

[DOI]

Johan P. Hansen

Inf. Comput., 2001

On Pseudorandom Generators in NC.

[BibT_eX]

[DOI]

Mary Cryan

Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

2000

On the Shannon Function for Partially Defined Boolean Functions.

[BibT_eX]

Proceedings of the ICALP Workshops 2000, 2000

New Bounds for the Language Compression Problem.

[BibT_eX]

[DOI]

Harry Buhrman

Sophie Laplante

Proceedings of the 15th Annual IEEE Conference on Computational Complexity, 2000

1999

Fusion Trees can be Implemented with AC0 Instructions Only.

[BibT_eX]

[DOI]

Arne Andersson

Mikkel Thorup

Theor. Comput. Sci., 1999

Guest Editors' Foreword.

[BibT_eX]

Jens Lagergren

Nord. J. Comput., 1999

Linear Hash Functions.

[BibT_eX]

[DOI]

Noga Alon

Martin Dietzfelbinger

Erez Petrank

Gábor Tardos

J. ACM, 1999

The Complexity of Identifying Large Equivalence Classes.

[BibT_eX]

[DOI]

Peter G. Binderup

Fundam. Informaticae, 1999

Super-Polynomial Versus Half-Exponential Circuit Size in the Exponential Hierarchy.

[BibT_eX]

[DOI]

N. V. Vinodchandran

Osamu Watanabe

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

On Monotone Planar Circuits.

[BibT_eX]

[DOI]

David A. Mix Barrington

Chi-Jen Lu

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

On Data Structures and Asymmetric Communication Complexity.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 1998

Error Correcting Codes, Perfect Hashing Circuits, and Deterministic Dynamic Dictionaries.

[BibT_eX]

[DOI]

Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

On showing lower bounds for external-memory computational geometry problems.

[BibT_eX]

[DOI]

Lars Arge

Proceedings of the External Memory Algorithms, 1998

1997

Dynamic word problems.

[BibT_eX]

[DOI]

J. ACM, 1997

Searching constant width mazes captures the AC0 hierarchy

[BibT_eX]

[DOI]

David A. Mix Barrington

Chi-Jen Lu

Electron. Colloquium Comput. Complex., 1997

Trans-Dichotomous Algorithms Without Multiplication - Some Upper and Lower Bounds.

[BibT_eX]

[DOI]

Andrej Brodnik

J. Ian Munro

Proceedings of the Algorithms and Data Structures, 5th International Workshop, 1997

Is Linear Hashing Good?

[BibT_eX]

[DOI]

Noga Alon

Martin Dietzfelbinger

Erez Petrank

Gábor Tardos

Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

1996

Relative to a Random Oracle, NP Is Not Small.

[BibT_eX]

[DOI]

Steven M. Kautz

J. Comput. Syst. Sci., 1996

The Asymptotic Complexity of Merging Networks.

[BibT_eX]

[DOI]

Mike Paterson

Jun Tarui

J. ACM, 1996

Lower Bounds for Static Dictionaries on RAMs with Bit Operations But No Multiplication.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 23rd International Colloquium, 1996

Static Dictionaries on AC0 RAMs: Query Time Theta(sqrt(log n/log log n)) is Necessary and Sufficient.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

On the Cell Probe Complexity of Polynomial Evaluation.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1995

Dynamic Algorithms for the Dyck Languages.

[BibT_eX]

[DOI]

Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

Tables Should Be Sorted (On Random Access Machines).

[BibT_eX]

[DOI]

Faith E. Fich

Proceedings of the Algorithms and Data Structures, 4th International Workshop, 1995

1994

Complexity Models for Incremental Computation.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1994

Lower bounds for union-split-find related problems on random access machines.

[BibT_eX]

[DOI]

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

1993

The Complexity of Malign Measures.

[BibT_eX]

[DOI]

SIAM J. Comput., 1993

The Bit Probe Complexity Measure Revisited.

[BibT_eX]

[DOI]

Proceedings of the STACS 93, 1993

The Complexity of Finding Replicas Using Equality Tests.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1993, 1993

1992

Circuit Depth Relative to a Random Oracle.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1992

1991

The Complexity of Malign Ensembles.

[BibT_eX]

[DOI]