Buchumschlag

On Sampling Lower Bounds for Polynomials

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Khodabandeh, Mohammad Mahdi, Shinkar, Igor
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Computational Complexity Combinatorics G.2.1; F.1.3
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions
von: Pavlov, Gorgi
Veröffentlicht: (2026)

Col is PSPACE-complete on Triangular Grids
von: Burke, Kyle, et al.
Veröffentlicht: (2025)

Algorithmic hardness of the partition function for nucleic acid strands
von: Ducloz, Gwendal, et al.
Veröffentlicht: (2025)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
von: Anand, Emile, et al.
Veröffentlicht: (2024)

Misère Partizan Arc Kayles is PSPACE-complete, even on Planar Graphs
von: Burke, Kyle, et al.
Veröffentlicht: (2025)

Lower Bounds for Symmetric Circuits for the Determinant
von: Dawar, Anuj, et al.
Veröffentlicht: (2021)

Which graph motif parameters count?
von: Bläser, Markus, et al.
Veröffentlicht: (2025)

PosSLP and Sum of Squares
von: Bläser, Markus, et al.
Veröffentlicht: (2024)

Small Shadow Partitions
von: Kopparty, Swastik, et al.
Veröffentlicht: (2024)

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

A Tractability Gap Beyond Nim-Sums: It's Hard to Tell Whether a Bunch of Superstars Are Losers
von: Burke, Kyle, et al.
Veröffentlicht: (2024)

Lower Bounds for CSP Hierarchies Through Ideal Reduction
von: Conneryd, Jonas, et al.
Veröffentlicht: (2025)

Superpolynomial Length Lower Bounds for Tree-Like Semantic Proof Systems with Bounded Line Size
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2026)

Dichotomy for orderings?
von: Kun, Gábor, et al.
Veröffentlicht: (2025)

Shifted Partial Derivative Polynomial Rank and Codimension
von: Edwards, Darren J.
Veröffentlicht: (2025)

Symmetric Arithmetic Circuits
von: Dawar, Anuj, et al.
Veröffentlicht: (2020)

Rankwidth of Graphs with Balanced Separations: Expansion for Dense Graphs
von: Anand, Emile
Veröffentlicht: (2025)

Graph-Based Deterministic Polynomial Framwork for NP Problems
von: Lee, Changryeol
Veröffentlicht: (2025)

Formula Size-Depth Tradeoffs for Iterated Sub-Permutation Matrix Multiplication
von: Rossman, Benjamin
Veröffentlicht: (2024)

Battle Sheep is PSPACE-complete
von: Burke, Kyle, et al.
Veröffentlicht: (2025)

Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz
von: Bläser, Markus, et al.
Veröffentlicht: (2025)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
von: Conneryd, Jonas, et al.
Veröffentlicht: (2025)

Clique Is Hard on Average for Sherali-Adams with Bounded Coefficients
von: de Rezende, Susanna F., et al.
Veröffentlicht: (2024)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
von: Lela, Marko
Veröffentlicht: (2025)

Functional Lower Bounds in Algebraic Proofs: Symmetry, Lifting, and Barriers
von: Hakoniemi, Tuomas, et al.
Veröffentlicht: (2024)

Upper and Lower Bounds for the Linear Ordering Principle
von: Hirsch, Edward A., et al.
Veröffentlicht: (2025)

CLIQUE as an AND of Polynomial-Sized Monotone Constant-Depth Circuits
von: Bodnar, Levente
Veröffentlicht: (2024)

Reduction of the graph isomorphism problem to equality checking of $n$-variables polynomials and the algorithms that use the reduction
von: Prolubnikov, Alexander
Veröffentlicht: (2015)

Tensor-based Model Reduction and Identification for Generalized Memory Polynomial
von: Wang, Yuchao, et al.
Veröffentlicht: (2025)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
von: Antonelli, Melissa, et al.
Veröffentlicht: (2025)

Polynomial-time Tractable Problems over the $p$-adic Numbers
von: Fehm, Arno, et al.
Veröffentlicht: (2025)

On the Complexity of Determinations
von: Hellerstein, Joseph M.
Veröffentlicht: (2026)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
von: Chen, Yijia, et al.
Veröffentlicht: (2023)

Imperative process algebra and models of computation
von: Middelburg, C. A.
Veröffentlicht: (2022)

Faster Algorithms for Structured Matrix Multiplication via Flip Graph Search
von: Khoruzhii, Kirill, et al.
Veröffentlicht: (2025)

A Permutation Avoidance Game with Reverse Replies and Monotone Traps
von: Ulfarsson, Henning
Veröffentlicht: (2026)

Nonuniform Deterministic Finite Automata over finite algebraic structures
von: Idziak, Paweł M., et al.
Veröffentlicht: (2025)

Explicit separations between randomized and deterministic Number-on-Forehead communication
von: Kelley, Zander, et al.
Veröffentlicht: (2023)

On the Complexity of Problems on Graphs Defined on Groups
von: Das, Bireswar, et al.
Veröffentlicht: (2025)

Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections
von: Eberly, Wayne, et al.
Veröffentlicht: (2007)