DROPS

Document

DOI: 10.4230/LIPIcs.CCC.2026.3

Improved Bounds on the Space Complexity of Circuit Evaluation

Authors: Yakov Shalunov

Published in: LIPIcs, Volume 383, 41st Computational Complexity Conference (CCC 2026)

Abstract

Williams (STOC 2025) recently proved that time-t multitape Turing machines can be simulated using O(√{t log t}) space using the Cook-Mertz (STOC 2024) tree evaluation procedure. As Williams notes, applying this result to fast algorithms for the circuit value problem implies an O(√s ⋅ polylog s) space algorithm for evaluating circuits with s gates. In this work, we provide a direct reduction from circuit value to tree evaluation without passing through Turing machines, simultaneously improving the bound to O(√{s log s}) space and providing a proof with fewer layers of abstraction. This result can be thought of as a "sibling" result to Williams' for circuit complexity instead of time; in particular, using the fact that time-t Turing machines have size O(t log t) circuits, we can recover a slightly weakened version of Williams' result, simulating time-t machines in space O(√t log t).

Cite as

Yakov Shalunov. Improved Bounds on the Space Complexity of Circuit Evaluation. In 41st Computational Complexity Conference (CCC 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 383, pp. 3:1-3:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{shalunov:LIPIcs.CCC.2026.3,
  author =	{Shalunov, Yakov},
  title =	{{Improved Bounds on the Space Complexity of Circuit Evaluation}},
  booktitle =	{41st Computational Complexity Conference (CCC 2026)},
  pages =	{3:1--3:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-437-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{383},
  editor =	{Moshkovitz, Dana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2026.3},
  URN =		{urn:nbn:de:0030-drops-270451},
  doi =		{10.4230/LIPIcs.CCC.2026.3},
  annote =	{Keywords: circuit value problem CVP, space complexity, tree evaluation problem}
}

Document

DOI: 10.4230/LIPIcs.MFCS.2024.83

Leakage-Resilient Hardness Equivalence to Logspace Derandomization

Authors: Yakov Shalunov

Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)

Abstract

Efficient derandomization has long been a goal in complexity theory, and a major recent result by Yanyi Liu and Rafael Pass identifies a new class of hardness assumption under which it is possible to perform time-bounded derandomization efficiently: that of "leakage-resilient hardness." They identify a specific form of this assumption which is equivalent to prP = prBPP. In this paper, we pursue an equivalence to derandomization of prBP⋅L (logspace promise problems with two-way randomness) through techniques analogous to Liu and Pass. We are able to obtain an equivalence between a similar "leakage-resilient hardness" assumption and a slightly stronger statement than derandomization of prBP⋅L, that of finding "non-no" instances of "promise search problems."

Cite as

Yakov Shalunov. Leakage-Resilient Hardness Equivalence to Logspace Derandomization. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 83:1-83:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{shalunov:LIPIcs.MFCS.2024.83,
  author =	{Shalunov, Yakov},
  title =	{{Leakage-Resilient Hardness Equivalence to Logspace Derandomization}},
  booktitle =	{49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)},
  pages =	{83:1--83:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-335-5},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{306},
  editor =	{Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.83},
  URN =		{urn:nbn:de:0030-drops-206395},
  doi =		{10.4230/LIPIcs.MFCS.2024.83},
  annote =	{Keywords: Derandomization, logspace computation, leakage-resilient hardness, psuedorandom generators}
}

Search Results

Documents authored by Shalunov, Yakov

Improved Bounds on the Space Complexity of Circuit Evaluation

Abstract

Cite as

Leakage-Resilient Hardness Equivalence to Logspace Derandomization

Abstract

Cite as

Thanks for your feedback!

Could not send message