Copertina

Monotone Contractions

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Batziou, Eleni, Fearnley, John, Gordon, Spencer, Mehta, Ruta, Savani, Rahul
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

The Complexity of Sparse Win-Lose Bimatrix Games
di: Batziou, Eleni, et al.
Pubblicazione: (2026)

Super Unique Tarski is in UEOPL
di: Fearnley, John, et al.
Pubblicazione: (2024)

Two Choices are Enough for P-LCPs, USOs, and Colorful Tangents
di: Borzechowski, Michaela, et al.
Pubblicazione: (2024)

The Complexity of Computing KKT Solutions of Quadratic Programs
di: Fearnley, John, et al.
Pubblicazione: (2023)

Constant Inapproximability for Fisher Markets
di: Deligkas, Argyrios, et al.
Pubblicazione: (2026)

Constant Inapproximability for PPA
di: Deligkas, Argyrios, et al.
Pubblicazione: (2022)

Fisher Markets with Approximately Optimal Bundles and the Need for a PCP Theorem for PPAD
di: Deligkas, Argyrios, et al.
Pubblicazione: (2026)

Pure-Circuit: Tight Inapproximability for PPAD
di: Deligkas, Argyrios, et al.
Pubblicazione: (2022)

Pizza Sharing is PPA-hard
di: Deligkas, Argyrios, et al.
Pubblicazione: (2020)

Monotone Circuit Complexity of Matching
di: Cavalar, Bruno, et al.
Pubblicazione: (2025)

Logical Expressibility of Syntactic NL for Complementarity, Monotonicity, and Maximization
di: Yamakami, Tomoyuki
Pubblicazione: (2024)

Monotone Bounded Depth Formula Complexity of Graph Homomorphism Polynomials
di: Komarath, Balagopal, et al.
Pubblicazione: (2025)

Optimal Monotone Depth-Three Circuit Lower Bounds for Majority
di: Gurumukhani, Mohit, et al.
Pubblicazione: (2026)

Conditional Complexity Hardness: Monotone Circuit Size, Matrix Rigidity, and Tensor Rank
di: Chukhin, Nikolai, et al.
Pubblicazione: (2024)

The Complexity of Contracting Bipartite Graphs into Small Cycles
di: Krithika, R., et al.
Pubblicazione: (2022)

A Distance Amplification Lemma for Monotonicity
di: Minzer, Dor
Pubblicazione: (2025)

Graph Homomorphism, Monotone Classes and Bounded Pathwidth
di: Eagling-Vose, Tala, et al.
Pubblicazione: (2024)

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
di: Bhargav, C. S., et al.
Pubblicazione: (2025)

Causal Discovery under Latent Class Confounding
di: Mazaheri, Bijan, et al.
Pubblicazione: (2023)

Query-Efficient Fixpoints of $\ell_p$-Contractions
di: Haslebacher, Sebastian, et al.
Pubblicazione: (2025)

On the power of counting the total number of computation paths of NPTMs
di: Bakali, Eleni, et al.
Pubblicazione: (2023)

A Critique of Quigley's "A Polynomial Time Algorithm for 3SAT"
di: DeJesse, Nicholas, et al.
Pubblicazione: (2025)

Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler-Leman
di: de Rezende, Susanna F., et al.
Pubblicazione: (2024)

Communication Complexity is NP-hard
di: Hirahara, Shuichi, et al.
Pubblicazione: (2025)

AC^0[p]-Frege Cannot Efficiently Prove that Constant-Depth Algebraic Circuit Lower Bounds are Hard
di: Lu, Jiaqi, et al.
Pubblicazione: (2025)

A Critique of Lin's "On $\text{NP}$ versus $\text{coNP}$ and Frege Systems"
di: DeJesse, Nicholas, et al.
Pubblicazione: (2025)

Lines in Every Direction with No ee-Random Points
di: Lutz, Neil, et al.
Pubblicazione: (2025)

From Proof Complexity to Circuit Complexity via Interactive Protocols
di: Arteche, Noel, et al.
Pubblicazione: (2024)

Constructive Separations and Their Consequences
di: Chen, Lijie, et al.
Pubblicazione: (2022)

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

Lossy Catalytic Computation
di: Gupta, Chetan, et al.
Pubblicazione: (2024)

Faster Exponential-Time Approximation Algorithms Using Approximate Monotone Local Search
di: Esmer, Barış Can, et al.
Pubblicazione: (2022)

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

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

Computational complexity of isometric tensor network states
di: Malz, Daniel, et al.
Pubblicazione: (2024)

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

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

New Approaches to Complexity via Quantum Graphs
di: Culf, Eric, et al.
Pubblicazione: (2023)

A Continuous-Time Perspective on Global Acceleration for Monotone Equation Problems
di: Lin, Tianyi, et al.
Pubblicazione: (2022)

Exponential-Size Circuit Complexity is Comeager in Symmetric Exponential Time
di: Hitchcock, John M.
Pubblicazione: (2026)