1 citations · 2 across the 3 of their papers we have counts for
4 papers
Approximate degree, secret sharing, and concentration phenomena
Andrej Bogdanov, Nikhil S. Mande, Justin Thaler +1
The -approximate degree of a Boolean function is the least degree of a real-valued polynomial that approximates pointwise to error . The approximate degree…
Complete Classification of Generalized Santha-Vazirani Sources
Salman Beigi, Andrej Bogdanov, Omid Etesami +1
Let be a finite alphabet and be a finite set of distributions over . A Generalized Santha-Vazirani (GSV) source of type $(\mathcal{F}, \mat…
Sparse extractor families for all the entropy
Andrej Bogdanov, Siyao Guo
We consider the problem of extracting entropy by sparse transformations, namely functions with a small number of overall input-output dependencies. In contrast to previous works, w…
A better tester for bipartiteness?
Andrej Bogdanov, Fan Li
Alon and Krivelevich (SIAM J. Discrete Math. 15(2): 211-227 (2002)) show that if a graph is ε-far from bipartite, then the subgraph induced by a random subset of O(1/ε) vertices is…