Zobrazeno 1 - 10
of 72
pro vyhledávání: '"Theory of computation → Pseudorandomness and derandomization"'
Autor:
Kumar, Vinayak M.
We initiate the study of generalized AC0 circuits comprised of negations and arbitrary unbounded fan-in gates that only need to be constant over inputs of Hamming weight $\ge k$, which we denote GC0$(k)$. The gate set of this class includes biased LT
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::0c6bc12fb125ead0db7468d3a093fb81
http://arxiv.org/abs/2304.02770
http://arxiv.org/abs/2304.02770
This work initiates the systematic study of explicit distributions that are indistinguishable from a single exponential-size combinatorial object. In this we extend the work of Goldreich, Goldwasser and Nussboim (SICOMP 2010) that focused on the impl
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::13a94d6f848d7e90536f8cf3f18b7f18
http://arxiv.org/abs/2302.12823
http://arxiv.org/abs/2302.12823
Autor:
Chattopadhyay, Eshan, Liao, Jyun-Jie
In a recent work, Gryaznov, Pudlák and Talebanfard (CCC '22) introduced a linear variant of read-once branching programs, with motivations from circuit and proof complexity. Such a read-once linear branching program is a branching program where each
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2357a7597d70877415fa6c48a07df774
Autor:
Doron, Dean, Tell, Roei
Existing proofs that deduce BPL = 𝐋 from circuit lower bounds convert randomized algorithms into deterministic algorithms with large constant overhead in space. We study space-bounded derandomization with minimal footprint, and ask what is the min
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::ba2b37c90c4e9d4fd3202834356578d6
Autor:
Kunisky, Dmitriy, Yu, Xifan
We prove that the degree 4 sum-of-squares (SOS) relaxation of the clique number of the Paley graph on a prime number $p$ of vertices has value at least $\Omega(p^{1/3})$. This is in contrast to the widely believed conjecture that the actual clique nu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6a6be6cd6a2d9729b401c981e9299a14
Autor:
Houen, Jakob Bæk Tejs, Thorup, Mikkel
The \emph{Sparse Johnson-Lindenstrauss Transform} of Kane and Nelson (SODA 2012) provides a linear dimensionality-reducing map $A \in \mathbb{R}^{m \times u}$ in $\ell_2$ that preserves distances up to distortion of $1 + \varepsilon$ with probability
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::48c02619af26cd819dd6d4188f379dd1
Autor:
Liu, Yanyi, Pass, Rafael
A central open problem in complexity theory concerns the question of whether all efficient randomized algorithms can be simulated by efficient deterministic algorithms. The celebrated "hardness v.s. randomness” paradigm pioneered by Blum-Micali (SI
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::78e3107965f77e663cd31d93d1aedcd2
Randomized algorithms and protocols assume the availability of a perfect source of randomness. In real life, however, perfect randomness is rare and is almost never guaranteed. The gap between these two facts motivated much of the work on randomness
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::b0b08a01d1916513be653354254e3711
Many streaming algorithms provide only a high-probability relative approximation. These two relaxations, of allowing approximation and randomization, seem necessary -- for many streaming problems, both relaxations must be employed simultaneously, to
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1b34bca8b1cf867664c8fa13e2c733d5
A fundamental question in computational complexity asks whether probabilistic polynomial-time algorithms can be simulated deterministically with a small overhead in time (the BPP vs. P problem). A corresponding question in the realm of interactive pr
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::73166b3c33a4aef776339133968ddd32