Cover Image

Fixed Point Computation: Beating Brute Force with Smoothed Analysis

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Attias, Idan, Dagan, Yuval, Daskalakis, Constantinos, Yao, Rui, Zampetakis, Manolis
Format:	Preprint
Published:	2025
Subjects:	Computer Science and Game Theory Data Structures and Algorithms Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Smooth Nash Equilibria: Algorithms and Complexity
by: Daskalakis, Constantinos, et al.
Published: (2023)

Computing Tarski Fixed Points in Financial Networks
by: Besting, Leander, et al.
Published: (2026)

Smoothed Analysis of Learning from Positive Samples
by: Lee, Jane H., et al.
Published: (2025)

Computing a Fixed Point of Contraction Maps in Polynomial Queries
by: Chen, Xi, et al.
Published: (2024)

Edge-weighted Online Stochastic Matching: Beating $1-\frac1e$
by: Yan, Shuyi
Published: (2022)

How Hard Is It to Rig a Tournament When Few Players Can Beat or Be Beaten by the Favorite?
by: Wang, Zhonghao, et al.
Published: (2026)

Repeated Bilateral Trade Against a Smoothed Adversary
by: Cesa-Bianchi, Nicolò, et al.
Published: (2023)

More Efforts Towards Fixed-Parameter Approximability of Multiwinner Rules
by: Gupta, Sushmita, et al.
Published: (2025)

Fair Repetitive Interval Scheduling
by: Heeger, Klaus, et al.
Published: (2024)

Breaking the $T^{2/3}$ Barrier for Sequential Calibration
by: Dagan, Yuval, et al.
Published: (2024)

Computing Power Indices in Weighted Majority Games with Formal Power Series
by: Kakimura, Naonori, et al.
Published: (2025)

The Geometry of Coalition Power: Majorization, Lattices, and Displacement in Multiwinner Elections
by: Guo, Qian, et al.
Published: (2026)

Computing Approximately Proportional Allocations of Indivisible Goods: Beyond Additive and Monotone Valuations
by: Andersen, Martin Jupakkal, et al.
Published: (2025)

Computing Optimal Regularizers for Online Linear Optimization
by: Gatmiry, Khashayar, et al.
Published: (2024)

Maximizing utility in multi-agent environments by anticipating the behavior of other learners
by: Assos, Angelos, et al.
Published: (2024)

Revisiting Ranking for Online Bipartite Matching with Random Arrivals: the Primal-Dual Analysis
by: Peng, Bo, et al.
Published: (2025)

A Smoothed FPTAS for Equilibria in Congestion Games
by: Giannakopoulos, Yiannis
Published: (2023)

Transfer Learning Beyond Bounded Density Ratios
by: Kalavasis, Alkis, et al.
Published: (2024)

Optimal Approximation -- Smoothness Tradeoffs for Soft-Max Functions
by: Epasto, Alessandro, et al.
Published: (2020)

High dimensional online calibration in polynomial time
by: Peng, Binghui
Published: (2025)

Improved Regret and Contextual Linear Extension for Pandora's Box and Prophet Inequality
by: Liu, Junyan, et al.
Published: (2025)

Repeated Contracting with Multiple Non-Myopic Agents: Policy Regret and Limited Liability
by: Collina, Natalie, et al.
Published: (2024)

Online Bidding Algorithms with Strict Return on Spend (ROS) Constraint
by: Vaze, Rahul, et al.
Published: (2025)

High-Dimensional Calibration from Swap Regret
by: Fishelson, Maxwell, et al.
Published: (2025)

On the Learning Curves of Revenue Maximization
by: Hanneke, Steve, et al.
Published: (2026)

An $α$-regret analysis of Adversarial Bilateral Trade
by: Azar, Yossi, et al.
Published: (2022)

Bandit Sequential Posted Pricing via Half-Concavity
by: Singla, Sahil, et al.
Published: (2023)

Strategizing against No-Regret Learners in First-Price Auctions
by: Rubinstein, Aviad, et al.
Published: (2024)

The Role of Transparency in Repeated First-Price Auctions with Unknown Valuations
by: Cesa-Bianchi, Nicolò, et al.
Published: (2023)

Simultaneous Swap Regret Minimization via KL-Calibration
by: Luo, Haipeng, et al.
Published: (2025)

Collaborative Prediction: Tractable Information Aggregation via Agreement
by: Collina, Natalie, et al.
Published: (2025)

Learning Safe Strategies for Value Maximizing Buyers in Uniform Price Auctions
by: Golrezaei, Negin, et al.
Published: (2024)

Contextual Learning for Stochastic Optimization
by: Heuser, Anna, et al.
Published: (2025)

Bandit Social Learning: Exploration under Myopic Behavior
by: Banihashem, Kiarash, et al.
Published: (2023)

Water-Filling is Universally Minimax Optimal
by: Banerjee, Siddhartha, et al.
Published: (2026)

Incentivizing Exploration with Selective Data Disclosure
by: Immorlica, Nicole, et al.
Published: (2018)

Learning Optimal Posted Prices for a Unit-Demand Buyer
by: Teng, Yifeng, et al.
Published: (2025)

Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning
by: Podimata, Chara, et al.
Published: (2020)

Procurement Auctions via Approximately Optimal Submodular Optimization
by: Deng, Yuan, et al.
Published: (2024)

Learning in Stackelberg Games with Non-myopic Agents
by: Haghtalab, Nika, et al.
Published: (2022)