Cover Image

Derandomizing Isolation In Catalytic Logspace

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Arvind, V., Chakraborty, Srijan, Datta, Samir
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Maximum Matching and Related Problems in Catalytic Logspace
by: Chakraborty, Srijan, et al.
Published: (2026)

Bipartite Matching is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
by: Shalunov, Yakov
Published: (2023)

Linear Matroid Intersection is in Catalytic Logspace
by: Agarwala, Aryan, et al.
Published: (2025)

Game Derandomization
by: Epstein, Samuel
Published: (2024)

Revisiting Tree Canonization using polynomials
by: Arvind, V., et al.
Published: (2024)

Derandomizing Multivariate Polynomial Factoring for Low Degree Factors
by: Dutta, Pranjal, et al.
Published: (2024)

$\exists\mathbb{R}$-Completeness of Tensor Degeneracy and a Derandomization Barrier for Hyperdeterminants
by: Majumdar, Angshul
Published: (2026)

Derandomizing Multi-Distribution Learning
by: Larsen, Kasper Green, et al.
Published: (2024)

On Efficient Noncommutative Polynomial Factorization via Higman Linearization
by: Arvind, V., et al.
Published: (2022)

Derandomized Non-Abelian Homomorphism Testing in Low Soundness Regime
by: Mittal, Tushant, et al.
Published: (2024)

A parallel algorithm for the odd two-face shortest k-disjoint path problem
by: Chakraborty, Srijan, et al.
Published: (2025)

Dynamic Planar Graph Isomorphism is in DynFO
by: Datta, Samir, et al.
Published: (2026)

Parallel Complexity of Depth-First-Search and Maximal path in restricted graph classes
by: Chauhan, Archit, et al.
Published: (2025)

A Multivariate to Bivariate Reduction for Noncommutative Rank and Related Results
by: Arvind, Vikraman, et al.
Published: (2024)

Collapsing Catalytic Classes
by: Koucký, Michal, et al.
Published: (2025)

Lossy Catalytic Computation
by: Gupta, Chetan, et al.
Published: (2024)

Query maintenance under batch changes with small-depth circuits
by: Datta, Samir, et al.
Published: (2024)

On a Hierarchy of Spectral Invariants for Graphs
by: Arvind, V., et al.
Published: (2023)

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

Structure of sparse Boolean functions over Abelian groups, and its application to testing
by: Chakraborty, Sourav, et al.
Published: (2024)

Fast exact algorithms via the Matrix Tree Theorem
by: Arvind, V., et al.
Published: (2025)

Trading Determinism for Noncommutativity in Edmonds' Problem
by: Arvind, V., et al.
Published: (2024)

Separations between Combinatorial Measures for Transitive Functions
by: Chakraborty, Sourav, et al.
Published: (2021)

Spectral Norm, Economical Sieve, and Linear Invariance Testing of Boolean Functions
by: Datta, Swarnalipa, et al.
Published: (2023)

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

On the Expressibility of the Reconstructional Color Refinement
by: Arvind, V., et al.
Published: (2024)

Efficient Catalytic Graph Algorithms
by: Cook, James, et al.
Published: (2025)

Understanding Robust Catalytic Computing
by: Koucký, Michal, et al.
Published: (2026)

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

On the Complexity of Vertex-Splitting Into an Interval Graph
by: Abu-Khzam, Faisal N., et al.
Published: (2026)

Fully Characterizing Lossy Catalytic Computation
by: Folkertsma, Marten, et al.
Published: (2024)

Exponential improvements to the average-case hardness of BosonSampling
by: Bouland, Adam, et al.
Published: (2024)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
by: Chakraborty, Dibyayan, et al.
Published: (2024)

Polynomial-Time Almost Log-Space Tree Evaluation by Catalytic Pebbling
by: Asadi, Vahid R., et al.
Published: (2026)

On full-separating sets and related codes in graphs
by: Chakraborty, Dipayan, et al.
Published: (2024)

The Interplay Between Domination and Separation in Graphs
by: Chakraborty, Dipayan, et al.
Published: (2026)

Complexity-theoretic foundations of BosonSampling with a linear number of modes
by: Bouland, Adam, et al.
Published: (2023)

Efficient Isolation of Perfect Matching in O(log n) Genus Bipartite Graphs
by: Gupta, Chetan, et al.
Published: (2025)