Imagen de Portada

Tolerant Testing for Unique Games

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Yoshida, Yuichi
Formato:	Preprint
Publicado:	2026
Materias:	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

Testing Monotonicity of Real-Valued Functions on DAGs
por: Yoshida, Yuichi
Publicado: (2026)

Lower Bounds for Testing Directed Acyclicity in the Unidirectional Bounded-Degree Model
por: Yoshida, Yuichi
Publicado: (2026)

Solving Hypergraph Laplacian Systems in Almost-Linear Time
por: Yoshida, Yuichi
Publicado: (2026)

Average sensitivity of the Knapsack Problem
por: Kumabe, Soh, et al.
Publicado: (2024)

Lipschitz Continuous Algorithms for Covering Problems
por: Kumabe, Soh, et al.
Publicado: (2023)

Lipschitz Continuous Allocations for Optimization Games
por: Kumabe, Soh, et al.
Publicado: (2024)

Non-Signaling Locality Lower Bounds for Dominating Set
por: Fleming, Noah, et al.
Publicado: (2026)

$O(\log n)$-Approximation Algorithms for Bipartiteness Ratio
por: Soma, Tasuku, et al.
Publicado: (2025)

Courcelle's Theorem for Lipschitz Continuity
por: Gima, Tatsuya, et al.
Publicado: (2025)

From Average Sensitivity to Small-Loss Regret Bounds under Random-Order Model
por: Sakaue, Shinsaku, et al.
Publicado: (2026)

Low-Sensitivity Matching via Sampling from Gibbs Distributions
por: Yoshida, Yuichi, et al.
Publicado: (2025)

Sensitivity Lower Bounds for Approximaiton Algorithms
por: Fleming, Noah, et al.
Publicado: (2024)

Pointwise Lipschitz Continuous Graph Algorithms
por: Liu, Quanquan C., et al.
Publicado: (2024)

Testing Spreading Behavior in Networks with Arbitrary Topologies
por: Modanese, Augusto, et al.
Publicado: (2023)

Optimal Non-Adaptive Tolerant Junta Testing via Local Estimators
por: Nadimpalli, Shivam, et al.
Publicado: (2024)

A Mysterious Connection Between Tolerant Junta Testing and Agnostically Learning Conjunctions
por: Chen, Xi, et al.
Publicado: (2025)

Faster Algorithms for Shortest Unique or Absent Substrings
por: Charalampopoulos, Panagiotis, et al.
Publicado: (2026)

Tolerant Testing of Stabilizer States with Mixed State Inputs
por: Iyer, Vishnu, et al.
Publicado: (2024)

A Tolerant Independent Set Tester
por: Seth, Cameron
Publicado: (2025)

Fault-Tolerant ST-Diameter Oracles
por: Bilò, Davide, et al.
Publicado: (2023)

Fault-Tolerant Bounded Flow Preservers
por: Bansal, Shivam, et al.
Publicado: (2024)

An Optimal $3$-Fault-Tolerant Connectivity Oracle
por: Kosinas, Evangelos
Publicado: (2025)

Sublinear Edge Fault Tolerant Spanners for Hypergraphs
por: He, Jialin, et al.
Publicado: (2025)

Nearly Optimal Fault Tolerant Distance Oracle
por: Dey, Dipan, et al.
Publicado: (2024)

Near Optimal Dual Fault Tolerant Distance Oracle
por: Dey, Dipan, et al.
Publicado: (2024)

Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks
por: Bilò, Davide, et al.
Publicado: (2024)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
por: Hoppenworth, Gary, et al.
Publicado: (2025)

Rapid Mixing at the Uniqueness Threshold
por: Chen, Xiaoyu, et al.
Publicado: (2024)

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
por: Parter, Merav, et al.
Publicado: (2024)

Approximations for Fault-Tolerant Total and Partial Positive Influence Domination
por: Lamprou, Ioannis, et al.
Publicado: (2025)

Fault-Tolerant Approximate Distance Oracles with a Source Set
por: Dey, Dipan, et al.
Publicado: (2025)

Near-Optimal Vertex Fault-Tolerant Labels for Steiner Connectivity
por: Bhanja, Koustav, et al.
Publicado: (2025)

Compressed Game Solving
por: Considine, Jeffrey
Publicado: (2024)

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
por: Khanna, Sanjeev, et al.
Publicado: (2026)

Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time
por: Parter, Merav, et al.
Publicado: (2025)

Maximum Unique Coverage on Streams: Improved FPT Approximation Scheme and Tighter Space Lower Bound
por: Cervenjak, Philip, et al.
Publicado: (2024)

Rapid Mixing on Random Regular Graphs beyond Uniqueness
por: Chen, Xiaoyu, et al.
Publicado: (2025)

An Objective Improvement Approach to Solving Discounted Payoff Games
por: Dell'Erba, Daniele, et al.
Publicado: (2024)

Testing Connectedness of Images
por: Berman, Piotr, et al.
Publicado: (2023)

Testing Suffixient Sets
por: Cenzato, Davide, et al.
Publicado: (2025)