Copertina

Towards infinite PCSP: a dichotomy for monochromatic cliques

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Banakh, Demian, Barsukov, Alexey, Nakajima, Tamio-Vesa
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Maximum $k$- vs. $\ell$-colourings of graphs
di: Nakajima, Tamio-Vesa, et al.
Pubblicazione: (2023)

On the complexity of symmetric vs. functional PCSPs
di: Nakajima, Tamio-Vesa, et al.
Pubblicazione: (2022)

A Dichotomy for Maximum PCSPs on Graphs
di: Nakajima, Tamio-Vesa, et al.
Pubblicazione: (2024)

Boolean PCSPs through the lens of Fourier Analysis
di: Banakh, Demian, et al.
Pubblicazione: (2026)

Injective hardness condition for PCSPs
di: Banakh, Demian, et al.
Pubblicazione: (2024)

Complexity of approximate conflict-free, linearly-ordered, and nonmonochromatic hypergraph colourings
di: Nakajima, Tamio-Vesa, et al.
Pubblicazione: (2025)

Strong Sparsification for 1-in-3-SAT via Polynomial Freiman-Ruzsa
di: Bedert, Benjamin, et al.
Pubblicazione: (2025)

1-in-3 vs. Not-All-Equal: Dichotomy of a broken promise
di: Ciardo, Lorenzo, et al.
Pubblicazione: (2023)

On guarded extensions of MMSNP
di: Barsukov, Alexey, et al.
Pubblicazione: (2023)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
di: Larrauri, Alberto
Pubblicazione: (2025)

Classical Simulation of Quantum CSP Strategies
di: Banakh, Demian, et al.
Pubblicazione: (2025)

From an odd arity signature to a Holant dichotomy
di: Meng, Boning, et al.
Pubblicazione: (2025)

Generalisations of Matrix Partitions : Complexity and Obstructions
di: Barsukov, Alexey, et al.
Pubblicazione: (2021)

Hardness of clique approximation for monotone circuits
di: Błasiok, Jarosław, et al.
Pubblicazione: (2025)

Maximum Cut on Interval Graphs of Interval Count Two is NP-complete
di: Barsukov, Alexey, et al.
Pubblicazione: (2022)

Dichotomies for \#CSP on graphs that forbid a clique as a minor
di: Meng, Boning, et al.
Pubblicazione: (2025)

The $\text{FP}^\text{NP}$ versus #P dichotomy for #EO
di: Meng, Boning, et al.
Pubblicazione: (2025)

On the complexity of Sandwich Problems for $M$-partitions
di: Barsukov, Alexey, et al.
Pubblicazione: (2026)

Towards a complexity-theoretic dichotomy for TQFT invariants
di: Bridges, Nicolas, et al.
Pubblicazione: (2025)

A topological proof of the Hell-Nešetřil dichotomy
di: Meyer, Sebastian, et al.
Pubblicazione: (2024)

A full dichotomy for Holant$^c$, inspired by quantum computation
di: Backens, Miriam
Pubblicazione: (2022)

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

A fine-grained dichotomy for the center problem on Gromov hyperbolic graphs
di: Ducoffe, Guillaume
Pubblicazione: (2026)

Limit on the computational power of $\mathrm{C}$-random strings
di: Milovanov, Alexey
Pubblicazione: (2026)

On the computational power of $C$-random strings
di: Milovanov, Alexey
Pubblicazione: (2024)

Algorithmic methods of finite discrete structures. Graph clique problem
di: Kurapov, Sergey, et al.
Pubblicazione: (2024)

Flow-augmentation III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
di: Kim, Eun Jung, et al.
Pubblicazione: (2022)

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

Edge-coloring problems with forbidden patterns and planted colors
di: Barsukov, Alexey, et al.
Pubblicazione: (2025)

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
di: Geniet, Colin, et al.
Pubblicazione: (2026)

Low-degree phase transitions for detecting a planted clique in sublinear time
di: Mardia, Jay, et al.
Pubblicazione: (2024)

The framework to unify all complexity dichotomy theorems for Boolean tensor networks
di: Xia, Mingji
Pubblicazione: (2026)

Vulnerability Abundance: A formal proof of infinite vulnerabilities in code
di: Leverett, Eireann, et al.
Pubblicazione: (2026)

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

An approximation algorithm for Maximum DiCut vs. Cut
di: Nakajima, Tamio-Vesa, et al.
Pubblicazione: (2024)

Maximum And- vs. Even-SAT
di: Nakajima, Tamio-Vesa, et al.
Pubblicazione: (2024)

The hidden subgroup problem for infinite groups
di: Kuperberg, Greg
Pubblicazione: (2025)

Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs
di: Aivasiliotis, Panagiotis, et al.
Pubblicazione: (2025)

From Alternation to FPRAS: Toward a Complexity Classification of Approximate Counting
di: Hecher, Markus, et al.
Pubblicazione: (2025)

Toward Better Depth Lower Bounds: Strong Composition of XOR and a Random Function
di: Chukhin, Nikolai, et al.
Pubblicazione: (2024)