Imagen de Portada

Undecidability of Polynomial Inequalities in Subset Densities and Additive Energies

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autor principal:	Li, Yaqiao
Formato:	Preprint
Publicado:	2025
Materias:	Combinatorics Computational Complexity Logic
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Separating complexity classes of LCL problems on grids
por: Berlow, Katalin, et al.
Publicado: (2025)

Restricted CSPs and F-free Digraph Algorithmics
por: Guzmán-Pro, Santiago, et al.
Publicado: (2025)

The Richness of CSP Non-redundancy
por: Brakensiek, Joshua, et al.
Publicado: (2025)

A Classification of Long-Refinement Graphs for Colour Refinement
por: Kiefer, Sandra, et al.
Publicado: (2025)

An Algorithmic Meta Theorem for Homomorphism Indistinguishability
por: Seppelt, Tim
Publicado: (2024)

Logical Equivalences, Homomorphism Indistinguishability, and Forbidden Minors
por: Seppelt, Tim
Publicado: (2023)

An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
por: Feller, Roman, et al.
Publicado: (2024)

Functional variant of Polynomial Analogue of Gandy's Fixed Point Theorem
por: Nechesov, Andrey
Publicado: (2024)

Polynomial Calculus sizes over the Boolean and Fourier bases are incomparable
por: Mouli, Sasank
Publicado: (2024)

Undecidability and incompleteness in quantum information theory and operator algebras
por: Goldbring, Isaac
Publicado: (2024)

A Subexponential Reduction from Product Partition to Subset Sum
por: Costandin, Marius
Publicado: (2024)

Lasserre Hierarchy for Graph Isomorphism and Homomorphism Indistinguishability
por: Roberson, David E., et al.
Publicado: (2023)

Undecidability of Translational Tiling with Three Tiles
por: Yang, Chan, et al.
Publicado: (2024)

Undecidability of tiling the plane with a fixed number of Wang bars
por: Yang, Chao, et al.
Publicado: (2024)

Undecidability of the elementary theory of Young--Fibonacci lattice
por: Evtushevsky, Vsevolod
Publicado: (2024)

A Schematic Definition of Quantum Polynomial Time Computability
por: Yamakami, Tomoyuki
Publicado: (2018)

Relating the Computational and Logical Difficulty of Solving ODEs: From Polynomial to Discontinuous Right-Hand Sides
por: Bournez, Olivier, et al.
Publicado: (2026)

Undecidability of Translational Tiling of the 4-dimensional Space with a Set of 4 Polyhypercubes
por: Yang, Chao, et al.
Publicado: (2024)

Undecidability of Translational Tiling of the 3-dimensional Space with a Set of 6 Polycubes
por: Yang, Chao, et al.
Publicado: (2024)

Finding hardness reductions automatically using SAT solvers
por: Bergold, Helena, et al.
Publicado: (2024)

Low-Degree Polynomials Are Good Extractors
por: Alrabiah, Omar, et al.
Publicado: (2024)

Provably Explaining Neural Additive Models
por: Bassan, Shahaf, et al.
Publicado: (2026)

The Cheeger Inequality and Coboundary Expansion: Beyond Constant Coefficients
por: First, Uriya A., et al.
Publicado: (2022)

Galois Energy Games: To Solve All Kinds of Quantitative Reachability Problems
por: Lemke, Caroline, et al.
Publicado: (2025)

The Proof Analysis Problem
por: Arteche, Noel, et al.
Publicado: (2025)

Effective Versions of Strong Measure Zero
por: Rayman, Matthew
Publicado: (2025)

Meta-Mathematics of Computational Complexity Theory
por: Oliveira, Igor C.
Publicado: (2025)

On the consistency of stronger lower bounds for NEXP
por: Thapen, Neil
Publicado: (2025)

Proof Complexity of Linear Logics
por: Tabatabai, Amirhossein Akbar, et al.
Publicado: (2026)

An order out of nowhere: a new algorithm for infinite-domain CSPs
por: Mottet, Antoine, et al.
Publicado: (2023)

Proof complexity of positive branching programs
por: Das, Anupam, et al.
Publicado: (2021)

Parallelism and Adaptivity in Student-Teacher Witnessing
por: Ježil, Ondřej, et al.
Publicado: (2026)

The complete classification for quantified equality constraints
por: Zhuk, Dmitriy, et al.
Publicado: (2021)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets
por: Atserias, Albert, et al.
Publicado: (2024)

$Π_{2}^{P}$ vs PSpace Dichotomy for the Quantified Constraint Satisfaction Problem
por: Zhuk, Dmitriy
Publicado: (2024)

Completeness in the Polynomial Hierarchy and PSPACE for many natural problems derived from NP
por: Grüne, Christoph, et al.
Publicado: (2026)

A Theory for Probabilistic Polynomial-Time Reasoning
por: Chen, Lijie, et al.
Publicado: (2026)

A Proposed Characterization of p-Simulation Between Theories
por: Monroe, Hunter
Publicado: (2025)

Feasibility of Primality in Bounded Arithmetic
por: Jalali, Raheleh, et al.
Publicado: (2025)

Proof complexity of Mal'tsev CSP
por: Gaysin, Azza
Publicado: (2025)