Sotabase

Career

· Associate Professor in the Department of Computer Science, Purdue University2012–

Publications (98)

Statistical algorithms and a lower bound for detecting planted cliques
Symposium on the Theory of Computing · 2012
236
cited
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science · 2004
138
cited
A Unified Framework for Testing Linear-Invariant Properties
IEEE Annual Symposium on Foundations of Computer Science · 2010
59
cited
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques · 2010
44
cited
Nearly optimal sparse group testing
Allerton Conference on Communication, Control, and Computing · 2016
35
cited
Statistical Algorithms and a Lower Bound for Planted Clique
Electron. Colloquium Comput. Complex. · 2012
35
cited
Communication-Efficient Distributed Learning of Discrete Distributions
Neural Information Processing Systems · 2017
33
cited
Succinct Representation of Codes with Applications to Testing
SIAM Journal on Discrete Mathematics · 2009
33
cited
2-Transitivity is Insufficient for Local Testability
2008 23rd Annual IEEE Conference on Computational Complexity · 2008
32
cited
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques · 2018
32
cited
Decodability of group homomorphisms beyond the johnson bound
Electron. Colloquium Comput. Complex. · 2008
24
cited
On Noise-Tolerant Learning of Sparse Parities and Related Problems
International Conference on Algorithmic Learning Theory · 2011
22
cited
List-Decoding Barnes–Wall Lattices
Computational Complexity · 2011
20
cited
Relaxed Locally Correctable Codes in Computationally Bounded Channels
IEEE Transactions on Information Theory · 2018
20
cited
On Sums of Locally Testable Affine Invariant Properties
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques · 2011
19
cited
AC 0 ◦ MOD 2 lower bounds for the Boolean Inner Product
2015
18
cited
Structural Results on Matching Estimation with Applications to Streaming
Algorithmica · 2018
18
cited
AC0∘MOD2 lower bounds for the Boolean Inner Product
Journal of computer and system sciences (Print) · 2018
17
cited
How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques · 2022
17
cited
Local Decoding and Testing for Homomorphisms
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques · 2006
15
cited
Sotabase
Elena Grigorescu | Researcher Profile | Sotabase | Sotabase