Elena Grigorescu

ORCID

Publication Activity (10 Years)

Years Active: 2003-2024
Publications (10 Years): 83

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

APPROX-RANDOM

FSTTCS

Massachusetts Institute of Technology, Cambridge, MA, USA (PHD)

Education History

Massachusetts Institute of Technology, Cambridge, MA, USA

PHD

Publications

Elena Grigorescu, Young-San Lin, Maoyuan Song
A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives. CoRR (2024)
Jeremiah Blocki, Hendrik Fichtenberger, Elena Grigorescu, Tamalika Mukherjee
Differential privacy and Sublinear time are incompatible sometimes. CoRR (2024)
Elena Grigorescu, Nithish Kumar, Young-San Lin
Directed Buy-at-Bulk Spanners. CoRR (2024)
Elena Grigorescu, Nithish Kumar, Young-San Lin
Approximation Algorithms for Directed Weighted Spanners. CoRR (2023)
Bhaskar DasGupta, Elena Grigorescu, Tamalika Mukherjee
On computing discretized Ricci curvatures of graphs: Local algorithms and (localized) fine-grained reductions. Theor. Comput. Sci. 975 (2023)
Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee, Samson Zhou
How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity. APPROX/RANDOM (2023)
Alexander R. Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu
On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors. CCC (2023)
Kuan Cheng, Elena Grigorescu, Xin Li, Madhu Sudan, Minshen Zhu
On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction. CoRR (2023)
Elena Grigorescu, Nithish Kumar, Young-San Lin
Approximation Algorithms for Directed Weighted Spanners. APPROX/RANDOM (2023)
Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu
Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions. FOCS (2022)
Elena Grigorescu, Young-San Lin, Sandeep Silwal, Maoyuan Song, Samson Zhou
Learning-Augmented Algorithms for Online Linear and Semidefinite Programming. NeurIPS (2022)
Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee
Privately Estimating Graph Parameters in Sublinear time. CoRR (2022)
Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee, Samson Zhou
How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity. CoRR (2022)
Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee
Privately Estimating Graph Parameters in Sublinear Time. ICALP (2022)
Elena Grigorescu, Young-San Lin, Sandeep Silwal, Maoyuan Song, Samson Zhou
Learning-Augmented Algorithms for Online Linear and Semidefinite Programming. CoRR (2022)
Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
Hardness of Maximum Likelihood Learning of DPPs. COLT (2022)
Alexander R. Block, Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu
On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors. CoRR (2022)
Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
Hardness of Maximum Likelihood Learning of DPPs. CoRR (2022)
Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
Hardness of Maximum Likelihood Learning of DPPs. Electron. Colloquium Comput. Complex. (2022)
Elena Grigorescu, Madhu Sudan, Minshen Zhu
Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Edit Distance. IEEE Trans. Inf. Theory 68 (10) (2022)
Bhaskar DasGupta, Elena Grigorescu, Tamalika Mukherjee
On computing Ollivier-Ricci curvatures of graphs: fine-grained reductions and local algorithms. CoRR (2022)
Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, Minshen Zhu
Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree. CoRR (2021)
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
List Learning with Attribute Noise. AISTATS (2021)
Elena Grigorescu, Madhu Sudan, Minshen Zhu
Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance. ISIT (2021)
Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, Minshen Zhu
The Maximum Binary Tree Problem. Algorithmica 83 (8) (2021)
Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee
Differentially-Private Sublinear-Time Clustering. ISIT (2021)
Jeremiah Blocki, Venkata Gandikota, Elena Grigorescu, Samson Zhou
Relaxed Locally Correctable Codes in Computationally Bounded Channels. IEEE Trans. Inf. Theory 67 (7) (2021)
Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu
Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions. CoRR (2021)
Elena Grigorescu, Young-San Lin, Kent Quanrud
Online Directed Spanners and Steiner Forests. CoRR (2021)
Elena Grigorescu, Young-San Lin, Kent Quanrud
Online Directed Spanners and Steiner Forests. APPROX-RANDOM (2021)
Jeremiah Blocki, Kuan Cheng, Elena Grigorescu, Xin Li, Yu Zheng, Minshen Zhu
Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions. FOCS (2021)
Jeremiah Blocki, Elena Grigorescu, Tamalika Mukherjee
Differentially-Private Sublinear-Time Clustering. CoRR (2021)
Elena Grigorescu, Madhu Sudan, Minshen Zhu
Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance. CoRR (2020)
Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, Minshen Zhu
The Maximum Binary Tree Problem. ESA (2020)
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
List Learning with Attribute Noise. CoRR (2020)
Alexander R. Block, Jeremiah Blocki, Elena Grigorescu, Shubhang Kulkarni, Minshen Zhu
Locally Decodable/Correctable Codes for Insertions and Deletions. FSTTCS (2020)
Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou
Periodicity in Data Streams with Wildcards. Theory Comput. Syst. 64 (1) (2020)
Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, Minshen Zhu
Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree. IPEC (2020)
Alexander R. Block, Jeremiah Blocki, Elena Grigorescu, Shubhang Kulkarni, Minshen Zhu
Locally Decodable/Correctable Codes for Insertions and Deletions. CoRR (2020)
Marc Bury, Elena Grigorescu, Andrew McGregor, Morteza Monemizadeh, Chris Schwiegelshohn, Sofya Vorotnikova, Samson Zhou
Structural Results on Matching Estimation with Applications to Streaming. Algorithmica 81 (1) (2019)
Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer
Testing k-Monotonicity: The Rise and Fall of Boolean Functions. Theory Comput. 15 (2019)
Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, Minshen Zhu
The Maximum Binary Tree Problem. CoRR (2019)
Elena Grigorescu, Akash Kumar, Karl Wimmer
Flipping Out with Many Flips: Hardness of Testing k-Monotonicity. SIAM J. Discret. Math. 33 (4) (2019)
Jeremiah Blocki, Venkata Gandikota, Elena Grigorescu, Samson Zhou
Relaxed Locally Correctable Codes in Computationally Bounded Channels. ISIT (2019)
Venkata Gandikota, Elena Grigorescu, Sidharth Jaggi, Samson Zhou
Nearly Optimal Sparse Group Testing. IEEE Trans. Inf. Theory 65 (5) (2019)
Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu
Local Testing of Lattices. SIAM J. Discret. Math. 32 (2) (2018)
Karthekeyan Chandrasekaran, Daniel Dadush, Venkata Gandikota, Elena Grigorescu
Lattice-based Locality Sensitive Hashing is Optimal. ITCS (2018)
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
lower bounds for the Boolean Inner Product. J. Comput. Syst. Sci. 97 (2018)
Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, Samson Zhou
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows. APPROX-RANDOM (2018)
Jeremiah Blocki, Venkata Gandikota, Elena Grigorescu, Samson Zhou
Relaxed Locally Correctable Codes in Computationally Bounded Channels. CoRR (2018)
Jeremiah Blocki, Venkata Gandikota, Elena Grigorescu, Samson Zhou
Brief Announcement: Relaxed Locally Correctable Codes in Computationally Bounded Channels. ICALP (2018)
Venkata Gandikota, Badih Ghazi, Elena Grigorescu
NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem. SIAM J. Comput. 47 (4) (2018)
Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou
Periodicity in Data Streams with Wildcards. CSR (2018)
Vladimir Braverman, Elena Grigorescu, Harry Lang, David P. Woodruff, Samson Zhou
Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows. CoRR (2018)
Elena Grigorescu, Akash Kumar, Karl Wimmer
Flipping out with Many Flips: Hardness of Testing k-Monotonicity. APPROX-RANDOM (2018)
Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou
Periodicity in Data Streams with Wildcards. CoRR (2018)
Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou
Streaming Periodicity with Mismatches. APPROX-RANDOM (2017)
Elena Grigorescu, Akash Kumar, Karl Wimmer
K-Monotonicity is Not Testable on the Hypercube. CoRR (2017)
Karthekeyan Chandrasekaran, Venkata Gandikota, Elena Grigorescu
Deciding Orthogonality in Construction-A Lattices. SIAM J. Discret. Math. 31 (2) (2017)
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao
Statistical Algorithms and a Lower Bound for Detecting Planted Cliques. J. ACM 64 (2) (2017)
Venkata Gandikota, Elena Grigorescu, Sidharth Jaggi, Samson Zhou
Nearly Optimal Sparse Group Testing. CoRR (2017)
Funda Ergün, Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou
Streaming Periodicity with Mismatches. CoRR (2017)
Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou
Streaming for Aibohphobes: Longest Palindrome with Mismatches. FSTTCS (2017)
Ilias Diakonikolas, Elena Grigorescu, Jerry Li, Abhiram Natarajan, Krzysztof Onak, Ludwig Schmidt
Communication-Efficient Distributed Learning of Discrete Distributions. NIPS (2017)
Elena Grigorescu, Chris Peikert
List-Decoding Barnes-Wall Lattices. Comput. Complex. 26 (2) (2017)
Karthekeyan Chandrasekaran, Daniel Dadush, Venkata Gandikota, Elena Grigorescu
Lattice-based Locality Sensitive Hashing is Optimal. CoRR (2017)
Venkata Gandikota, Elena Grigorescu, Clayton Thomas, Minshen Zhu
Maximally recoverable codes: The bounded case. Allerton (2017)
Elena Grigorescu, Akash Kumar, Karl Wimmer
K-Monotonicity is Not Testable on the Hypercube. Electron. Colloquium Comput. Complex. 24 (2017)
Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou
Longest alignment with edits in data streams. Allerton (2017)
Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou
Streaming for Aibohphobes: Longest Palindrome with Mismatches. CoRR (2017)
Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer
Testing k-Monotonicity. ITCS (2017)
Elena Grigorescu, Erfan Sadeqi Azer, Samson Zhou
Longest Alignment with Edits in Data Streams. CoRR (2017)
Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer
Testing k-Monotonicity. CoRR (2016)
Venkata Gandikota, Elena Grigorescu, Sidharth Jaggi, Samson Zhou
Nearly optimal sparse group testing. Allerton (2016)
Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu
Local Testing for Membership in Lattices. FSTTCS (2016)
Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu
Local Testing for Membership in Lattices. CoRR (2016)
Clément L. Canonne, Elena Grigorescu, Siyao Guo, Akash Kumar, Karl Wimmer
Testing k-Monotonicity. Electron. Colloquium Comput. Complex. 23 (2016)
Elena Grigorescu, Morteza Monemizadeh, Samson Zhou
Estimating Weighted Matchings in o(n) Space. CoRR (2016)
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
AC^0 o MOD_2 Lower Bounds for the Boolean Inner Product. ICALP (2016)
Karthekeyan Chandrasekaran, Mahdi Cheraghchi, Venkata Gandikota, Elena Grigorescu
Local Testing for Membership in Lattices. Electron. Colloquium Comput. Complex. 23 (2016)
Venkata Gandikota, Badih Ghazi, Elena Grigorescu
NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem. CoRR (2016)
Venkata Gandikota, Badih Ghazi, Elena Grigorescu
NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem. Electron. Colloquium Comput. Complex. 23 (2016)
Venkata Gandikota, Badih Ghazi, Elena Grigorescu
NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem. FOCS (2016)
Karthekeyan Chandrasekaran, Venkata Gandikota, Elena Grigorescu
Deciding Orthogonality in Construction-A Lattices. FSTTCS (2015)
Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira
A unified framework for testing linear-invariant properties. Random Struct. Algorithms 46 (2) (2015)
Venkata Gandikota, Badih Ghazi, Elena Grigorescu
On the NP-hardness of bounded distance decoding of Reed-Solomon codes. ISIT (2015)
Karthekeyan Chandrasekaran, Venkata Gandikota, Elena Grigorescu
Deciding Orthogonality in Construction-A Lattices. CoRR (2015)
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, Ning Xie
lower bounds for the Boolean Inner Product. Electron. Colloquium Comput. Complex. 22 (2015)
Piotr Berman, Arnab Bhattacharyya, Elena Grigorescu, Sofya Raskhodnikova, David P. Woodruff, Grigory Yaroslavtsev
Steiner transitive-closure spanners of low-dimensional posets. Comb. 34 (3) (2014)
Victor Chen, Elena Grigorescu, Ronald de Wolf
Error-Correcting Data Structures. SIAM J. Comput. 42 (1) (2013)
Elena Grigorescu, Karl Wimmer, Ning Xie
Tight Lower Bounds for Testing Linear Isomorphism. Electron. Colloquium Comput. Complex. 20 (2013)
Elena Grigorescu, Karl Wimmer, Ning Xie
Tight Lower Bounds for Testing Linear Isomorphism. APPROX-RANDOM (2013)
Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao
Statistical algorithms and a lower bound for detecting planted cliques. STOC (2013)
Mikhail J. Atallah, Elena Grigorescu, Yi Wu
A lower-variance randomized algorithm for approximate string matching. Inf. Process. Lett. 113 (18) (2013)
Elena Grigorescu, Tali Kaufman, Madhu Sudan
2-Transitivity is Insufficient for Local Testability. Comput. Complex. 22 (1) (2013)
Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners. SIAM J. Discret. Math. 26 (2) (2012)
Elena Grigorescu, Tali Kaufman, Madhu Sudan
Succinct Representation of Codes with Applications to Testing. SIAM J. Discret. Math. 26 (4) (2012)
Arnab Bhattacharyya, Elena Grigorescu, Kyomin Jung, Sofya Raskhodnikova, David P. Woodruff
Transitive-Closure Spanners. SIAM J. Comput. 41 (6) (2012)
Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira
Testing odd-cycle-freeness in Boolean functions. SODA (2012)
Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira
Testing Odd-Cycle-Freeness in Boolean Functions. Comb. Probab. Comput. 21 (6) (2012)

Elena Grigorescu.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Elena Grigorescu