16 citations · 17 across the 15 of their papers we have counts for
Showing cs.CCShow all
3 papers · 1 filter
cs.CC2025
Generalized and Unified Equivalences between Hardness and Pseudoentropy
Lunjia Hu, Salil Vadhan
Pseudoentropy characterizations give quantitatively precise formulations of the relationship between computational hardness and computational randomness. We prove a unified pseudoe…
cs.CC2023
Complexity-Theoretic Implications of Multicalibration
Sílvia Casacuberta, Cynthia Dwork, Salil Vadhan
We present connections between the recent literature on multigroup fairness for prediction algorithms and classical results in computational complexity. Multiaccurate predictors ar…
cs.CC2014★ 16 cited
Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs
Thomas Steinke, Salil Vadhan, Andrew Wan
We present an explicit pseudorandom generator for oblivious, read-once, width- branching programs, which can read their input bits in any order. The generator has seed length $\…