Copertina

Deterministic factorization of constant-depth algebraic circuits in subexponential time

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bhattacharjee, Somnath, Kumar, Mrinal, Ramanathan, Varun, Saptharishi, Ramprasad, Saraf, Shubhangi
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
di: Kumar, Mrinal, et al.
Pubblicazione: (2024)

Constant-depth circuits for polynomial GCD over any characteristic
di: Bhattacharjee, Somnath, et al.
Pubblicazione: (2025)

Closure under factorization from a result of Furstenberg
di: Bhattacharjee, Somnath, et al.
Pubblicazione: (2025)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
di: Yang, Yang
Pubblicazione: (2024)

Deterministic Independent Sets in the Semi-Streaming Model
di: Ye, Daniel
Pubblicazione: (2025)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
di: Wang, Yichuan
Pubblicazione: (2024)

Self-referential instances of the dominating set problem are irreducible
di: Zhou, Guangyan
Pubblicazione: (2026)

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting
di: Grossman, Ofer, et al.
Pubblicazione: (2023)

Kronecker scaling of tensors with applications to arithmetic circuits and algorithms
di: Björklund, Andreas, et al.
Pubblicazione: (2025)

Black-Box Identity Testing of Noncommutative Rational Formulas in Deterministic Quasipolynomial Time
di: Arvind, V., et al.
Pubblicazione: (2023)

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
di: Gaspers, Serge, et al.
Pubblicazione: (2025)

Most Juntas Saturate the Hardcore Lemma
di: Kumar, Vinayak M.
Pubblicazione: (2025)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
di: Gaikwad, Ajinkya, et al.
Pubblicazione: (2025)

The complexity of testing all properties of planar graphs, and the role of isomorphism
di: Basu, Sabyasachi, et al.
Pubblicazione: (2021)

Parameterized Algorithms for Editing to Uniform Cluster Graph
di: Gaikwad, Ajinkya, et al.
Pubblicazione: (2024)

Precoloring extension with demands on paths
di: Das, Arun Kumar, et al.
Pubblicazione: (2025)

Linear Hashing Is Optimal
di: Jaber, Michael, et al.
Pubblicazione: (2025)

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields
di: Rai, Shanthanu S
Pubblicazione: (2024)

On the Parameterized Complexity of Min-Sum-Radii
di: Kumar, Pankaj, et al.
Pubblicazione: (2026)

Deterministic Algorithm for Non-monotone Submodular Maximization under Matroid and Knapsack Constraints
di: Chen, Shengminjie, et al.
Pubblicazione: (2026)

A quantum neural network framework for scalable quantum circuit approximation of unitary matrices
di: Sarkar, Rohit Sarma, et al.
Pubblicazione: (2024)

Constant congestion linkages in polynomially strong digraphs in polynomial time
di: Lopes, Raul, et al.
Pubblicazione: (2024)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
di: Greilhuber, Jakob, et al.
Pubblicazione: (2025)

The Trichotomy of Regular Property Testing
di: Bathie, Gabriel, et al.
Pubblicazione: (2025)

Downward self-reducibility in the total function polynomial hierarchy
di: Gajulapalli, Karthik, et al.
Pubblicazione: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
di: Fujie, Yuto, et al.
Pubblicazione: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
di: Moroie, Gregory
Pubblicazione: (2025)

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
di: Gholizadeh, Hossein, et al.
Pubblicazione: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
di: Herrmann, Anton, et al.
Pubblicazione: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
di: Maalouly, Nicolas El, et al.
Pubblicazione: (2025)

k-SUM Hardness Implies Treewidth-SETH
di: Lampis, Michael
Pubblicazione: (2025)

Efficient Catalytic Graph Algorithms
di: Cook, James, et al.
Pubblicazione: (2025)

Minimizing Envy and Maximizing Happiness in Graphical House Allocation
di: Dhar, Anubhav, et al.
Pubblicazione: (2025)

Scheduling Problems with Constrained Rejections
di: Davies, Sami, et al.
Pubblicazione: (2025)

Graded Projection Recursion (GPR): Corrections, Obstructions, and Conservative Approximate Matrix Multiplication
di: Uhlmann, Jeffrey
Pubblicazione: (2025)

Parameterized Complexity of Vehicle Routing
di: Döring, Michelle, et al.
Pubblicazione: (2025)

Geometric Interpretation of 3-SAT and Phase Transition
di: Gillet, Frederic
Pubblicazione: (2025)

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
di: Scheder, Dominik, et al.
Pubblicazione: (2025)

Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
di: Curticapean, Radu, et al.
Pubblicazione: (2025)