We propose a new approach to the hardness-to-randomness framework and to the
conjecture. Classical results rely on nonuniform hardness assumptions to construct …

This is a survey of unconditional pseudorandom generators (PRGs). A PRG uses a short,
truly random seed to generate a long," pseudorandom" sequence of bits. To be more …

The leading technical approach in uniform hardness-to-randomness in the last two decades
faced several well-known barriers that caused results to rely on overly strong hardness …

What's new in the world of derandomization? Questions about pseudorandomness and
derandomization have been driving progress in complexity theory for many decades. In this …

The Exponential-Time Hypothesis (ETH) is a strengthening of the P≠ NP conjecture, stating
that 3-SAT on n variables cannot be solved in (uniform) time 2 ε· n, for some. In recent years …

We study deterministic algorithms for computing graph cuts, with focus on two fundamental
problems: balanced sparse cut and $ k $-vertex connectivity for small $ k $($ k= O (\polylog …

The Exponential-Time Hypothesis (ETH) is a strengthening of the 𝒫≠ 𝒩𝒫 conjecture, stating
that 3-SAT on n variables cannot be solved in (uniform) time 2εċ n, for some ε> 0. In recent …

The nascent field of Fine-Grained Complexity Theory has emerged and grown rapidly in the
past decade. By studying “Hardness within P” and the connections of problems computable …

What is the role of randomness in computation? This thesis focuses on the prBPP= prP
conjecture, which asserts that randomness is not crucial for efficiently solving decision …

This dissertation presents several results at the intersection ofcomplexity theory and
algorithm design. Complexity theory aims tolower-bound the amount of computational …