Cover Image

On Pigeonhole Principles and Ramsey in TFNP

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Jain, Siddhartha, Li, Jiawei, Robere, Robert, Xun, Zhiyang
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Separations in Proof Complexity and TFNP
by: Göös, Mika, et al.
Published: (2022)

Quantum Communication Advantage in TFNP
by: Göös, Mika, et al.
Published: (2024)

A Quantum Pigeonhole Principle and Two Semidefinite Relaxations of Communication Complexity
by: Dvořák, Pavel, et al.
Published: (2024)

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

Lower Bounds for Bit Pigeonhole Principles in Bounded-Depth Resolution over Parities
by: Byramji, Farzan, et al.
Published: (2025)

Lower Bounds for Approximate Sign Rank
by: Bindua, Riju, et al.
Published: (2026)

Separations above TFNP from Sherali-Adams Lower Bounds
by: Fleming, Noah, et al.
Published: (2026)

How to fit large complexity classes into TFNP
by: Thapen, Neil
Published: (2024)

KRW Composition Theorems via Lifting
by: de Rezende, Susanna F., et al.
Published: (2020)

An unholy trinity: TFNP, polynomial systems, and the quantum satisfiability problem
by: Aldi, Marco, et al.
Published: (2024)

Total Search Problems in $\mathsf{ZPP}$
by: Fleming, Noah, et al.
Published: (2025)

Near-Optimal Averaging Samplers and Matrix Samplers
by: Xun, Zhiyang, et al.
Published: (2024)

Efficient quantum circuits for high-dimensional representations of SU(n) and Ramanujan quantum expanders
by: Iyer, Vishnu, et al.
Published: (2026)

The Rank-Ramsey Problem and the Log-Rank Conjecture
by: Beniamini, Gal, et al.
Published: (2024)

Efficient Quantum Hermite Transform
by: Jain, Siddhartha, et al.
Published: (2025)

Consumable Data via Quantum Communication
by: Gilboa, Dar, et al.
Published: (2024)

Reinforced Generation of Combinatorial Structures: Ramsey Numbers
by: Nagda, Ansh, et al.
Published: (2026)

On the Rational Degree of Boolean Functions and Applications
by: Iyer, Vishnu, et al.
Published: (2023)

An Invariance Principle for the Multi-slice, with Applications
by: Braverman, Mark, et al.
Published: (2021)

Finding Bugs in Short Proofs: The Metamathematics of Resolution Lower Bounds
by: Li, Jiawei, et al.
Published: (2024)

Exponential Resolution Lower Bounds for Weak Pigeonhole Principle and Perfect Matching Formulas over Sparse Graphs
by: de Rezende, Susanna F., et al.
Published: (2019)

Lossy Catalytic Computation
by: Gupta, Chetan, et al.
Published: (2024)

Pseudo-deterministic Quantum Algorithms
by: Aaronson, Hugo, et al.
Published: (2026)

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

Quantum information advantage based on Bell inequalities
by: Jain, Rahul, et al.
Published: (2026)

How to Resolve Envy by Adding Goods
by: Bentert, Matthias, et al.
Published: (2025)

Algebraic Pseudorandomness in $VNC^0$
by: Andrews, Robert
Published: (2025)

On Matrix Multiplication and Polynomial Identity Testing
by: Andrews, Robert
Published: (2022)

Bribery's Influence on Ranked Aggregation
by: Jain, Pallavi, et al.
Published: (2026)

An Improved Construction of Variety-Evasive Subspace Families
by: Andrews, Robert, et al.
Published: (2026)

Polynomial-Time PIT from (Almost) Necessary Assumptions
by: Andrews, Robert, et al.
Published: (2025)

VC-Dimension vs Degree: An Uncertainty Principle for Boolean Functions
by: Chang, Fan, et al.
Published: (2025)

Experimental relativistic zero-knowledge proofs with unconditional security
by: Weng, Chen-Xun, et al.
Published: (2025)

A Parameterized-Complexity Framework for Finding Local Optima
by: Ganian, Robert, et al.
Published: (2026)

Constant-Depth Arithmetic Circuits for Linear Algebra Problems
by: Andrews, Robert, et al.
Published: (2024)

Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform
by: Li, Zeyong
Published: (2023)

Algorithmics and Complexity of Cost-Driven Task Offloading with Submodular Optimization in Edge-Cloud Environments
by: Guo, Longkun, et al.
Published: (2024)

Modular composition & polynomial GCD in the border of small, shallow circuits
by: Andrews, Robert, et al.
Published: (2025)

Hilbert's Nullstellensatz is in the Counting Hierarchy
by: Andrews, Robert, et al.
Published: (2026)

The PCP-like Theorem for Sub-linear Time Inapproximability
by: Ma, Hengzhao, et al.
Published: (2021)