Imagen de Portada

On Extremal Properties of k-CNF: Capturing Threshold Functions

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Gurumukhani, Mohit, Künnemann, Marvin, Paturi, Ramamohan
Formato:	Preprint
Publicado:	2024
Materias:	Computational Complexity
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

Local Enumeration: The Not-All-Equal Case
por: Gurumukhani, Mohit, et al.
Publicado: (2025)

Local Enumeration and Majority Lower Bounds
por: Gurumukhani, Mohit, et al.
Publicado: (2024)

Optimal Depth-Three Circuits for Inner Product
por: Gurumukhani, Mohit, et al.
Publicado: (2026)

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

Completeness Theorems for k-SUM and Geometric Friends: Deciding Fragments of Integer Linear Arithmetic
por: Gokaj, Geri, et al.
Publicado: (2025)

On the Existence of Seedless Condensers: Exploring the Terrain
por: Chattopadhyay, Eshan, et al.
Publicado: (2023)

Extractors for Polynomial Sources over $\mathbb{F}_2$
por: Chattopadhyay, Eshan, et al.
Publicado: (2023)

When Does Sparsity Help for k-Independent Set in Hypergraphs and Other Boolean CSPs?
por: Fritsch, Timo, et al.
Publicado: (2026)

The Role of Regularity in (Hyper-)Clique Detection and Implications for Optimizing Boolean CSPs
por: Fischer, Nick, et al.
Publicado: (2025)

Fine-Grained Classification Of Detecting Dominating Patterns
por: Dransfeld, Jonathan, et al.
Publicado: (2025)

Condensing and Extracting Against Online Adversaries
por: Chattopadhyay, Eshan, et al.
Publicado: (2024)

Hard CNF Instances for Ideal Proof Systems
por: Hakoniemi, Tuomas, et al.
Publicado: (2026)

Two-Sided Lossless Expanders in the Unbalanced Setting
por: Chattopadhyay, Eshan, et al.
Publicado: (2024)

On the Satisfaction Probabilities of $k$-CNF Formulas
por: Tantau, Till
Publicado: (2022)

The 2CNF Boolean Formula Satisfiability Problem and the Linear Space Hypothesis
por: Yamakami, Tomoyuki
Publicado: (2017)

Improved Bounds for Coin Flipping, Leader Election, and Random Selection
por: Chattopadhyay, Eshan, et al.
Publicado: (2025)

The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
por: Bringmann, Karl, et al.
Publicado: (2023)

Compilation and Fast Model Counting beyond CNF
por: de Colnet, Alexis, et al.
Publicado: (2025)

Compression with wildcards: All models of a Boolean 2-CNF
por: Wild, Marcel
Publicado: (2012)

A Pseudorandom Generator for Functions of Low-Degree Polynomial Threshold Functions
por: Yao, Penghui, et al.
Publicado: (2025)

Forrelation is Extremally Hard
por: Girish, Uma, et al.
Publicado: (2025)

Sharp Thresholds for the Overlap Gap Property: Ising $p$-Spin Glass and Random $k$-SAT
por: Kızıldağ, Eren C.
Publicado: (2023)

Multiplayer Parallel Repetition Is the Same as High-Dimensional Extremal Combinatorics
por: Mittal, Kunal
Publicado: (2025)

On Boolean PCSPs with Polynomial Threshold Polymorphisms
por: Michno, Katzper
Publicado: (2025)

Low Sets and Closure Properties of Counting Function Classes
por: Ivanashev, Yaroslav
Publicado: (2025)

Complexity Thresholds for the Constrained Colored Token Swapping Problem
por: Bilò, Davide, et al.
Publicado: (2026)

Elementary Quantum Recursion Schemes That Capture Quantum Polylogarithmic Time Computability of Quantum Functions
por: Yamakami, Tomoyuki
Publicado: (2023)

Quantum Threshold is Powerful
por: Grier, Daniel, et al.
Publicado: (2024)

On Approximability of Satisfiable k-CSPs: V
por: Bhangale, Amey, et al.
Publicado: (2024)

Trading Determinism for Time: The k-Reach Problem
por: Bhadra, Ronak, et al.
Publicado: (2024)

Near Optimal Hardness of Approximating $k$-CSP
por: Minzer, Dor, et al.
Publicado: (2025)

Width Hierarchy for k-OBDD of Small Width
por: Khadiev, Kamil
Publicado: (2015)

Constant-Cost Communication is not Reducible to k-Hamming Distance
por: Fang, Yuting, et al.
Publicado: (2024)

Almost Polynomial Factor Inapproximability for Parameterized k-Clique
por: S., Karthik C., et al.
Publicado: (2021)

Limits of Sequential Local Algorithms on the Random $k$-XORSAT Problem
por: Yung, Kingsley
Publicado: (2024)

Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR
por: Błasiok, Jarosław, et al.
Publicado: (2026)

Tensor Spectral Threshold is $\exists\mathbb{R}$-Hard
por: Majumdar, Angshul
Publicado: (2026)

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
por: Gu, Yuzhou, et al.
Publicado: (2025)

On Approximability of Satisfiable $k$-CSPs: VI
por: Bhangale, Amey, et al.
Publicado: (2024)

On Approximability of Satisfiable $k$-CSPs: VII
por: Bhangale, Amey, et al.
Publicado: (2024)