Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data. A simulation from public publication records: the people listed were not invited and did not agree to review.
? Tutorial for this page

Alon Dermer

dblp:428/9246 · DBLP profile ↗
← Back
1ranked-venue papers
1as first author
1since 2021 · last 2026
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 1 · 1 first-author · 1 since 2021

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Computational complexity · 100%

Topics — the 4 heaviest of 4, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Computational complexity
circuit complexity
1.012026
Multiplicative Pseudorandom Generators for Nondeterministic Circuits · CCC 2026
Computational complexity › derandomization
hardness versus randomness
1.012026
Multiplicative Pseudorandom Generators for Nondeterministic Circuits · CCC 2026
Computational complexity › pseudorandomness
pseudorandom generators
1.012026
Multiplicative Pseudorandom Generators for Nondeterministic Circuits · CCC 2026
Computational complexity
pseudorandomness
1.012026
Multiplicative Pseudorandom Generators for Nondeterministic Circuits · CCC 2026
YearPublicationVenuePosition
2026 Multiplicative Pseudorandom Generators for Nondeterministic Circuits
abstract
The hardness vs. randomness paradigm aims to construct pseudorandom generators (PRGs) based on complexity theoretic hardness assumptions. A seminal result in this area is a PRG construction by [N. Nisan and A. Wigderson, 1994; R. Impagliazzo and A. Wigderson, 1997]. A sequence of works [A. Klivans and D. van Melkebeek, 2002; R. Shaltiel and C. Umans, 2005; C. Umans, 2003; R. Shaltiel and C. Umans, 2006] generalized the result of [N. Nisan and A. Wigderson, 1994; R. Impagliazzo and A. Wigderson, 1997] to nondeterministic circuits, and showed that if E = DTIME(2^{O(n)}) requires nondeterministic circuits of size 2^{Ω(n)}, then for every sufficiently large s, and every ε ≥ 1/s, there is an ε-PRG G:{0,1}^{r = O(log s + log 1/(ε))} → {0,1}^s that runs in time poly(s), and fools size s nondeterministic circuits. In particular, for every size s nondeterministic circuit C, Pr[C(G(U_r)) = 1] ≤ Pr[C(U_s) = 1] + ε. Applebaum et al. [B. Applebaum et al., 2015] showed that "black-box techniques" cannot achieve such results for ε = s^{-ω(1)}. In order to circumvent this problem, Artemenko et al. [S. Artemenko et al., 2016] suggested a "multiplicative" version of PRGs, which requires that: Pr[C(G(U_r)) = 1] ≤ 2 ⋅ Pr[C(U_s) = 1] + ε. This still gives that Pr[C(G(U_r)) = 1] is very small, if Pr[C(U_s) = 1] is very small, and is therefore suitable for applications that only require this consequence. [S. Artemenko et al., 2016] constructed such multiplicative PRGs for ε = s^{-ω(1)} (based on very strong hardness assumptions). In this paper, we give an optimal construction of multiplicative PRGs for nondeterministic circuits. More specifically, under the same hardness assumption used for (standard) PRGs for nondeterministic circuits, we show that for every ε ≥ 1/(2^{s)}, there is a multiplicative PRG G:{0,1}^{r = O(log s + log 1/(ε))} → {0,1}^s that runs in time poly(s) and fools size s nondeterministic circuits. This gives the optimal seed length under a hardness assumption that is necessary, and provides improvements in several applications of multiplicative PRGs. Our result improves upon the previous multiplicative PRG construction of [S. Artemenko et al., 2016], which uses a stronger hardness assumption against Σ₃-circuits, and where the seed length is the suboptimal r = O(log s) + O(log 1/(ε))². Our result also improves upon the recent multiplicative PRG of Shaltiel [R. Shaltiel, 2025] that only achieves very small stretch (the output length in [R. Shaltiel, 2025] is less than twice the seed length). Our PRG construction borrows ideas from the recent "low stretch" PRG of Shaltiel [R. Shaltiel, 2025], and the (standard) PRG construction of Shaltiel and Umans [R. Shaltiel and C. Umans, 2005]. Loosely speaking, we aim to get the "multiplicativity" of the former, and the "large stretch" of the latter. While both approaches generalize the list-decoding results of Sudan, Trevisan and Vadhan [M. Sudan et al., 2001], the two results are tailored to two very different parameter regimes, and we introduce several new ideas to make the two approaches co-exist.
Alon Dermer, Ronen Shaltiel
CCC1