Imagen de Portada

Quadratic Speedup for Computing Contraction Fixed Points

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Chen, Xi, Li, Yuhao, Yannakakis, Mihalis
Formato:	Preprint
Publicado:	2026
Materias:	Computational Complexity Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

The Mystery Deepens: On the Query Complexity of Tarski Fixed Points
por: Chen, Xi, et al.
Publicado: (2026)

Asymptotic Rank Speedup Theorems, Revisited
por: Alman, Josh, et al.
Publicado: (2026)

The Computational Complexity of Avoiding Strict Saddle Points in Constrained Optimization
por: Kontogiannis, Andreas, et al.
Publicado: (2026)

The Parameterized Landscape of Labeled Graph Contractions
por: Lafond, Manuel, et al.
Publicado: (2025)

Self-referential instances of the dominating set problem are irreducible
por: Zhou, Guangyan
Publicado: (2026)

An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians
por: Mataraarachchi, Ranitha, et al.
Publicado: (2026)

Finding Maximum Common Contractions Between Phylogenetic Networks
por: Marchand, Bertrand, et al.
Publicado: (2024)

Homogeneous Network Caching is Fixed-Parameter Tractable Parameterized by the Number of Caches
por: Pintér, József, et al.
Publicado: (2026)

DNF formulas are efficiently testable with relative error
por: Chen, Xi, et al.
Publicado: (2026)

Lower Bounds for Convexity Testing
por: Chen, Xi, et al.
Publicado: (2024)

Computational Complexity in Property Testing
por: Pinto Jr., Renato Ferreira, et al.
Publicado: (2025)

The Structure of In-Place Space-Bounded Computation
por: Cook, James, et al.
Publicado: (2025)

Computational Explorations of Total Variation Distance
por: Bhattacharyya, Arnab, et al.
Publicado: (2024)

Sublinear-query relative-error testing of halfspaces
por: Chen, Xi, et al.
Publicado: (2026)

Halfspaces are hard to test with relative error
por: Chen, Xi, et al.
Publicado: (2025)

Relative-error monotonicity testing
por: Chen, Xi, et al.
Publicado: (2024)

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $δ$-Covering All Points on All Edges
por: Frei, Fabian, et al.
Publicado: (2024)

Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
por: Krithika, R., et al.
Publicado: (2023)

Testing Sumsets is Hard
por: Chen, Xi, et al.
Publicado: (2024)

Computational Complexity of Swish
por: Horiyama, Takashi, et al.
Publicado: (2026)

Constructing self-referential instances for the clique problem
por: Li, Jiaqi, et al.
Publicado: (2026)

Kronecker Powers, Orthogonal Vectors, and the Asymptotic Spectrum
por: Alman, Josh, et al.
Publicado: (2025)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
por: Li, Qian, et al.
Publicado: (2025)

The Query Complexity of Local Search and Brouwer in Rounds
por: Brânzei, Simina, et al.
Publicado: (2020)

On the Complexity of Minimizing Energy Consumption of Partitioning DAG Tasks
por: Liu, Wei, et al.
Publicado: (2024)

Downward self-reducibility in the total function polynomial hierarchy
por: Gajulapalli, Karthik, et al.
Publicado: (2025)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
por: Focke, Jacob, et al.
Publicado: (2023)

Faster Convolutions: Yates and Strassen Revisited
por: Brand, Cornelius, et al.
Publicado: (2025)

Computing the $D$-base and $D$-relation in finite closure systems
por: Adaricheva, Kira, et al.
Publicado: (2024)

Detecting Low-Degree Truncation
por: De, Anindya, et al.
Publicado: (2024)

Computational Complexities of Folding
por: Eppstein, David
Publicado: (2024)

The Fine-Grained Complexity of Episode Matching
por: Bille, Philip, et al.
Publicado: (2021)

A New Information Complexity Measure for Multi-pass Streaming with Applications
por: Braverman, Mark, et al.
Publicado: (2024)

Beyond Bits: An Introduction to Computation over the Reals
por: Miltzow, Tillmann
Publicado: (2026)

Boolean function monotonicity testing requires (almost) $n^{1/2}$ queries
por: Chen, Mark, et al.
Publicado: (2025)

Computational-Statistical Tradeoffs from NP-hardness
por: Blanc, Guy, et al.
Publicado: (2025)

A Fixed-Parameter Algorithm for the Kneser Problem
por: Haviv, Ishay
Publicado: (2022)

Relative-error testing of conjunctions and decision lists
por: Chen, Xi, et al.
Publicado: (2025)

Testing Juntas and Junta Subclasses with Relative Error
por: Chen, Xi, et al.
Publicado: (2025)