Rocco A. Servedio

ORCID

Publication Activity (10 Years)

Years Active: 1999-2024
Publications (10 Years): 106

Top Venues

CoRR

SODA

STOC

Electron. Colloquium Comput. Complex.

Publications

Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
Testing Intersecting and Union-Closed Families. ITCS (2024)
Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas. SODA (2024)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio
Trace reconstruction from local statistical queries. CoRR (2024)
Anindya De, Huan Li, Shivam Nadimpalli, Rocco A. Servedio
Detecting Low-Degree Truncation. CoRR (2024)
Xi Chen, Shivam Nadimpalli, Tim Randolph, Rocco A. Servedio, Or Zamir
Testing Sumsets is Hard. CoRR (2024)
Anindya De, Huan Li, Shivam Nadimpalli, Rocco A. Servedio
Detecting Low-Degree Truncation. STOC (2024)
Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio
/ poly(n). APPROX/RANDOM (2023)
Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
Testing Intersecting and Union-Closed Families. CoRR (2023)
Ryan O'Donnell, Rocco A. Servedio, Pedro Paredes
Explicit orthogonal and unitary designs. CoRR (2023)
Anindya De, Shivam Nadimpalli, Rocco A. Servedio
Testing Convex Truncation. SODA (2023)
Ryan O'Donnell, Rocco A. Servedio, Pedro Paredes
Explicit orthogonal and unitary designs. FOCS (2023)
Anindya De, Shivam Nadimpalli, Rocco A. Servedio
Gaussian Approximation of Convex Sets by Intersections of Halfspaces. CoRR (2023)
Xi Chen, Anindya De, Yuhao Li, Shivam Nadimpalli, Rocco A. Servedio
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas. CoRR (2023)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
Approximate Trace Reconstruction from a Single Trace. SODA (2023)
Anindya De, Shivam Nadimpalli, Rocco A. Servedio
Testing Convex Truncation. CoRR (2023)
Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio
/poly(n). CoRR (2023)
Rocco A. Servedio, Li-Yang Tan
Improved Pseudorandom Generators from Pseudorandom Multi-switching Lemmas. Theory Comput. 18 (2022)
Daniel Hsu, Clayton Sanford, Rocco A. Servedio, Emmanouil-Vasileios Vlatakis-Gkaragkounis
Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals. CoRR (2022)
Philip M. Long, Rocco A. Servedio
The Perils of Being Unhinged: On the Accuracy of Classifiers Minimizing a Noise-Robust Convex Loss. Neural Comput. 34 (6) (2022)
Daniel J. Hsu, Clayton Hendrick Sanford, Rocco A. Servedio, Emmanouil-Vasileios Vlatakis-Gkaragkounis
Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals. COLT (2022)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
Fooling Polytopes. J. ACM 69 (2) (2022)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
Approximate Trace Reconstruction from a Single Trace. CoRR (2022)
Anindya De, Shivam Nadimpalli, Rocco A. Servedio
Approximating Sumset Size. SODA (2022)
Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun
A Lower Bound on Cycle-Finding in Sparse Digraphs. ACM Trans. Algorithms 18 (4) (2022)
Anindya De, Shivam Nadimpalli, Rocco A. Servedio
Convex Influences. ITCS (2022)
Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio
Average-Case Subset Balancing Problems. SODA (2022)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces. SODA (2022)
Anindya De, Ryan O'Donnell, Rocco A. Servedio
Learning sparse mixtures of permutations from noisy information. COLT (2021)
Anindya De, Shivam Nadimpalli, Rocco A. Servedio
Convex Influences. CoRR (2021)
Anindya De, Shivam Nadimpalli, Rocco A. Servedio
Approximating Sumset Size. CoRR (2021)
Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola
-Polynomials and Applications. APPROX-RANDOM (2021)
Anindya De, Rocco A. Servedio
Weak learning convex sets under normal distributions. COLT (2021)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces. CoRR (2021)
Xi Chen, Yaonan Jin, Tim Randolph, Rocco A. Servedio
Average-Case Subset Balancing Problems. CoRR (2021)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
Polynomial-time trace reconstruction in the smoothed complexity model. SODA (2021)
Daniel Hsu, Clayton Sanford, Rocco A. Servedio, Emmanouil-Vasileios Vlatakis-Gkaragkounis
On the Approximation Power of Two-Layer Networks of Random ReLUs. CoRR (2021)
Daniel Hsu, Clayton H. Sanford, Rocco A. Servedio, Emmanouil-Vasileios Vlatakis-Gkaragkounis
On the Approximation Power of Two-Layer Networks of Random ReLUs. COLT (2021)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan, Daniel Kane
Fooling Gaussian PTFs via Local Hyperconcentration. CoRR (2021)
Huck Bennett, Anindya De, Rocco A. Servedio, Emmanouil-Vasileios Vlatakis-Gkaragkounis
Reconstructing weighted voting schemes from partial information about their power indices. COLT (2021)
Rocco A. Servedio, Li-Yang Tan
Deterministic Approximate Counting of Polynomial Threshold Functions via a Derandomized Regularity Lemma. APPROX-RANDOM (2021)
Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola
Fourier growth of structured $\mathbb{F}_2$-polynomials and applications. Electron. Colloquium Comput. Complex. 28 (2021)
Anindya De, Shivam Nadimpalli, Rocco A. Servedio
Quantitative Correlation Inequalities via Semigroup Interpolation. ITCS (2021)
Jaroslaw Blasiok, Peter Ivanov, Yaonan Jin, Chin Ho Lee, Rocco A. Servedio, Emanuele Viola
Fourier growth of structured $\mathbb{F}_2$-polynomials and applications. CoRR (2021)
Philip M. Long, Rocco A. Servedio
The perils of being unhinged: On the accuracy of classifiers minimizing a noise-robust convex loss. CoRR (2021)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
Polynomial-Time Trace Reconstruction in the Low Deletion Rate Regime. ITCS (2021)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
Polynomial-time trace reconstruction in the low deletion rate regime. CoRR (2020)
Xi Chen, Anindya De, Chin Ho Lee, Rocco A. Servedio, Sandip Sinha
Polynomial-time trace reconstruction in the smoothed complexity model. CoRR (2020)
Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun
A Lower Bound on Cycle-Finding in Sparse Digraphs. SODA (2020)
Anindya De, Ryan O'Donnell, Rocco A. Servedio
Sharp Bounds for Population Recovery. Theory Comput. 16 (2020)
Xue Chen, Anindya De, Rocco A. Servedio
Testing noisy linear functions for sparsity. STOC (2020)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
Fooling Gaussian PTFs via local hyperconcentration. STOC (2020)
Clément L. Canonne, Anindya De, Rocco A. Servedio
Learning from satisfying assignments under continuous distributions. SODA (2020)
Anindya De, Shivam Nadimpalli, Rocco A. Servedio
Quantitative Correlation Inequalities via Semigroup Interpolation. CoRR (2020)
Huck Bennett, Anindya De, Rocco A. Servedio, Emmanouil-Vasileios Vlatakis-Gkaragkounis
Reconstructing weighted voting schemes from partial information about their power indices. CoRR (2020)
Xi Chen, Tim Randolph, Rocco A. Servedio, Timothy Sun
A Lower Bound on Cycle-Finding in Sparse Digraphs. CoRR (2019)
Anindya De, Rocco A. Servedio
Kruskal-Katona for convex sets, with applications. CoRR (2019)
Frank Ban, Xi Chen, Rocco A. Servedio, Sandip Sinha
Efficient Average-Case Population Recovery in the Presence of Insertions and Deletions. APPROX-RANDOM (2019)
Rocco A. Servedio, Li-Yang Tan
Pseudorandomness for read-k DNF formulas. SODA (2019)
Clément L. Canonne, Anindya De, Rocco A. Servedio
Learning from satisfying assignments under continuous distributions. CoRR (2019)
Eshan Chattopadhyay, Anindya De, Rocco A. Servedio
Simple and Efficient Pseudorandom Generators from Gaussian Processes. Computational Complexity Conference (2019)
Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha
Beyond trace reconstruction: Population recovery from the deletion channel. CoRR (2019)
Xue Chen, Anindya De, Rocco A. Servedio
Testing noisy linear functions for sparsity. CoRR (2019)
Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie
Distribution-free Junta Testing. ACM Trans. Algorithms 15 (1) (2019)
Frank Ban, Xi Chen, Adam Freilich, Rocco A. Servedio, Sandip Sinha
Beyond Trace Reconstruction: Population Recovery from the Deletion Channel. FOCS (2019)
Rocco A. Servedio, Li-Yang Tan
Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas. APPROX-RANDOM (2019)
Anindya De, Philip M. Long, Rocco A. Servedio
Density Estimation for Shift-Invariant Multidimensional Distributions. ITCS (2019)
Frank Ban, Xi Chen, Rocco A. Servedio, Sandip Sinha
Efficient average-case population recovery in the presence of insertions and deletions. CoRR (2019)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
Fooling polytopes. STOC (2019)
Anindya De, Philip M. Long, Rocco A. Servedio
Density estimation for shift-invariant multidimensional distributions. CoRR (2018)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
Settling the Query Complexity of Non-adaptive Junta Testing. J. ACM 65 (6) (2018)
Anindya De, Philip M. Long, Rocco A. Servedio
Learning Sums of Independent Random Variables with Sparse Collective Support. FOCS (2018)
Rocco A. Servedio, Li-Yang Tan
Deterministic search for CNF satisfying assignments in almost polynomial time. CoRR (2018)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
Fooling Polytopes. Electron. Colloquium Comput. Complex. 25 (2018)
Xi Chen, Zhengyang Liu, Rocco A. Servedio, Ying Sheng, Jinyu Xie
Distribution-free Junta Testing. CoRR (2018)
Anindya De, Philip M. Long, Rocco A. Servedio
Learning Sums of Independent Random Variables with Sparse Collective Support. CoRR (2018)
Ryan O'Donnell, Rocco A. Servedio, Li-Yang Tan
Fooling Polytopes. CoRR (2018)
Rocco A. Servedio, Li-Yang Tan
Luby-Veličković-Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits. CoRR (2018)
Zhengyang Liu, Xi Chen, Rocco A. Servedio, Ying Sheng, Jinyu Xie
Distribution-free junta testing. STOC (2018)
Rocco A. Servedio, Li-Yang Tan
Improved pseudorandom generators from pseudorandom multi-switching lemmas. CoRR (2018)
Anindya De, Ryan O'Donnell, Rocco A. Servedio
Learning sparse mixtures of rankings from noisy information. CoRR (2018)
Rocco A. Servedio, Li-Yang Tan
Luby-Velickovic-Wigderson Revisited: Improved Correlation Bounds and Pseudorandom Generators for Depth-Two Circuits. APPROX-RANDOM (2018)
Eshan Chattopadhyay, Anindya De, Rocco A. Servedio
Simple and efficient pseudorandom generators from Gaussian processes. Electron. Colloquium Comput. Complex. 25 (2018)
Anindya De, Ilias Diakonikolas, Rocco A. Servedio
The Inverse Shapley value problem. Games Econ. Behav. 105 (2017)
Xi Chen, Adam Freilich, Rocco A. Servedio, Timothy Sun
Sample-Based High-Dimensional Convexity Testing. APPROX-RANDOM (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
Settling the query complexity of non-adaptive junta testing. CoRR (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
Settling the query complexity of non-adaptive junta testing. Electron. Colloquium Comput. Complex. 24 (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie
Settling the Query Complexity of Non-Adaptive Junta Testing. Computational Complexity Conference (2017)
Anindya De, Ryan O'Donnell, Rocco A. Servedio
Sharp bounds for population recovery. CoRR (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten
Adaptivity is exponentially powerful for testing monotonicity of halfspaces. CoRR (2017)
Rocco A. Servedio, Li-Yang Tan
Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time. FOCS (2017)
Xi Chen, Igor Carboni Oliveira, Rocco A. Servedio
Addition is exponentially harder than counting for shallow monotone circuits. STOC (2017)
Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten
Adaptivity Is Exponentially Powerful for Testing Monotonicity of Halfspaces. APPROX-RANDOM (2017)
Rocco A. Servedio, Li-Yang Tan
What Circuit Classes Can Be Learned with Non-Trivial Savings?. ITCS (2017)
Xi Chen, Adam Freilich, Rocco A. Servedio, Timothy Sun
Sample-based high-dimensional convexity testing. CoRR (2017)
Rocco A. Servedio, Li-Yang Tan
Fooling intersections of low-weight halfspaces. CoRR (2017)
Johan Håstad, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
An Average-Case Depth Hierarchy Theorem for Boolean Circuits. J. ACM 64 (5) (2017)
Rocco A. Servedio, Li-Yang Tan
Fooling Intersections of Low-Weight Halfspaces. FOCS (2017)
Anindya De, Ryan O'Donnell, Rocco A. Servedio
Optimal mean-based algorithms for trace reconstruction. STOC (2017)
Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan
Poly-logarithmic Frege depth lower bounds via an expander switching lemma. STOC (2016)
Anindya De, Ilias Diakonikolas, Rocco A. Servedio
A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry. SIAM J. Discret. Math. 30 (2) (2016)

Rocco A. Servedio.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Rocco A. Servedio