Elena Grigorescu

Generating author description...

All published works

Action	Title	Year	Authors
+ PDF Chat	Multicriteria Spanners -- A New Tool for Network Design	2024	Elena Grigorescu Nithish Kumar Young‐San Lin
+ PDF Chat	Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems	2024	Elena Grigorescu Young‐San Lin Maoyuan Song
+ PDF Chat	Differential privacy and Sublinear time are incompatible sometimes	2024	Jeremiah Blocki Hendrik Fichtenberger Elena Grigorescu Tamalika Mukherjee
+ PDF Chat	On $k$-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction	2024	Kuan Cheng Elena Grigorescu Xin Li Madhu Sudan Minshen Zhu
+ PDF Chat	A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives	2024	Elena Grigorescu Young‐San Lin Maoyuan Song
+ PDF Chat	Directed Buy-at-Bulk Spanners	2024	Elena Grigorescu Nithish Kumar Young‐San Lin
+	On computing discretized Ricci curvatures of graphs: Local algorithms and (localized) fine-grained reductions	2023	Bhaskar DasGupta Elena Grigorescu Tamalika Mukherjee
+	Approximation Algorithms for Directed Weighted Spanners	2023	Elena Grigorescu Nithish Kumar Young‐San Lin
+	On k-Mer-Based and Maximum Likelihood Estimation Algorithms for Trace Reconstruction	2023	Kuan Cheng Elena Grigorescu Xin Li Madhu Sudan Minshen Zhu
+ PDF Chat	Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions	2022	Jeremiah Blocki Kuan Cheng Elena Grigorescu Xin Li Yu Zheng Minshen Zhu
+	Privately Estimating Graph Parameters in Sublinear time	2022	Jeremiah Blocki Elena Grigorescu Tamalika Mukherjee
+	Hardness of Maximum Likelihood Learning of DPPs	2022	Elena Grigorescu Brendan Juba Karl Wimmer Ning Xie
+	On computing Discretized Ricci curvatures of graphs: local algorithms and (localized) fine-grained reductions	2022	Bhaskar DasGupta Elena Grigorescu Tamalika Mukherjee
+	On Relaxed Locally Decodable Codes for Hamming and Insertion-Deletion Errors	2022	Alexander R. Block Jeremiah Blocki Kuan Cheng Elena Grigorescu Xin Li Yu Zheng Minshen Zhu
+	Learning-Augmented Algorithms for Online Linear and Semidefinite Programming	2022	Elena Grigorescu Young‐San Lin Sandeep Silwal Maoyuan Song Samson Zhou
+	How to Make Your Approximation Algorithm Private: A Black-Box Differentially-Private Transformation for Tunable Approximation Algorithms of Functions with Low Sensitivity	2022	Jeremiah Blocki Elena Grigorescu Tamalika Mukherjee Samson Zhou
+ PDF Chat	Differentially-Private Sublinear-Time Clustering	2021	Jeremiah Blocki Elena Grigorescu Tamalika Mukherjee
+ PDF Chat	Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance	2021	Elena Grigorescu Madhu Sudant Minshen Zhu
+ PDF Chat	The Maximum Binary Tree Problem	2021	Karthekeyan Chandrasekaran Elena Grigorescu Gabriel Istrate Shubhang Kulkarni Young-San Lin Minshen Zhu
+	Relaxed Locally Correctable Codes in Computationally Bounded Channels	2021	Jeremiah Blocki Venkata Gandikota Elena Grigorescu Samson Zhou
+	Online Directed Spanners and Steiner Forests	2021	Elena Grigorescu Young‐San Lin Kent Quanrud
+	Fixed-Parameter Algorithms for Longest Heapable Subsequence and Maximum Binary Tree	2021	Karthekeyan Chandrasekaran Elena Grigorescu Gabriel Istrate Shubhang Kulkarni Young‐San Lin Minshen Zhu
+	Differentially-Private Sublinear-Time Clustering	2021	Jeremiah Blocki Elena Grigorescu Tamalika Mukherjee
+	Online Directed Spanners and Steiner Forests	2021	Elena Grigorescu Young‐San Lin Kent Quanrud
+	Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions	2021	Jeremiah Blocki Kuan Cheng Elena Grigorescu Xin Li Yu Zheng Minshen Zhu
+ PDF Chat	Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance	2020	Elena Grigorescu Madhu Sudan Minshen Zhu
+	List Learning with Attribute Noise	2020	Mahdi Cheraghchi Elena Grigorescu Brendan Juba Karl Wimmer Ning Xie
+	Locally Decodable/Correctable Codes for Insertions and Deletions	2020	Alexander R. Block Jeremiah Blocki Elena Grigorescu Shubhang Kulkarni Minshen Zhu
+	Limitations of Mean-Based Algorithms for Trace Reconstruction at Small Distance	2020	Elena Grigorescu Madhu Sudan Minshen Zhu
+ PDF Chat	Periodicity in Data Streams with Wildcards	2019	Funda Ergün Elena Grigorescu Erfan Sadeqi Azer Samson Zhou
+ PDF Chat	Relaxed Locally Correctable Codes in Computationally Bounded Channels	2019	Jeremiah Blocki Venkata Gandikota Elena Grigorescu Samson Zhou
+	Nearly Optimal Sparse Group Testing	2019	Venkata Gandikota Elena Grigorescu Sidharth Jaggi Samson Zhou
+	The Maximum Binary Tree Problem	2019	Karthekeyan Chandrasekaran Elena Grigorescu Gabriel Istrate Shubhang Kulkarni Young‐San Lin Minshen Zhu
+ PDF Chat	Flipping Out with Many Flips: Hardness of Testing $k$-Monotonicity	2019	Elena Grigorescu Akash Kumar Karl Wimmer
+	Periodicity in Data Streams with Wildcards	2018	Funda Ergün Elena Grigorescu Erfan Sadeqi Azer Samson Zhou
+	Relaxed Locally Correctable Codes in Computationally Bounded Channels	2018	Jeremiah Blocki Venkata Gandikota Elena Grigorescu Samson Zhou
+	Nearly Optimal Distinct Elements and Heavy Hitters on Sliding Windows	2018	Vladimir Braverman Elena Grigorescu Harry G. Lang David P. Woodruff Samson Zhou
+ PDF Chat	NP-Hardness of Reed--Solomon Decoding, and the Prouhet--Tarry--Escott Problem	2018	Venkata Gandikota Badih Ghazi Elena Grigorescu
+ PDF Chat	Periodicity in Data Streams with Wildcards	2018	Funda Ergün Elena Grigorescu Erfan Sadeqi Azer Samson Zhou
+	Lattice-based Locality Sensitive Hashing is Optimal	2017	Karthekeyan Chandrasekaran Daniel Dadush Venkata Gandikota Elena Grigorescu
+ PDF Chat	Longest alignment with edits in data streams	2017	Elena Grigorescu Erfan Sadeqi Azer Samson Zhou
+	Flipping out with many flips: hardness of testing k-monotonicity	2017	Elena Grigorescu Akash Kumar Karl Wimmer
+ PDF Chat	List-Decoding Barnes–Wall Lattices	2017	Elena Grigorescu Chris Peikert
+	Nearly Optimal Sparse Group Testing	2017	Venkata Gandikota Elena Grigorescu Sidharth Jaggi Samson Zhou
+	Streaming for Aibohphobes: Longest Palindrome with Mismatches	2017	Elena Grigorescu Erfan Sadeqi Azer Samson Zhou
+	Streaming Periodicity with Mismatches	2017	Funda Ergün Elena Grigorescu Erfan Sadeqi Azer Samson Zhou
+	Longest Alignment with Edits in Data Streams	2017	Elena Grigorescu Erfan Sadeqi Azer Samson Zhou
+	K-Monotonicity is Not Testable on the Hypercube.	2017	Elena Grigorescu Akash Kumar Karl Wimmer
+ PDF Chat	Deciding Orthogonality in Construction-A Lattices	2017	Karthekeyan Chandrasekaran Venkata Gandikota Elena Grigorescu
+	Lattice-based Locality Sensitive Hashing is Optimal	2017	Karthekeyan Chandrasekaran Daniel Dadush Venkata Gandikota Elena Grigorescu
+	Flipping out with many flips: hardness of testing k-monotonicity	2017	Elena Grigorescu Akash Kumar Karl Wimmer
+	NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem	2016	Venkata Gandikota Badih Ghazi Elena Grigorescu
+ PDF Chat	NP-Hardness of Reed-Solomon Decoding and the Prouhet-Tarry-Escott Problem	2016	Venkata Gandikota Badih Ghazi Elena Grigorescu
+	Testing $k$-Monotonicity	2016	Clément L. Canonne Elena Grigorescu Siyao Guo Akash Kumar Karl Wimmer
+ PDF Chat	Nearly optimal sparse group testing	2016	Venkata Gandikota Elena Grigorescu Sidharth Jaggi Samson Zhou
+	Testing $k$-Monotonicity	2016	Clément L. Canonne Elena Grigorescu Siyao Guo Akash Kumar Karl Wimmer
+	Estimating Weighted Matchings in $o(n)$ Space	2016	Elena Grigorescu Morteza Monemizadeh Samson Zhou
+	Local Testing for Membership in Lattices	2016	Karthekeyan Chandrasekaran Mahdi Cheraghchi Venkata Gandikota Elena Grigorescu
+	Streaming Weighted Matchings: Optimal Meets Greedy	2016	Elena Grigorescu Morteza Monemizadeh Samson Zhou
+	Testing $k$-Monotonicity	2016	Clément L. Canonne Elena Grigorescu Siyao Guo Akash Kumar Karl Wimmer
+	NP-Hardness of Reed-Solomon Decoding, and the Prouhet-Tarry-Escott Problem	2016	Venkata Gandikota Badih Ghazi Elena Grigorescu
+	Deciding Orthogonality in Construction-A Lattices	2015	Karthekeyan Chandrasekaran Venkata Gandikota Elena Grigorescu
+	Deciding Orthogonality in Construction-A Lattices	2015	Karthekeyan Chandrasekaran Venkata Gandikota Elena Grigorescu
+ PDF Chat	A unified framework for testing linear‐invariant properties	2013	Arnab Bhattacharyya Elena Grigorescu A. Shapira
+ PDF Chat	Error-Correcting Data Structures	2013	Victor Chen Elena Grigorescu Ronald de Wolf
+	Efficient and error-correcting data structures for membership and polynomial evaluation	2013	Vienna Chen Elena Grigorescu R.M. deWolf
+ PDF Chat	Testing Odd-Cycle-Freeness in Boolean Functions	2012	Arnab Bhattacharyya Elena Grigorescu Prasad Raghavendra A. Shapira
+ PDF Chat	List Decoding Barnes-Wall Lattices	2012	Elena Grigorescu Chris Peikert
+ PDF Chat	Testing Odd-Cycle-Freeness in Boolean Functions	2012	Arnab Bhattacharyya Elena Grigorescu Prasad Raghavendra A. Shapira
+	The Complexity of Statistical Algorithms	2012	Vitaly Feldman Elena Grigorescu Lev Reyzin Santosh Vempala
+	Statistical Algorithms and a Lower Bound for Detecting Planted Clique	2012	Vitaly Feldman Elena Grigorescu Lev Reyzin Santosh Vempala Ying Xiao
+ PDF Chat	Succinct Representation of Codes with Applications to Testing	2012	Elena Grigorescu Tali Kaufman Madhu Sudan
+	List Decoding Barnes-Wall Lattices	2011	Elena Grigorescu Chris Peikert
+	Testing Odd-Cycle-Freeness in Boolean Functions	2011	Arnab Bhattacharyya Elena Grigorescu Prasad Raghavendra A. Shapira
+	List Decoding Barnes-Wall Lattices	2011	Elena Grigorescu Chris Peikert
+	Steiner Transitive-Closure Spanners of d-Dimensional Posets	2010	Piotr Berman Arnab Bhattacharyya Elena Grigorescu Sofya Raskhodnikova David P. Woodruff Grigory Yaroslavtsev
+	A Unified Framework for Testing Linear-Invariant Properties	2010	Arnab Bhattacharyya Elena Grigorescu A. Shapira
+ PDF Chat	A Unified Framework for Testing Linear-Invariant Properties	2010	Arnab Bhattacharyya Elena Grigorescu A. Shapira
+	Separations of Matroid Freeness Properties	2010	Arnab Bhattacharyya Elena Grigorescu Jakob Nordström Ning Xie
+	Steiner Transitive-Closure Spanners of d-Dimensional Posets	2010	Piotr Berman Arnab Bhattacharyya Elena Grigorescu Sofya Raskhodnikova David P. Woodruff Grigory Yaroslavtsev
+	A Unified Framework for Testing Linear-Invariant Properties	2010	Arnab Bhattacharyya Elena Grigorescu A. Shapira
+	Transitive-closure spanners	2009	Arnab Bhattacharyya Elena Grigorescu Kyomin Jung Sofya Raskhodnikova David P. Woodruff
+	Transitive-Closure Spanners	2009	Arnab Bhattacharyya Elena Grigorescu Kyomin Jung Sofya Raskhodnikova David P. Woodruff
+ PDF Chat	Succinct Representation of Codes with Applications to Testing	2009	Elena Grigorescu Tali Kaufman Madhu Sudan
+	Efficient and Error-Correcting Data Structures for Membership and Polynomial Evaluation	2009	Victor Chen Elena Grigorescu Ronald de Wolf
+	Transitive-Closure Spanners	2008	Arnab Bhattacharyya Elena Grigorescu Kyomin Jung Sofya Raskhodnikova David P. Woodruff
+	The insulation sequence of a graph	2003	Elena Grigorescu
+	Decreasing the diameter of cycles	2003	Elena Grigorescu

Common Coauthors

Coauthor	Papers Together
Samson Zhou	18
Venkata Gandikota	16
Arnab Bhattacharyya	13
Jeremiah Blocki	12
Young‐San Lin	10
Minshen Zhu	9
Karl Wimmer	9
Karthekeyan Chandrasekaran	9
Tamalika Mukherjee	7
A. Shapira	7
Akash Kumar	7
Erfan Sadeqi Azer	7
Madhu Sudan	6
David P. Woodruff	6
Sofya Raskhodnikova	5
Shubhang Kulkarni	4
Funda Ergün	4
Chris Peikert	4
Clément L. Canonne	3
Minshen Zhu	3
Maoyuan Song	3
Kuan Cheng	3
Badih Ghazi	3
Gabriel Istrate	3
Nithish Kumar	3
Kyomin Jung	3
Prasad Raghavendra	3
Siyao Guo	3
Sidharth Jaggi	3
Bhaskar DasGupta	2
Brendan Juba	2
Ronald de Wolf	2
Daniel Dadush	2
Yu Zheng	2
Victor Chen	2
Alexander R. Block	2
Lev Reyzin	2
Piotr Berman	2
Kent Quanrud	2
Xin Li	2
Xin Li	2
Kuan Cheng	2
Santosh Vempala	2
Mahdi Cheraghchi	2
Grigory Yaroslavtsev	2
Tali Kaufman	2
Vitaly Feldman	2
Morteza Monemizadeh	2
Yu Zheng	1
Ning Xie	1

Commonly Cited References

Action	Title	Year	Authors	# of times referenced
+	Exponential lower bound for 2-query locally decodable codes via a quantum argument	2003	Iordanis Kerenidis Ronald de Wolf	6
+ PDF Chat	Green's conjecture and testing linear-invariant properties	2009	A. Shapira	6
+	Some Applications of Coding Theory in Computational Complexity	2004	Luca Trevisan	5
+ PDF Chat	High-Rate Locally Correctable and Locally Testable Codes with Sub-Polynomial Query Complexity	2017	Swastik Kopparty Or Meir Noga Ron‐Zewi Shubhangi Saraf	5
+	Efficient Testing of Large Graphs	2000	Noga Alon Eldar Fischer Michael Krivelevich Márió Szegedy	4
+	Prouhet's 1851 Solution of the Tarry-Escott Problem of 1910	1959	E. M. Wright	4
+	A combinatorial proof of the Removal Lemma for Groups	2009	Daniel Kráľ Oriol Serra Lluís Vena	4
+	Space lower bounds for online pattern matching	2012	Raphaël Clifford Markus Jalsenius Ely Porat Benjamin Sach	4
+ PDF Chat	A removal lemma for systems of linear equations over finite fields	2011	Daniel Kráľ Oriol Serra Lluís Vena	4
+	Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams	2016	Paweł Gawrychowski Oleg Merkurev Arseny M. Shur Przemysław Uznański	4
+ PDF Chat	Error-Correcting Data Structures	2013	Victor Chen Elena Grigorescu Ronald de Wolf	4
+ PDF Chat	Sustained Space Complexity	2018	Joël Alwen Jeremiah Blocki Krzysztof Pietrzak	4
+	On the Advantage over Random for Maximum Acyclic Subgraph	2007	Moses Charikar Konstantin Makarychev Yury Maka	4
+	On sparse graphs with dense long paths	1975	P. Erdős Ronald Graham Endre Szemerédi	4
+	A Szemeredi-type regularity lemma in abelian groups	2003	Ben Green	4
+ PDF Chat	Optimal Rate Code Constructions for Computationally Simple Channels	2016	Venkatesan Guruswami Adam C. Smith	4
+ PDF Chat	Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)	2015	Artūrs Bačkurs Piotr Indyk	3
+ PDF Chat	Group Testing With Probabilistic Tests: Theory, Design and Application	2011	Mahdi Cheraghchi Ali Hormati Amin Karbasi Martin Vetterli	3
+	The <i>k</i>-mismatch problem revisited	2015	Raphaël Clifford Allyx Fontaine Ely Porat Benjamin Sach Tatiana Starikovskaya	3
+	Lower bounds for trace reconstruction	2020	Nina Holden Russell Lyons	3
+ PDF Chat	The capacity of adaptive group testing	2013	Leonardo Baldassini Oliver Johnson Matthew Aldridge	3
+ PDF Chat	Trace reconstruction with varying deletion probabilities	2018	Lisa Hartung Nina Holden Yuval Peres	3
+	Optimal hashing-based time-space trade-offs for approximate near neighbors	2017	Alexandr Andoni Thijs Laarhoven Ilya Razenshteyn Erik Waingarten	3
+	Unique Reconstruction of Coded Strings From Multiset Substring Spectra	2019	Ryan Gabrys Olgica Milenković	3
+ PDF Chat	Low-degree tests at large distances	2007	Alex Samorodnitsky	3
+	Streaming Periodicity with Mismatches	2017	Funda Ergün Elena Grigorescu Erfan Sadeqi Azer Samson Zhou	3
+ PDF Chat	The hybrid k-deck problem: Reconstructing sequences from short and long traces	2017	Ryan Gabrys Olgica Milenković	3
+ PDF Chat	Polynomial-time trace reconstruction in the smoothed complexity model	2021	Xi Chen Anindya De Chin Ho Lee Rocco A. Servedio Sandip Sinha	3
+ PDF Chat	New lower bounds for trace reconstruction	2021	Zachary Chase	3
+	Shortcutting Planar Digraphs	1995	Mikkel Thorup	3
+	Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors	2017	Alexandr Andoni Thijs Laarhoven Ilya Razenshteyn Erik Waingarten	3
+	A Szemeredi-type regularity lemma in abelian groups, with applications	2003	Ben Green	3
+ PDF Chat	Trace reconstruction with exp(O(n <sup>1/3</sup> )) samples	2017	Fëdor Nazarov Yuval Peres	3
+ PDF Chat	Nearly optimal sparse group testing	2016	Venkata Gandikota Elena Grigorescu Sidharth Jaggi Samson Zhou	3
+ PDF Chat	Computational investigations of the Prouhet-Tarry-Escott Problem	2002	Peter Borwein Petr Lisoněk Colin Percival	3
+	Near-optimal sparse fourier representations via sampling	2002	Anna C. Gilbert Suvajyoti Guha Piotr Indyk S. Muthukrishnan Michael Strauss	3
+ PDF Chat	Succinct Representation of Codes with Applications to Testing	2009	Elena Grigorescu Tali Kaufman Madhu Sudan	3
+ PDF Chat	Optimal Testing of Reed-Muller Codes	2010	Arnab Bhattacharyya Swastik Kopparty Grant Schoenebeck Madhu Sudan David Zuckerman	3
+	The Ramsey number of a graph with bounded maximum degree	1983	C Chvatál V. Rödl Endre Szemerédi W. T. Trotter	3
+	Generalizations of the removal lemma	2009	Vojtěch Rödl Mathias Schacht	3
+ PDF Chat	Littlewood-type problems on subarcs of the unit circle	1997	Peter Borwein Tamás Erdélyi	3
+ PDF Chat	Streaming K-Mismatch with Error Correcting and Applications	2017	Jakub Radoszewski Tatiana Starikovskaya	3
+ PDF Chat	Maximum-Likelihood Decoding of Reed–Solomon Codes is NP-Hard	2005	Venkatesan Guruswami Alexander Vardy	3
+	The Hardness of Approximating Spanner Problems	2007	Michael Elkin David Peleg	3
+	A simple construction of d-disjunct matrices with certain constant weights	1996	Anthony J. Macula	3
+ PDF Chat	None	2001	Gabriele Nebe Eric M. Rains N. J. A. Sloane	3
+	Analysis of Boolean Functions	2014	Ryan O’Donnell	2
+ PDF Chat	The Algorithmic Aspects of the Regularity Lemma	1994	Noga Alon Richard A. Duke Hanno Lefmann V. Rödl Raphael Yuster	2
+	Introduction to number theory	2009	Luo Hua	2
+ PDF Chat	Approximating Longest Directed Paths and Cycles	2004	Andreas Björklund Thore Husfeldt Sanjeev Khanna	2