:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Bhattacharjee, Somnath, Kumar, Mrinal, Rai, Shanthanu S., Ramanathan, Varun, Saptharishi, Ramprasad, Saraf, Shubhangi
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2506.23214
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Deterministic factorization of constant-depth algebraic circuits in subexponential time
by: Bhattacharjee, Somnath, et al.
Published: (2025)

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

Modular composition & polynomial GCD in the border of small, shallow circuits
by: Andrews, Robert, et al.
Published: (2025)

If VNP is hard, then so are equations for it
by: Kumar, Mrinal, et al.
Published: (2020)

On the Existence of Algebraic Natural Proofs
by: Chatterjee, Prerona, et al.
Published: (2020)

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

An exposition of recent list-size bounds of FRS Codes
by: Garg, Abhibhav, et al.
Published: (2025)

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

Lower Bounds for Set-Multilinear Branching Programs
by: Chatterjee, Prerona, et al.
Published: (2023)

Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes
by: Kopparty, Swastik, et al.
Published: (2023)

Exponential lower bound via exponential sums
by: Bhattacharjee, Somnath, et al.
Published: (2026)

Advances in List Decoding of Polynomial Codes
by: Kumar, Mrinal, et al.
Published: (2026)

Deterministic list decoding of Reed-Solomon codes
by: Chatterjee, Soham, et al.
Published: (2025)

High Rate Multivariate Polynomial Evaluation Codes
by: Kopparty, Swastik, et al.
Published: (2024)

On hardness of computing analytic Brouwer degree
by: Chakraborty, Somnath
Published: (2023)

Fast list recovery of univariate multiplicity and folded Reed-Solomon codes
by: Goyal, Rohan, et al.
Published: (2025)

Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes
by: Goyal, Rohan, et al.
Published: (2023)

New Bounds for the Ideal Proof System in Positive Characteristic
by: Behera, Amik Raj, et al.
Published: (2025)

Closure Properties and Characterizations of TotP
by: Ivanashev, Yaroslav
Published: (2025)

Algorithmizing the Multiplicity Schwartz-Zippel Lemma
by: Bhandari, Siddharth, et al.
Published: (2021)

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

A Hierarchy of Tinhofer Graphs: Separations and Membership Testing
by: Bhattacharjee, Sutanay, et al.
Published: (2026)

A primer on the closure of algebraic complexity classes under factoring
by: Bhargav, C. S., et al.
Published: (2025)

$m$-Eternal Dominating Set Problem on Subclasses of Chordal Graphs
by: Rai, Ashutosh, et al.
Published: (2026)

Debordering Closure Results in Determinantal and Pfaffian Ideals
by: Dey, Anakin, et al.
Published: (2025)

Determination Problems for Orbit Closures and Matrix Groups
by: Manssour, Rida Ait El, et al.
Published: (2024)

Almost-catalytic Computation
by: Bisoyi, Sagar, et al.
Published: (2024)

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
by: Armand, Jules, et al.
Published: (2025)

Bounding the computational power of bosonic systems
by: Upreti, Varun, et al.
Published: (2025)

Tractability results for integration in subspaces of the Wiener algebra
by: Dick, Josef, et al.
Published: (2024)

Some structural complexity results for $\exists\mathbb R$
by: Meer, Klaus, et al.
Published: (2025)

On the Computation of the Zariski Closure of Finitely Generated Groups of Matrices
by: Nosan, Klara, et al.
Published: (2021)

New results in canonical polyadic decomposition over finite fields
by: Yang, Jason
Published: (2025)

When quantum resources backfire: Non-gaussianity and symplectic coherence in noisy bosonic circuits
by: Upreti, Varun, et al.
Published: (2025)

How Global Calibration Strengthens Multiaccuracy
by: Casacuberta, Sílvia, et al.
Published: (2025)

Sensitivity and Query Complexity under Uncertainty
by: Benson, Deepu, et al.
Published: (2025)

Deterministic Weighted Automata under Partial Observability
by: Michaliszyn, Jakub, et al.
Published: (2024)

Hardness results for decoding the surface code with Pauli noise
by: Fischer, Alex, et al.
Published: (2023)

New Pseudorandom Generators and Correlation Bounds Using Extractors
by: Kumar, Vinayak M.
Published: (2025)