Cover Image

Downward self-reducibility in the total function polynomial hierarchy

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gajulapalli, Karthik, Ghentiyala, Surendra, Li, Zeyong, Saraogi, Sidhant
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Online Orthogonal Vectors Revisited
by: Gajulapalli, Karthik, et al.
Published: (2026)

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

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

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

On Equivalence of Parameterized Inapproximability of k-Median, k-Max-Coverage, and 2-CSP
by: S., Karthik C., et al.
Published: (2024)

Revisiting Tree Canonization using polynomials
by: Arvind, V., et al.
Published: (2024)

Testing noisy low-degree polynomials for sparsity
by: Bao, Yiqiao, et al.
Published: (2025)

Hierarchies within TFNP: building blocks and collapses
by: Ghentiyala, Surendra, et al.
Published: (2025)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
by: S., Karthik C., et al.
Published: (2023)

Solution independence and self-referential instances
by: Zhou, Guangyan, et al.
Published: (2026)

A tight quasi-polynomial bound for Global Label Min-Cut
by: Jaffke, Lars, et al.
Published: (2022)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
by: Guruswami, Venkatesan, et al.
Published: (2023)

Constant congestion linkages in polynomially strong digraphs in polynomial time
by: Lopes, Raul, et al.
Published: (2024)

Resilient functions: Optimized, simplified, and generalized
by: Ivanov, Peter, et al.
Published: (2024)

On connections between k-coloring and Euclidean k-means
by: Aman, Enver, et al.
Published: (2024)

More basis reduction for linear codes: backward reduction, BKZ, slide reduction, and more
by: Ghentiyala, Surendra, et al.
Published: (2024)

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
by: Scheder, Dominik, et al.
Published: (2025)

On Approximability of Steiner Tree in $\ell_p$-metrics
by: Fleischmann, Henry, et al.
Published: (2023)

Hardness of Median and Center in the Ulam Metric
by: Fischer, Nick, et al.
Published: (2025)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

Inapproximability of Maximum Diameter Clustering for Few Clusters
by: Fleischmann, Henry, et al.
Published: (2023)

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

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

Asymptotic Rank Speedup Theorems, Revisited
by: Alman, Josh, et al.
Published: (2026)

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

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

Quadratic Speedup for Computing Contraction Fixed Points
by: Chen, Xi, et al.
Published: (2026)

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

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

Detecting Low-Degree Truncation
by: De, Anindya, et al.
Published: (2024)

A note on polynomial-time tolerant testing stabilizer states
by: Arunachalam, Srinivasan, et al.
Published: (2024)

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

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

Fine-Grained Complexity of Continuous Euclidean k-Center
by: Blank, Lotte, et al.
Published: (2026)

A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization
by: Umans, Chris, et al.
Published: (2025)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2025)

The Trichotomy of Regular Property Testing
by: Bathie, Gabriel, et al.
Published: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
by: Fujie, Yuto, et al.
Published: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
by: Moroie, Gregory
Published: (2025)