Cover Image

Maximum Matching and Related Problems in Catalytic Logspace

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chakraborty, Srijan, Datta, Samir, Kusre, Aryan, Mukhopadhyay, Partha, Sinhababu, Amit
Format:	Preprint
Published:	2026
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Derandomizing Isolation In Catalytic Logspace
by: Arvind, V., et al.
Published: (2025)

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

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

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

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

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

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

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

Negations are powerful even in small depth
by: Cavalar, Bruno, et al.
Published: (2025)

Limitation of Quantum Walk Approach to the Maximum Matching Problem
by: Júnior, Alcides Gomes Andrade, et al.
Published: (2025)

Pseudodeterministic Algorithms for Minimum Cut Problems
by: Agarwala, Aryan, et al.
Published: (2025)

On the Exact Matching Problem in Dense Graphs
by: Maalouly, Nicolas El, et al.
Published: (2024)

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

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

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

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

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

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)

$\#$W[1] = $\text{FPT}$: Fixed-Parameter Tractable Exact Algorithms for the $\#k$-Matching Problem
by: Yi, Yongming
Published: (2026)

On the Maximum Distance Sublattice Problem and Closest Vector Problem
by: Kumar, Rajendra, et al.
Published: (2018)

On Computational Aspects of Ordered Matching Problems
by: Čertík, Michal, et al.
Published: (2025)

The Descriptive Complexity of Relation Modification Problems
by: Chudigiewitsch, Florian, et al.
Published: (2026)

Improved Lower Bounds for Approximating Parameterized Nearest Codeword and Related Problems under ETH
by: Li, Shuangle, et al.
Published: (2024)

Quantum k-SAT Related Hypergraph Problems
by: Kremer, Simon-Luca, et al.
Published: (2025)

Tight Bounds for Quantum Phase Estimation and Related Problems
by: Mande, Nikhil S., et al.
Published: (2023)

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

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
by: Gupta, Rishav, et al.
Published: (2026)

Symmetric Exponential Time Requires Near-Maximum Circuit Size: Simplified, Truly Uniform
by: Li, Zeyong
Published: (2023)

Deterministic Hardness of Approximation For SVP in all Finite $\ell_p$ Norms
by: Hair, Isaac M, et al.
Published: (2026)

SVP$_p$ is Deterministically NP-Hard for all $p > 2$, Even to Approximate Within a Factor of $2^{\log^{1-\varepsilon} n}$
by: Hair, Isaac M., et al.
Published: (2025)

Higher Hardness Results for the Reconfiguration of Odd Matchings
by: Dorfer, Joseph
Published: (2026)

Parameterized Complexity of Fair Many-to-One Matchings
by: Javadi, Ramin, 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)

Maximum Reachability Orientation of Mixed Graphs
by: Hörsch, Florian
Published: (2025)

Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius
by: Lucke, Felicia, et al.
Published: (2023)

A Qubit, a Coin, and an Advice String Walk Into a Relational Problem
by: Aaronson, Scott, et al.
Published: (2023)

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