Cover Image

The Bit Complexity of Dynamic Algebraic Formulas and their Determinants

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Anand, Emile, Brand, Jan van den, Ghadiri, Mehrdad, Zhang, Daniel
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity F.1.2; F.2.1; G.1.3
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

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

Entrywise Approximate Solutions for SDDM Systems in Almost-Linear Time
by: Farfan, Angelo, et al.
Published: (2025)

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

Col is PSPACE-complete on Triangular Grids
by: Burke, Kyle, et al.
Published: (2025)

On the Complexity of Determinations
by: Hellerstein, Joseph M.
Published: (2026)

The Banach-Butterfly Invariant: Influence-Adaptive Walsh Geometry for Ternary Polynomial Threshold Functions
by: Pavlov, Gorgi
Published: (2026)

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

The Structural Complexity of Matrix-Vector Multiplication
by: Anand, Emile, et al.
Published: (2025)

Lower Bounds for Symmetric Circuits for the Determinant
by: Dawar, Anuj, et al.
Published: (2021)

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

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

Rankwidth of Graphs with Balanced Separations: Expansion for Dense Graphs
by: Anand, Emile
Published: (2025)

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

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

Towards the Pseudorandomness of Expander Random Walks for Read-Once ACC0 circuits
by: Anand, Emile
Published: (2025)

Constructing Orthogonal Rational Function Vectors with an application in Rational Approximation
by: Vermeiren, Robbe
Published: (2026)

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

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

Symmetric Arithmetic Circuits
by: Dawar, Anuj, et al.
Published: (2020)

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

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

Dichotomy for orderings?
by: Kun, Gábor, et al.
Published: (2025)

Entrywise Approximation for Matrix Inversion and Linear Systems
by: Ghadiri, Mehrdad, et al.
Published: (2025)

$\rm P$ has polynomial-time finite-state verifiers
by: Gezer, M. Utkan, et al.
Published: (2023)

IECZ-III: Hardcore Condensation Lift with Size-Aware Invariants
by: Lela, Marko
Published: (2025)

On the Computation of 2-Dimensional Recurrence Equations
by: Natale, Giuseppe
Published: (2024)

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
by: Kumar, Mrinal, et al.
Published: (2018)

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

Pauli-structured preconditioning for quantum linear system solvers
by: Nie, Hantao, et al.
Published: (2026)

Quantum algorithms through graph composition
by: Cornelissen, Arjan
Published: (2025)

Quantum walks through generalized graph composition
by: Cornelissen, Arjan
Published: (2025)

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

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)

Towards New Characterizations of Small Circuit Classes via Discrete Ordinary Differential Equations
by: Antonelli, Melissa, et al.
Published: (2025)

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