:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Bhargav, C. S., Dwivedi, Prateek, Saxena, Nitin
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2506.19604
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Monotone Bounded-Depth Complexity of Homomorphism Polynomials
by: Bhargav, C. S., et al.
Published: (2025)

Complexity of counting points on curves and the factor $P_1(T)$ of the zeta function of surfaces
by: Roy, Diptajit, et al.
Published: (2025)

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

Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
by: Dwivedi, Prateek, et al.
Published: (2026)

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

On the communication complexity of finding a king in a tournament
by: Mande, Nikhil S., et al.
Published: (2024)

Completeness classes in algebraic complexity theory
by: Bürgisser, Peter
Published: (2024)

Unconventional complexity classes in unconventional computing (extended abstract)
by: Porreca, Antonio E.
Published: (2024)

Entanglement-Dependent Error Bounds for Hamiltonian Simulation
by: Kulkarni, Prateek P.
Published: (2026)

Quantum Algorithms for Approximate Graph Isomorphism Testing
by: Kulkarni, Prateek P.
Published: (2026)

How to fit large complexity classes into TFNP
by: Thapen, Neil
Published: (2024)

Encoding of algebraic geometry codes with quasi-linear complexity $O(N\log N)$
by: Li, Songsong, et al.
Published: (2024)

Separating complexity classes of LCL problems on grids
by: Berlow, Katalin, et al.
Published: (2025)

Optimal Pseudorandom Generators for Low-Degree Polynomials Over Moderately Large Fields
by: Dwivedi, Ashish, et al.
Published: (2024)

Characterizations and models for the $C_{1,r}$ class and quantum annulus
by: Pal, Sourav, et al.
Published: (2022)

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

Optimal Sensor and Actuator Selection for Factored Markov Decision Processes: Complexity, Approximability and Algorithms
by: Bhargav, Jayanth, et al.
Published: (2024)

On a class of interdiction problems with partition matroids: complexity and polynomial-time algorithms
by: Ketkov, Sergey S., et al.
Published: (2024)

Approximate Degree Composition for Recursive Functions
by: Chakraborty, Sourav, et al.
Published: (2024)

The Parameterized Complexity of Terminal Monitoring Set
by: Aravind, N. R., et al.
Published: (2024)

The complexity of computing in continuous time: space complexity is precision
by: Blanc, Manon, et al.
Published: (2024)

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

On the complexity of Multipacking
by: Das, Sandip, et al.
Published: (2026)

The complexity of convexity number and percolation time in the cycle convexity
by: Lima, Carlos V. G. C., et al.
Published: (2024)

Submodular Information Selection for Hypothesis Testing with Misclassification Penalties
by: Bhargav, Jayanth, et al.
Published: (2024)

Computing the $D$-base and $D$-relation in finite closure systems
by: Adaricheva, Kira, et al.
Published: (2024)

Instance complexity of Boolean functions
by: Liu, Alison Hsiang-Hsuan, et al.
Published: (2023)

Unambiguous parity-query complexity
by: Gavinsky, Dmytro
Published: (2024)

Bounds for Hardness Condensation in the Query Model
by: Kayal, Chandrima, et al.
Published: (2026)

A new metric for evaluating the performance and complexity of computer programs: A new approach to the traditional ways of measuring the complexity of algorithms and estimating running times
by: Folea, Rares, et al.
Published: (2025)

On complexity of restricted fragments of Decision DNNF
by: Calí, Andrea, et al.
Published: (2025)

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

On the complexity of the word problem of the R. Thompson group V
by: Birget, J. C.
Published: (2022)

Between the deterministic and non-deterministic query complexity
by: Gerbner, Dániel
Published: (2019)

On the complexity of embedding in graph products
by: Biedl, Therese, et al.
Published: (2023)

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

A domain in $\mathbb C^4$ and its connection with $μ$-synthesis problem
by: Pal, Sourav, et al.
Published: (2026)

Communication complexity of pointer chasing via the fixed-set lemma
by: Viola, Emanuele
Published: (2025)

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
by: Cai, Jin-Yi, et al.
Published: (2024)

On the complexity of covering points by guillotine cuts
by: Garijo, Delia, et al.
Published: (2026)