:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Chatterjee, Prerona, Kumar, Mrinal, Ramya, C, Saptharishi, Ramprasad, Tengse, Anamay
Format:	Preprint
Published:	2020
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2004.14147
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

Lower Bounds from Succinct Hitting Sets
by: Chatterjee, Prerona, et al.
Published: (2023)

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

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

The Complexity of Order-Finding for ROABPs
by: Bhargava, Vishwas, et al.
Published: (2024)

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

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

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

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

IPS Lower Bounds for Formulas and Sum of ROABPs
by: Chatterjee, Prerona, et al.
Published: (2025)

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

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

Lower bounds for planar Arithmetic Circuits
by: Ramya, C., et al.
Published: (2025)

On the Hardness of Order Finding and Equivalence Testing for ROABPs
by: Ramya, C., et al.
Published: (2025)

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

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

Fine-Grained Complexity via Quantum Natural Proofs
by: Chen, Yanlin, et al.
Published: (2025)

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

Efficient Polynomial Identity Testing Over Nonassociative Algebras
by: Mukhopadhyay, Partha, et al.
Published: (2025)

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)

Semi-Algebraic Proof Systems for QBF
by: Beyersdorff, Olaf, et al.
Published: (2025)

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals
by: Garg, Abhibhav, et al.
Published: (2025)

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

Algebraic Pseudorandomness in $VNC^0$
by: Andrews, Robert
Published: (2025)

On the Existence of Anomalies, The Reals Case
by: Epstein, Samuel
Published: (2023)

The Algebraic Cost of a Boolean Sum
by: Orzel, Ian, et al.
Published: (2025)

Symmetric Algebraic Circuits and Homomorphism Polynomials
by: Dawar, Anuj, et al.
Published: (2025)

Symmetric Proofs in the Ideal Proof System
by: Dawar, Anuj, et al.
Published: (2025)

On the Existence of Seedless Condensers: Exploring the Terrain
by: Chattopadhyay, Eshan, et al.
Published: (2023)

Distribution-Free Proofs of Proximity
by: Aaronson, Hugo, et al.
Published: (2023)

Separations in Proof Complexity and TFNP
by: Göös, Mika, et al.
Published: (2022)

Algebraic Global Gadgetry for Surjective Constraint Satisfaction
by: Chen, Hubie
Published: (2020)

Proof Systems Based on Structured Circuits
by: Micun, Matthäus, et al.
Published: (2026)

Recursive Jump Operators and Optimal Proof Systems
by: Egidy, Fabian
Published: (2026)

Hard CNF Instances for Ideal Proof Systems
by: Hakoniemi, Tuomas, et al.
Published: (2026)

Proof Complexity and Feasible Interpolation
by: Tabatabai, Amirhossein Akbar
Published: (2025)

On the Bit Size of Sum-of-Squares Proofs for Symmetric Formulations
by: Bortolotti, Alex, et al.
Published: (2025)

The SPARSE-Relativization Framework and Applications to Optimal Proof Systems
by: Egidy, Fabian
Published: (2026)