19 citations · 26 across the 5 of their papers we have counts for
8 papers
Learning and Testing Variable Partitions
Andrej Bogdanov, Baoxiang Wang
Let be a multivariate function from a product set to an Abelian group . A -partition of with cost is a partition of the set of variables int…
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…
Homomorphic encryption from codes
Andrej Bogdanov, Chin Ho Lee
We propose a new homomorphic encryption scheme based on the hardness of decoding under independent random noise from certain affine families of codes. Unlike in previous lattice-ba…
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…