Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > LOSSY CODE:
Reports tagged with lossy code:
TR25-048 | 11th April 2025
Aryan Agarwala, Ian Mertz

Bipartite Matching is in Catalytic Logspace

Matching is a central problem in theoretical computer science, with a large body of work spanning the last five decades. However, understanding matching in the time-space bounded setting remains a longstanding open question, even in the presence of additional resources such as randomness or non-determinism.

In this work we study ... more >>>


TR25-123 | 25th July 2025
Surendra Ghentiyala, Zeyong Li

Hierarchies within TFNP: building blocks and collapses

We initiate the study of complexity classes ${A^B}$ where ${A}$ and ${B}$ are both ${TFNP}$ subclasses. For example, we consider complexity classes of the form ${PPP^{PPP}}$, ${PPAD^{PPA}}$, and ${PPA^{PLS}}$. We define complete problems for such classes, and show that they belong in ${TFNP}$. These definitions require some care, since ... more >>>




ISSN 1433-8092 | Imprint