Buchumschlag

The Randomized Query Complexity of Finding a Tarski Fixed Point on the Boolean Hypercube

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Brânzei, Simina, Phillips, Reed, Recker, Nicholas
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity Computer Science and Game Theory
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Tarski Lower Bounds from Multi-Dimensional Herringbones
von: Brânzei, Simina, et al.
Veröffentlicht: (2025)

Dueling over Multiple Pieces of Dessert
von: Brânzei, Simina, et al.
Veröffentlicht: (2026)

Computing Envy-Free up to Any Good (EFX) Allocations via Local Search
von: Brânzei, Simina
Veröffentlicht: (2025)

Tit-for-Tat Dynamics and Market Volatility
von: Brânzei, Simina
Veröffentlicht: (2019)

Spectral Lower Bounds for Local Search
von: Brânzei, Simina, et al.
Veröffentlicht: (2024)

A note on quantum lower bounds for local search via congestion and expansion
von: Brânzei, Simina, et al.
Veröffentlicht: (2024)

The Quantum Query Complexity of Finding a Tarski Fixed Point on the 2D Grid
von: Phillips, Reed
Veröffentlicht: (2026)

Computing a Fixed Point of Contraction Maps in Polynomial Queries
von: Chen, Xi, et al.
Veröffentlicht: (2024)

Multiplayer Bandit Learning, from Competition to Cooperation
von: Brânzei, Simina, et al.
Veröffentlicht: (2019)

Complexity of Round-Robin Allocation with Potentially Noisy Queries
von: Li, Zihan, et al.
Veröffentlicht: (2024)

Dueling Over Dessert, Mastering the Art of Repeated Cake Cutting
von: Brânzei, Simina, et al.
Veröffentlicht: (2024)

The Query Complexity of Local Search and Brouwer in Rounds
von: Brânzei, Simina, et al.
Veröffentlicht: (2020)

Persuading a Credible Agent
von: Gan, Jiarui, et al.
Veröffentlicht: (2024)

The Computational Complexity of the Housing Market
von: Lock, Edwin, et al.
Veröffentlicht: (2024)

On the Complexity of Learning Nash Equilibria
von: Biggar, Oliver, et al.
Veröffentlicht: (2026)

On the Smoothed Complexity of Combinatorial Local Search
von: Giannakopoulos, Yiannis, et al.
Veröffentlicht: (2022)

The Complexity of Symmetric Bimatrix Games with Common Payoffs
von: Ghosh, Abheek, et al.
Veröffentlicht: (2024)

The Complexity of Min-Max Optimization with Product Constraints
von: Bernasconi, Martino, et al.
Veröffentlicht: (2026)

Modelling Network Resilience: The Complexity of Some Graph Division Games
von: Gutowski, Grzegorz, et al.
Veröffentlicht: (2026)

Complexity of Manipulation and Bribery in Premise-Based Judgment Aggregation with Simple Formulas
von: Bredereck, Robert, et al.
Veröffentlicht: (2024)

Ex-post Stability under Two-Sided Matching: Complexity and Characterization
von: Aziz, Haris, et al.
Veröffentlicht: (2024)

On the Complexity of Stationary Nash Equilibria in Discounted Perfect Information Stochastic Games
von: Hansen, Kristoffer Arnsfelt, et al.
Veröffentlicht: (2025)

A Computational Analysis of Strategic Nominations: Modeling Equilibrium and Complexity in Organizational Elections
von: Lin, Chuang-Chieh, et al.
Veröffentlicht: (2023)

The Complexity of Symmetric Equilibria in Min-Max Optimization and Team Zero-Sum Games
von: Anagnostides, Ioannis, et al.
Veröffentlicht: (2025)

Phase Transitions of Diversity in Stochastic Block Model Dynamics
von: Brânzei, Simina, et al.
Veröffentlicht: (2023)

Envy-Free House Allocation with Minimum Subsidy
von: Choo, Davin, et al.
Veröffentlicht: (2024)

The Query Complexity of Local Search in Rounds on General Graphs
von: Brânzei, Simina, et al.
Veröffentlicht: (2026)

Learning and Collusion in Multi-unit Auctions
von: Brânzei, Simina, et al.
Veröffentlicht: (2023)

Reducing the complexity of computing the values of a Nash equilibrium
von: Chatterjee, Debtoru, et al.
Veröffentlicht: (2025)

Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
von: Deligkas, Argyrios, et al.
Veröffentlicht: (2026)

Complexity of Stability in Trading Networks
von: Fleiner, Tamás, et al.
Veröffentlicht: (2018)

The Complexity of Optimizing Atomic Congestion
von: Brand, Cornelius, et al.
Veröffentlicht: (2023)

Structural Complexities of Matching Mechanisms
von: Gonczarowski, Yannai A., et al.
Veröffentlicht: (2022)

Computing Tarski Fixed Points in Financial Networks
von: Besting, Leander, et al.
Veröffentlicht: (2026)

Computational Social Choice: Parameterized Complexity and Challenges
von: Chen, Jiehua, et al.
Veröffentlicht: (2024)

The Complexity of Sparse Win-Lose Bimatrix Games
von: Batziou, Eleni, et al.
Veröffentlicht: (2026)

Smoothed analysis of deterministic discounted and mean-payoff games
von: Loff, Bruno, et al.
Veröffentlicht: (2024)

Disrupting Bipartite Trading Networks: Matching for Revenue Maximization
von: D'Amico-Wong, Luca, et al.
Veröffentlicht: (2024)

Controlling Borda Elections by Adding or Deleting either Votes or Candidates: Complete and Top-Truncated Votes
von: Zhou, Aizhong, et al.
Veröffentlicht: (2024)

Hardness of Approximate Sperner and Applications to Envy-Free Cake Cutting
von: Gao, Ruiquan, et al.
Veröffentlicht: (2024)