Andrej Bogdanov

activity

20102020

most citedA better tester for bipartiteness?

1 citations · 2 across the 3 of their papers we have counts for

collaborators

Showing cs.CCShow all

3 papers · 1 filter

cs.CC2019

Approximate degree, secret sharing, and concentration phenomena

Andrej Bogdanov, Nikhil S. Mande, Justin Thaler +1

The $ε$ -approximate degree $d e g_{ε} (f)$ of a Boolean function $f$ is the least degree of a real-valued polynomial that approximates $f$ pointwise to error $ε$ . The approximate degree…

cs.CC2017★ 1 cited

Complete Classification of Generalized Santha-Vazirani Sources

Salman Beigi, Andrej Bogdanov, Omid Etesami +1

Let $F$ be a finite alphabet and $D$ be a finite set of distributions over $F$ . A Generalized Santha-Vazirani (GSV) source of type $(\mathcal{F}, \mat…

cs.CC2012

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…