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-121 | 27th July 2025
Karthik Gajulapalli, Surendra Ghentiyala, Zeyong Li, Sidhant Saraogi

Downward self-reducibility in the total function polynomial hierarchy

A problem $\mathcal{P}$ is considered downward self-reducible, if there exists an efficient algorithm for $\mathcal{P}$ that is allowed to make queries to only strictly smaller instances of $\mathcal{P}$. Downward self-reducibility has been well studied in the case of decision problems, and it is well known that any downward self-reducible problem ... more >>>


TR25-120 | 1st August 2025
Shuichi Hirahara, Naoto Ohsaka

Asymptotically Optimal Inapproximability of E$k$-SAT Reconfiguration

In the Maxmin E$k$-SAT Reconfiguration problem, we are given a satisfiable $k$-CNF formula $\varphi$ where each clause contains exactly $k$ literals, along with a pair of its satisfying assignments. The objective is transform one satisfying assignment into the other by repeatedly flipping the value of a single variable, while maximizing ... more >>>


TR25-119 | 30th July 2025
John Hitchcock, Adewale Sekoni, Hadi Shafei

Counting Martingales for Measure and Dimension in Complexity Classes

This paper makes two primary contributions. First, we introduce the concept of counting martingales and use it to define counting measures, counting dimensions, and counting strong dimensions. Second, we apply these new tools to strengthen previous circuit lower bounds.

Resource-bounded measure and dimension have traditionally focused on deterministic time ... more >>>



previous PreviousNext next


ISSN 1433-8092 | Imprint