Cover Image

Problems from Optimization and Computational Algebra Equivalent to Hilbert's Nullstellensatz

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bläser, Markus, Dutta, Sagnik, Jindal, Gorav
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity I.1.2; G.1.6; F.1.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

PosSLP and Sum of Squares
by: Bläser, Markus, et al.
Published: (2024)

On the Counting Complexity of the Skolem Problem
by: Jindal, Gorav, et al.
Published: (2024)

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
by: Conneryd, Jonas, et al.
Published: (2025)

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants
by: Anand, Emile, et al.
Published: (2024)

Flexible Quaternion Generalized Minimal Residual Method for Ill-Posed Quaternion Inverse Problems
by: Liu, Xuan, et al.
Published: (2024)

Propagation by Selective Initialization and Its Application to Numerical Constraint Satisfaction Problems
by: van Emden, M. H., et al.
Published: (2004)

Universal Matrix Sparsifiers and Fast Deterministic Algorithms for Linear Algebra
by: Bhattacharjee, Rajarshi, et al.
Published: (2023)

Randomized Approach to Matrix Completion: Applications in Recommendation Systems and Image Inpainting
by: Krajewska, Antonina, et al.
Published: (2024)

Faster Inversion and Other Black Box Matrix Computations Using Efficient Block Projections
by: Eberly, Wayne, et al.
Published: (2007)

Imperative process algebra and models of computation
by: Middelburg, C. A.
Published: (2022)

Homogeneous Algebraic Complexity Theory and Algebraic Formulas
by: Dutta, Pranjal, et al.
Published: (2023)

Algorithmic hardness of the partition function for nucleic acid strands
by: Ducloz, Gwendal, et al.
Published: (2025)

Explicit Commutative ROABPs from Partial Derivatives
by: Bhargava, Vishwas, et al.
Published: (2024)

Fixed-parameter debordering of Waring rank
by: Dutta, Pranjal, et al.
Published: (2024)

Certification of the QR factor R, and of lattice basis reducedness
by: Villard, Gilles
Published: (2007)

On bounded depth proofs for Tseitin formulas on the grid; revisited
by: Håstad, Johan, et al.
Published: (2022)

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

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

Supercritical Tradeoffs for Monotone Circuits
by: Göös, Mika, et al.
Published: (2024)

Memory-Efficient Training with In-Place FFT Implementation
by: Ding, Xinyu, et al.
Published: (2025)

Which graph motif parameters count?
by: Bläser, Markus, et al.
Published: (2025)

On Sampling Lower Bounds for Polynomials
by: Khodabandeh, Mohammad Mahdi, et al.
Published: (2026)

Improved Spectral Density Estimation via Explicit and Implicit Deflation
by: Bhattacharjee, Rajarshi, et al.
Published: (2024)

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

Deep Learning for Solving and Estimating Dynamic Models in Economics and Finance
by: Scheidegger, Simon
Published: (2026)

Lifted Forward Planning in Relational Factored Markov Decision Processes with Concurrent Actions
by: Marwitz, Florian Andreas, et al.
Published: (2025)

Regular Tree Search for Simulation Optimization
by: Wang, Du-Yi, et al.
Published: (2025)

The Affine Divergence: Aligning Activation Updates Beyond Normalisation
by: Bird, George
Published: (2025)

Tensor-based Model Reduction and Identification for Generalized Memory Polynomial
by: Wang, Yuchao, et al.
Published: (2025)

Covariance Matrix Analysis for Optimal Portfolio Selection
by: Keith, Lim Hao Shen
Published: (2024)

Catalytic Computing and Register Programs Beyond Log-Depth
by: Alekseev, Yaroslav, et al.
Published: (2025)

Graph Neural Networks and Arithmetic Circuits
by: Barlag, Timon, et al.
Published: (2024)

Average Attention Transformers and Arithmetic Circuits
by: Ehrmuth, Lena, et al.
Published: (2026)

Recurrent Graph Neural Networks and Arithmetic Circuits
by: Barlag, Timon, et al.
Published: (2026)

The Deterministic Horizon: Impossibility Results as Design Specifications for Trustworthy AI Systems
by: Guo, Dongxin
Published: (2026)

Integer Polynomial Factorization by Recombination of Real Factors: Re-evaluating an Old Technique in Modern Era
by: Iravanian, Shahriar
Published: (2024)

An arithmetic method algorithm optimizing k-nearest neighbors compared to regression algorithms and evaluated on real world data sources
by: Anagnostopoulos, Theodoros, et al.
Published: (2026)

Beyond Worst-Case Subset Sum: An Adaptive, Structure-Aware Solver with Sub-$2^{n/2}$ Enumeration
by: Salas, Jesus
Published: (2025)

Graph-Based Deterministic Polynomial Framwork for NP Problems
by: Lee, Changryeol
Published: (2025)

Arithmetic Complexity of Solutions of the Dirichlet Problem
by: Boche, Holger, et al.
Published: (2026)