Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



LATEST > REPORTS:
RSS-Feedprevious PreviousNext next

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-047 | 10th April 2025
Michael Jaber, Yang P. Liu, Shachar Lovett, Anthony Ostuni, Mehtaab Sawhney

Quasipolynomial bounds for the corners theorem

Let $G$ be a finite abelian group and $A$ be a subset of $G \times G$ which is corner--free, meaning that there are no $x, y \in G$ and $d \in G \setminus \{0\}$ such that $(x, y)$, $(x+d, y)$, $(x, y+d) \in A$. We prove that
$|A| \le |G|^2 ... more >>>


TR25-046 | 12th April 2025
Gil Cohen, Leonard Schulman, Piyush Srivastava

The Rate-Immediacy Barrier in Explicit Tree Code Constructions

Since the introduction of tree codes by Schulman (STOC 1993), explicit construction of such codes has remained a notorious challenge. While the construction of asymptotically-good explicit tree codes continues to be elusive, a work by Cohen, Haeupler and Schulman (STOC 2018), as well as the state-of-the-art construction by Ben Yaacov, ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint