On the Communication Complexity of Approximate Fixed Points

No abstract is available for this paper.

• Publication year

  2016

• Venue

  IEEE Annual Symposium on Foundations of Computer Science

• Publication date

  2016-10-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/FOCS.2016.32
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Communication Complexity

  2016cited by this paper
• Settling the Complexity of Computing Approximate Two-Player Nash Equilibria

  2016cited by this paper
• Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games

  2015cited by this paper
• Deterministic Communication vs. Partition Number

  2015cited by this paper
• Distributed Methods for Computing Approximate Equilibria

  2015cited by this paper
• THE FEDERMANN CENTER FOR THE STUDY OF RATIONALITY

  2015cited by this paper
• Rectangles Are Nonnegative Juntas

  2015cited by this paper
• Separations in query complexity based on pointer functions

  2015cited by this paper
• Lower Bounds for Clique vs. Independent Set

  2015cited by this paper
• Simple approximate equilibria in large games

  2014cited by this paper
• Communication lower bounds via critical block sensitivity

  2013cited by this paper
• Query complexity of approximate nash equilibria

  2013cited by this paper
• On the communication complexity of approximate Nash equilibria

  2012cited by this paper
• How long to equilibrium? The communication complexity of uncoupled equilibrium procedures

  2010cited by this paper
• Using the Borsuk-Ulam Theorem: Lectures on Topological Methods in Combinatorics and Geometry

  2007cited by this paper
• Settling the complexity of computing two-player Nash equilibria

  2007cited by this paper
• On the complexity of 2D discrete fixed point problem

  2006cited by this paper
• The complexity of computing a Nash equilibrium

  2006cited by this paper
• A TOUR OF THE THEORY OF ABSOLUTELY MINIMIZING FUNCTIONS

  2004cited by this paper
• Communication complexity as a lower bound for learning in games

  2004cited by this paper
• Uncoupled Dynamics Do Not Lead to Nash Equilibrium

  2003cited by this paper
• Playing large games using simple strategies

  2003cited by this paper
• Complexity measures and decision tree complexity: a survey

  2002cited by this paper
• Uncoupled Dynamics Cannot Lead to Nash Equilibrium ∗

  2002cited by this paper
• Separation of the Monotone NC Hierarchy

  1997cited by this paper
• On equilibrium points in bimatrix games

  1996cited by this paper
• On rank vs. communication complexity

  1994cited by this paper
• On the Complexity of the Parity Argument and Other Inefficient Proofs of Existence

  1994cited by this paper
• Search problems in the decision tree model

  1991cited by this paper
• Exponential lower bounds for finding Brouwer fixed points

  1987cited by this paper
• Some topics in two-person games

  1971cited by this paper
• The Approximation of Fixed Points of a Continuous Mapping

  1967cited by this paper
• Analytic Extensions of Differentiable Functions Defined in Closed Sets

  1934cited by this paper

• Fast Swap Regret Minimization and Applications to Approximate Correlated Equilibria

  2023cites this paper
• Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games

  2023cites this paper
• Envy-Free Cake-Cutting for Four Agents

  2023cites this paper
• Quantum Communication Complexity of Classical Auctions

  2023cites this paper
• The randomized communication complexity of randomized auctions

  2021cites this paper
• A ZPPNP[1] Lifting Theorem

  2020cites this paper
• Settling the complexity of Nash equilibrium in congestion games

  2020cites this paper
• Informational bounds on equilibria (a survey)

  2020cites this paper
• Complexity Theory, Game Theory, and Economics: The Barbados Lectures

  2020cites this paper
• On Communication Complexity of Fixed Point Computation

  2019influential citation
• Settling the Communication Complexity of Combinatorial Auctions with Two Subadditive Buyers

  2019cites this paper
• Hardness of Approximation Between P and NP

  2019cites this paper
• Adventures in Monotone Complexity and TFNP

  2018cites this paper
• Near-Optimal Communication Lower Bounds for Approximate Nash Equilibria

  2018influential citation
• Complexity Theory, Game Theory, and Economics

  2018influential citation
• A ZPP NP [1] Lifting Theorem

  2017cites this paper
• Ham Sandwich is Equivalent to Borsuk-Ulam

  2017cites this paper
• Communication Complexity of Cake Cutting

  2017cites this paper
• Communication Complexity of Correlated Equilibrium in Two-Player Games

  2017cites this paper
• Communication complexity of approximate Nash equilibria

  2016cites this paper
• Deterministic Communication vs. Partition Number

  2015cites this paper
• Well-Supported vs. Approximate Nash Equilibria: Query Complexity of Large Games

  2015cites this paper