3 Search Results for "Sberlo, Ori"

Document

DOI: 10.4230/LIPIcs.CCC.2024.4

Derandomizing Logspace with a Small Shared Hard Drive

Authors: Edward Pyne

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract

We obtain new catalytic algorithms for space-bounded derandomization. In the catalytic computation model introduced by (Buhrman, Cleve, Koucký, Loff, and Speelman STOC 2013), we are given a small worktape, and a larger catalytic tape that has an arbitrary initial configuration. We may edit this tape, but it must be exactly restored to its initial configuration at the completion of the computation. We prove that BPSPACE[S] ⊆ CSPACE[S,S²] where BPSPACE[S] corresponds to randomized space S computation, and CSPACE[S,C] corresponds to catalytic algorithms that use O(S) bits of workspace and O(C) bits of catalytic space. Previously, only BPSPACE[S] ⊆ CSPACE[S,2^O(S)] was known. In fact, we prove a general tradeoff, that for every α ∈ [1,1.5], BPSPACE[S] ⊆ CSPACE[S^α,S^(3-α)]. We do not use the algebraic techniques of prior work on catalytic computation. Instead, we develop an algorithm that branches based on if the catalytic tape is conditionally random, and instantiate this primitive in a recursive framework. Our result gives an alternate proof of the best known time-space tradeoff for BPSPACE[S], due to (Cai, Chakaravarthy, and van Melkebeek, Theory Comput. Sys. 2006). As a final application, we extend our results to solve search problems in CSPACE[S,S²]. As far as we are aware, this constitutes the first study of search problems in the catalytic computing model.

Cite as

Edward Pyne. Derandomizing Logspace with a Small Shared Hard Drive. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{pyne:LIPIcs.CCC.2024.4,
  author =	{Pyne, Edward},
  title =	{{Derandomizing Logspace with a Small Shared Hard Drive}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{4:1--4:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.4},
  URN =		{urn:nbn:de:0030-drops-204006},
  doi =		{10.4230/LIPIcs.CCC.2024.4},
  annote =	{Keywords: Catalytic computation, space-bounded computation, derandomization}
}

Document

DOI: 10.4230/LIPIcs.CCC.2024.32

BPL ⊆ L-AC¹

Authors: Kuan Cheng and Yichuan Wang

Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)

Abstract

Whether BPL = 𝖫 (which is conjectured to be equal) or even whether BPL ⊆ NL, is a big open problem in theoretical computer science. It is well known that 𝖫 ⊆ NL ⊆ L-AC¹. In this work we show that BPL ⊆ L-AC¹ also holds. Our proof is based on a new iteration method for boosting precision in approximating matrix powering, which is inspired by the Richardson Iteration method developed in a recent line of work [AmirMahdi Ahmadinejad et al., 2020; Edward Pyne and Salil P. Vadhan, 2021; Gil Cohen et al., 2021; William M. Hoza, 2021; Gil Cohen et al., 2023; Aaron (Louie) Putterman and Edward Pyne, 2023; Lijie Chen et al., 2023]. We also improve the algorithm for approximate counting in low-depth L-AC circuits from an additive error setting to a multiplicative error setting.

Cite as

Kuan Cheng and Yichuan Wang. BPL ⊆ L-AC¹. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{cheng_et_al:LIPIcs.CCC.2024.32,
  author =	{Cheng, Kuan and Wang, Yichuan},
  title =	{{BPL ⊆ L-AC¹}},
  booktitle =	{39th Computational Complexity Conference (CCC 2024)},
  pages =	{32:1--32:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-331-7},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{300},
  editor =	{Santhanam, Rahul},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.32},
  URN =		{urn:nbn:de:0030-drops-204282},
  doi =		{10.4230/LIPIcs.CCC.2024.32},
  annote =	{Keywords: Randomized Space Complexity, Circuit Complexity, Derandomization}
}

Document

DOI: 10.4230/LIPIcs.CCC.2021.22

Error Reduction for Weighted PRGs Against Read Once Branching Programs

Authors: Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, and Amnon Ta-Shma

Published in: LIPIcs, Volume 200, 36th Computational Complexity Conference (CCC 2021)

Abstract

Weighted pseudorandom generators (WPRGs), introduced by Braverman, Cohen and Garg [Braverman et al., 2020], are a generalization of pseudorandom generators (PRGs) in which arbitrary real weights are considered, rather than a probability mass. Braverman et al. constructed WPRGs against read once branching programs (ROBPs) with near-optimal dependence on the error parameter. Chattopadhyay and Liao [Eshan Chattopadhyay and Jyun-Jie Liao, 2020] somewhat simplified the technically involved BCG construction, also obtaining some improvement in parameters. In this work we devise an error reduction procedure for PRGs against ROBPs. More precisely, our procedure transforms any PRG against length n width w ROBP with error 1/poly(n) having seed length s to a WPRG with seed length s + O(logw/(ε) ⋅ log log1/(ε)). By instantiating our procedure with Nisan’s PRG [Noam Nisan, 1992] we obtain a WPRG with seed length O(log{n} ⋅ log(nw) + logw/(ε) ⋅ log log 1/(ε)). This improves upon [Braverman et al., 2020] and is incomparable with [Eshan Chattopadhyay and Jyun-Jie Liao, 2020]. Our construction is significantly simpler on the technical side and is conceptually cleaner. Another advantage of our construction is its low space complexity O(log{nw})+poly(log log1/(ε)) which is logarithmic in n for interesting values of the error parameter ε. Previous constructions (like [Braverman et al., 2020; Eshan Chattopadhyay and Jyun-Jie Liao, 2020]) specify the seed length but not the space complexity, though it is plausible they can also achieve such (or close) space complexity.

Cite as

Gil Cohen, Dean Doron, Oren Renard, Ori Sberlo, and Amnon Ta-Shma. Error Reduction for Weighted PRGs Against Read Once Branching Programs. In 36th Computational Complexity Conference (CCC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 200, pp. 22:1-22:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{cohen_et_al:LIPIcs.CCC.2021.22,
  author =	{Cohen, Gil and Doron, Dean and Renard, Oren and Sberlo, Ori and Ta-Shma, Amnon},
  title =	{{Error Reduction for Weighted PRGs Against Read Once Branching Programs}},
  booktitle =	{36th Computational Complexity Conference (CCC 2021)},
  pages =	{22:1--22:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-193-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{200},
  editor =	{Kabanets, Valentine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2021.22},
  URN =		{urn:nbn:de:0030-drops-142963},
  doi =		{10.4230/LIPIcs.CCC.2021.22},
  annote =	{Keywords: Pseudorandom generators, Read once branching programs, Space-bounded computation}
}

Refine by Author
1 Cheng, Kuan
1 Cohen, Gil
1 Doron, Dean
1 Pyne, Edward
1 Renard, Oren
Show More...

Refine by Classification
3 Theory of computation → Pseudorandomness and derandomization
1 Theory of computation → Computational complexity and cryptography

Refine by Keyword
1 Catalytic computation
1 Circuit Complexity
1 Derandomization
1 Pseudorandom generators
1 Randomized Space Complexity
Show More...

Refine by Type
3 document

Refine by Publication Year
2 2024
1 2021