|
+
PDF
Chat
|
Relative-error monotonicity testing
|
2025
|
Xi Chen
Anindya De
Yizhi Huang
Yuhao Li
Shivam Nadimpalli
Rocco A. Servedio
Tianqi Yang
|
|
+
PDF
Chat
|
Sparsifying Suprema of Gaussian Processes
|
2024
|
Anindya De
Shivam Nadimpalli
Ryan O’Donnell
Rocco A. Servedio
|
|
+
|
Gaussian Approximation of Convex Sets by Intersections of Halfspaces*
|
2024
|
Anindya De
Shivam Nadimpalli
Rocco A. Servedio
|
|
+
PDF
Chat
|
Lower Bounds for Convexity Testing
|
2024
|
Xin Chen
Anindya De
Shivam Nadimpalli
Rocco A. Servedio
Erik Waingarten
|
|
+
PDF
Chat
|
Relative-error monotonicity testing
|
2024
|
Xi Chen
Anindya De
Yizhi Huang
Yuhao Li
Shivam Nadimpalli
Rocco A. Servedio
Tianqi Yang
|
|
+
PDF
Chat
|
Trace reconstruction from local statistical queries
|
2024
|
Xi Chen
Anindya De
Chin Ho Lee
Rocco A. Servedio
|
|
+
|
Detecting Low-Degree Truncation
|
2024
|
Anindya De
Huan Li
Shivam Nadimpalli
Rocco A. Servedio
|
|
+
PDF
Chat
|
Detecting Low-Degree Truncation
|
2024
|
Anindya De
Huan Li
Shivam Nadimpalli
Rocco A. Servedio
|
|
+
PDF
Chat
|
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas
|
2024
|
Xi Chen
Anindya De
Yuhao Li
Shivam Nadimpalli
Rocco A. Servedio
|
|
+
|
Testing Sumsets is Hard
|
2024
|
Xi Chen
Shivam Nadimpalli
Tim Randolph
Rocco A. Servedio
Or Zamir
|
|
+
PDF
Chat
|
Explicit orthogonal and unitary designs
|
2023
|
Ryan O’Donnell
Rocco A. Servedio
Pedro Paredes
|
|
+
PDF
Chat
|
Approximate Trace Reconstruction from a Single Trace
|
2023
|
Xi Chen
Anindya De
Chin Ho Lee
Rocco A. Servedio
Sandip Sinha
|
|
+
PDF
Chat
|
Testing Convex Truncation
|
2023
|
Anindya De
Shivam Nadimpalli
Rocco A. Servedio
|
|
+
|
Subset Sum in Time $2^{n/2} / poly(n)$
|
2023
|
Xi Chen
Yaonan Jin
Tim Randolph
Rocco A. Servedio
|
|
+
|
Testing Convex Truncation
|
2023
|
Anindya De
Shivam Nadimpalli
Rocco A. Servedio
|
|
+
|
Mildly Exponential Lower Bounds on Tolerant Testers for Monotonicity, Unateness, and Juntas
|
2023
|
Xi Chen
Anindya De
Yuhao Li
Shivam Nadimpalli
Rocco A. Servedio
|
|
+
|
Explicit orthogonal and unitary designs
|
2023
|
Ryan O’Donnell
Rocco A. Servedio
Pedro Paredes
|
|
+
|
Gaussian Approximation of Convex Sets by Intersections of Halfspaces
|
2023
|
Anindya De
Shivam Nadimpalli
Rocco A. Servedio
|
|
+
|
Testing Intersecting and Union-Closed Families
|
2023
|
Xi Chen
Anindya De
Yuhao Li
Shivam Nadimpalli
Rocco A. Servedio
|
|
+
PDF
Chat
|
Polynomial-time trace reconstruction in the smoothed complexity model
|
2022
|
Xi Chen
Anindya De
Chin Ho Lee
Rocco A. Servedio
Sandip Sinha
|
|
+
PDF
Chat
|
The Perils of Being Unhinged: On the Accuracy of Classifiers Minimizing a Noise-Robust Convex Loss
|
2022
|
Philip M. Long
Rocco A. Servedio
|
|
+
|
Quantitative correlation inequalities via extremal power series
|
2022
|
Anindya De
Shivam Nadimpalli
Rocco A. Servedio
|
|
+
PDF
Chat
|
A Lower Bound on Cycle-Finding in Sparse Digraphs
|
2022
|
Xi Chen
Tim Randolph
Rocco A. Servedio
Timothy Sun
|
|
+
|
Fooling Polytopes
|
2022
|
Ryan O’Donnell
Rocco A. Servedio
Li-Yang Tan
|
|
+
PDF
Chat
|
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces
|
2022
|
Xi Chen
Anindya De
Chin Ho Lee
Rocco A. Servedio
Sandip Sinha
|
|
+
PDF
Chat
|
Approximating Sumset Size
|
2022
|
Anindya De
Shivam Nadimpalli
Rocco A. Servedio
|
|
+
PDF
Chat
|
Average-Case Subset Balancing Problems
|
2022
|
Xi Chen
Yaonan Jin
Tim Randolph
Rocco A. Servedio
|
|
+
|
Near-Optimal Statistical Query Lower Bounds for Agnostically Learning Intersections of Halfspaces with Gaussian Marginals
|
2022
|
Daniel Hsu
Clayton Sanford
Rocco A. Servedio
Emmanouil-Vasileios Vlatakis-Gkaragkounis
|
|
+
|
Approximate Trace Reconstruction from a Single Trace
|
2022
|
Xi Chen
Anindya De
Chin Ho Lee
Rocco A. Servedio
Sandip Sinha
|
|
+
PDF
Chat
|
The perils of being unhinged: On the accuracy of classifiers minimizing
a noise-robust convex loss
|
2021
|
Philip M. Long
Rocco A. Servedio
|
|
+
|
Convex Influences
|
2021
|
Anindya De
Shivam Nadimpalli
Rocco A. Servedio
|
|
+
|
Fourier growth of structured $\mathbb{F}_2$-polynomials and applications
|
2021
|
Jarosław Błasiok
Peter Ivanov
Yaonan Jin
Chin Ho Lee
Rocco A. Servedio
Emanuele Viola
|
|
+
|
Fourier growth of structured $\mathbb{F}_2$-polynomials and applications
|
2021
|
Jarosław Błasiok
Peter Ivanov
Yaonan Jin
Chin Ho Lee
Rocco A. Servedio
Emanuele Viola
|
|
+
|
Fooling Gaussian PTFs via Local Hyperconcentration
|
2021
|
Ryan O’Donnell
Rocco A. Servedio
Li-Yang Tan
Daniel M. Kane
|
|
+
|
On the Approximation Power of Two-Layer Networks of Random ReLUs
|
2021
|
Daniel Hsu
Clayton Sanford
Rocco A. Servedio
Emmanouil-Vasileios Vlatakis-Gkaragkounis
|
|
+
PDF
Chat
|
Polynomial-time trace reconstruction in the smoothed complexity model
|
2021
|
Xi Chen
Anindya De
Chin Ho Lee
Rocco A. Servedio
Sandip Sinha
|
|
+
|
On the Approximation Power of Two-Layer Networks of Random ReLUs
|
2021
|
Daniel Hsu
Clayton Sanford
Rocco A. Servedio
Emmanouil-Vasileios Vlatakis-Gkaragkounis
|
|
+
|
Approximating Sumset Size
|
2021
|
Anindya De
Shivam Nadimpalli
Rocco A. Servedio
|
|
+
|
Fourier Growth of Structured 𝔽 2 -Polynomials and Applications.
|
2021
|
Jarosław Błasiok
Peter Ivanov
Yaonan Jin
Chin Ho Lee
Rocco A. Servedio
Emanuele Viola
|
|
+
|
Average-Case Subset Balancing Problems
|
2021
|
Xi Chen
Yaonan Jin
Tim Randolph
Rocco A. Servedio
|
|
+
|
The perils of being unhinged: On the accuracy of classifiers minimizing a noise-robust convex loss
|
2021
|
Philip M. Long
Rocco A. Servedio
|
|
+
|
Fourier growth of structured $\mathbb{F}_2$-polynomials and applications
|
2021
|
Jarosław Błasiok
Ivanov Pa
Yaonan Jin
Chin Ho Lee
Rocco A. Servedio
Emanuele Viola
|
|
+
|
Fooling Gaussian PTFs via Local Hyperconcentration
|
2021
|
Ryan O’Donnell
Rocco A. Servedio
Li-Yang Tan
Daniel M. Kane
|
|
+
|
Convex Influences
|
2021
|
Anindya De
Shivam Nadimpalli
Rocco A. Servedio
|
|
+
|
Near-Optimal Average-Case Approximate Trace Reconstruction from Few Traces
|
2021
|
Xi Chen
Anindya De
Chin Ho Lee
Rocco A. Servedio
Sandip Sinha
|
|
+
|
Reconstructing weighted voting schemes from partial information about their power indices
|
2020
|
Huck Bennett
Anindya De
Rocco A. Servedio
Emmanouil-Vasileios Vlatakis-Gkaragkounis
|
|
+
PDF
Chat
|
Testing noisy linear functions for sparsity
|
2020
|
Xue Chen
Anindya De
Rocco A. Servedio
|
|
+
|
Fooling Gaussian PTFs via local hyperconcentration
|
2020
|
Ryan O’Donnell
Rocco A. Servedio
Li-Yang Tan
|
|
+
|
Polynomial-time trace reconstruction in the smoothed complexity model
|
2020
|
Xi Chen
Anindya De
Chin Ho Lee
Rocco A. Servedio
Sandip Sinha
|
|
+
|
Polynomial-time trace reconstruction in the low deletion rate regime
|
2020
|
Xi Chen
Anindya De
Chin Ho Lee
Rocco A. Servedio
Sandip Sinha
|
|
+
|
Quantitative Correlation Inequalities via Semigroup Interpolation
|
2020
|
Anindya De
Shivam Nadimpalli
Rocco A. Servedio
|
|
+
|
Reconstructing weighted voting schemes from partial information about their power indices
|
2020
|
Huck Bennett
Anindya De
Rocco A. Servedio
Emmanouil-Vasileios Vlatakis-Gkaragkounis
|
|
+
PDF
Chat
|
A Lower Bound on Cycle-Finding in Sparse Digraphs
|
2019
|
Xi Chen
Tim Randolph
Rocco A. Servedio
Timothy Sun
|
|
+
PDF
Chat
|
Learning from satisfying assignments under continuous distributions
|
2019
|
Clément L. Canonne
Anindya De
Rocco A. Servedio
|
|
+
PDF
Chat
|
Beyond Trace Reconstruction: Population Recovery from the Deletion Channel
|
2019
|
Frank Ban
Xi Chen
Adam Freilich
Rocco A. Servedio
Sandip Sinha
|
|
+
|
Kruskal-Katona for convex sets, with applications.
|
2019
|
Anindya De
Rocco A. Servedio
|
|
+
|
Efficient average-case population recovery in the presence of insertions and deletions
|
2019
|
Frank Ban
Xi Chen
Rocco A. Servedio
Sandip Sinha
|
|
+
|
Learning from satisfying assignments under continuous distributions
|
2019
|
Clément L. Canonne
Anindya De
Rocco A. Servedio
|
|
+
PDF
Chat
|
Optimal mean-based algorithms for trace reconstruction
|
2019
|
Anindya De
Ryan O’Donnell
Rocco A. Servedio
|
|
+
|
Beyond trace reconstruction: Population recovery from the deletion channel
|
2019
|
Frank Ban
Xi Chen
Adam Freilich
Rocco A. Servedio
Sandip Sinha
|
|
+
|
Efficient average-case population recovery in the presence of insertions and deletions
|
2019
|
Frank Ban
Xi Chen
Rocco A. Servedio
Sandip Sinha
|
|
+
|
A Lower Bound on Cycle-Finding in Sparse Digraphs
|
2019
|
Xi Chen
Tim Randolph
Rocco A. Servedio
Timothy Sun
|
|
+
|
Testing noisy linear functions for sparsity
|
2019
|
Xue Chen
Anindya De
Rocco A. Servedio
|
|
+
|
Kruskal-Katona for convex sets, with applications
|
2019
|
Anindya De
Rocco A. Servedio
|
|
+
|
Learning from satisfying assignments under continuous distributions
|
2019
|
Clément L. Canonne
Anindya De
Rocco A. Servedio
|
|
+
PDF
Chat
|
Settling the Query Complexity of Non-adaptive Junta Testing
|
2018
|
Xi Chen
Rocco A. Servedio
Li-Yang Tan
Erik Waingarten
Jinyu Xie
|
|
+
PDF
Chat
|
Learning Sums of Independent Random Variables with Sparse Collective Support
|
2018
|
Anindya De
Philip M. Long
Rocco A. Servedio
|
|
+
PDF
Chat
|
Distribution-free Junta Testing
|
2018
|
Zhengyang Liu
Xi Chen
Rocco A. Servedio
Ying Sheng
Jinyu Xie
|
|
+
|
Learning Sums of Independent Random Variables with Sparse Collective Support
|
2018
|
Anindya De
Philip M. Long
Rocco A. Servedio
|
|
+
|
Distribution-free junta testing
|
2018
|
Zhengyang Liu
Xi Chen
Rocco A. Servedio
Ying Sheng
Jinyu Xie
|
|
+
|
Luby--Veli\v{c}kovi\'c--Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits
|
2018
|
Rocco A. Servedio
Li-Yang Tan
|
|
+
|
Deterministic search for CNF satisfying assignments in almost polynomial time
|
2018
|
Rocco A. Servedio
Li-Yang Tan
|
|
+
|
Improved pseudorandom generators from pseudorandom multi-switching lemmas
|
2018
|
Rocco A. Servedio
Li-Yang Tan
|
|
+
|
Distribution-free Junta Testing
|
2018
|
Xi Chen
Zhengyang Liu
Rocco A. Servedio
Ying Sheng
Jinyu Xie
|
|
+
|
Learning sparse mixtures of rankings from noisy information
|
2018
|
Anindya De
Ryan O’Donnell
Rocco A. Servedio
|
|
+
|
Density estimation for shift-invariant multidimensional distributions
|
2018
|
Anindya De
Philip M. Long
Rocco A. Servedio
|
|
+
|
Luby--Veličković--Wigderson revisited: Improved correlation bounds and pseudorandom generators for depth-two circuits
|
2018
|
Rocco A. Servedio
Li-Yang Tan
|
|
+
|
Improved Pseudorandom Generators from Pseudorandom Multi-Switching Lemmas.
|
2018
|
Rocco A. Servedio
Li-Yang Tan
|
|
+
|
Learning Sums of Independent Random Variables with Sparse Collective Support
|
2018
|
Anindya De
Philip M. Long
Rocco A. Servedio
|
|
+
|
Fooling Polytopes
|
2018
|
Ryan O’Donnell
Rocco A. Servedio
Li-Yang Tan
|
|
+
PDF
Chat
|
Fooling Intersections of Low-Weight Halfspaces
|
2017
|
Rocco A. Servedio
Li-Yang Tan
|
|
+
PDF
Chat
|
Deterministic Search for CNF Satisfying Assignments in Almost Polynomial Time
|
2017
|
Rocco A. Servedio
Li-Yang Tan
|
|
+
|
A new central limit theorem and decomposition for Gaussian polynomials, with an application to deterministic approximate counting
|
2017
|
Anindya De
Rocco A. Servedio
|
|
+
PDF
Chat
|
An Average-Case Depth Hierarchy Theorem for Boolean Circuits
|
2017
|
Johan HĂĄstad
Benjamin Rossman
Rocco A. Servedio
Li-Yang Tan
|
|
+
PDF
Chat
|
The Inverse Shapley value problem
|
2017
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Optimal mean-based algorithms for trace reconstruction
|
2017
|
Anindya De
Ryan O’Donnell
Rocco A. Servedio
|
|
+
|
Addition is exponentially harder than counting for shallow monotone circuits
|
2017
|
Xi Chen
Igor Carboni Oliveira
Rocco A. Servedio
|
|
+
|
Sharp bounds for population recovery
|
2017
|
Anindya De
Ryan O’Donnell
Rocco A. Servedio
|
|
+
|
Adaptivity is exponentially powerful for testing monotonicity of halfspaces
|
2017
|
Xi Chen
Rocco A. Servedio
Li-Yang Tan
Erik Waingarten
|
|
+
|
Sample-based high-dimensional convexity testing
|
2017
|
Xi Chen
Adam Freilich
Rocco A. Servedio
Timothy Sun
|
|
+
|
Settling the query complexity of non-adaptive junta testing
|
2017
|
Xi Chen
Rocco A. Servedio
Li-Yang Tan
Erik Waingarten
Jinyu Xie
|
|
+
|
Fooling intersections of low-weight halfspaces
|
2017
|
Rocco A. Servedio
Li-Yang Tan
|
|
+
|
Sample-Based High-Dimensional Convexity Testing.
|
2017
|
Xi Chen
Adam Freilich
Rocco A. Servedio
Timothy Sun
|
|
+
|
Near-optimal small-depth lower bounds for small distance connectivity
|
2016
|
Xi Chen
Igor Carboni Oliveira
Rocco A. Servedio
Li-Yang Tan
|
|
+
|
Degree and Sensitivity: tails of two distributions
|
2016
|
Parikshit Gopalan
Rocco A. Servedio
Avishay Tal
Avi Wigderson
|
|
+
PDF
Chat
|
A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry
|
2016
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Degree and Sensitivity: tails of two distributions.
|
2016
|
Parikshit Gopalan
Rocco A. Servedio
Avishay Tal
Avi Wigderson
|
|
+
|
Optimal mean-based algorithms for trace reconstruction
|
2016
|
Anindya De
Ryan O’Donnell
Rocco A. Servedio
|
|
+
|
Degree and Sensitivity: tails of two distributions
|
2016
|
Parikshit Gopalan
Rocco A. Servedio
Avishay Tal
Avi Wigderson
|
|
+
PDF
Chat
|
An Average-Case Depth Hierarchy Theorem for Boolean Circuits
|
2015
|
Benjamin Rossman
Rocco A. Servedio
Li-Yang Tan
|
|
+
PDF
Chat
|
Boolean Function Monotonicity Testing Requires (Almost) n 1/2 Non-adaptive Queries
|
2015
|
Xi Chen
Anindya De
Rocco A. Servedio
Li-Yang Tan
|
|
+
PDF
Chat
|
Learning Poisson Binomial Distributions
|
2015
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
PDF
Chat
|
None
|
2015
|
Ilias Diakonikolas
Ragesh Jaiswal
Rocco A. Servedio
Li-Yang Tan
Andrew Wan
|
|
+
|
Addition is exponentially harder than counting for shallow monotone circuits
|
2015
|
Xi Chen
Igor Carboni Oliveira
Rocco A. Servedio
|
|
+
|
An average-case depth hierarchy theorem for Boolean circuits
|
2015
|
Benjamin Rossman
Rocco A. Servedio
Li-Yang Tan
|
|
+
|
Smooth Boolean functions are easy: efficient algorithms for low-sensitivity functions
|
2015
|
Parikshit Gopalan
Noam Nisan
Rocco A. Servedio
Kunal Talwar
Avi Wigderson
|
|
+
|
Near-optimal small-depth lower bounds for small distance connectivity
|
2015
|
Xi Chen
Igor Carboni Oliveira
Rocco A. Servedio
Li-Yang Tan
|
|
+
PDF
Chat
|
Testing Probability Distributions using Conditional Samples
|
2015
|
Clément L. Canonne
Dana Ron
Rocco A. Servedio
|
|
+
|
Learning circuits with few negations
|
2015
|
Eric Blais
Clément L. Canonne
Igor Carboni Oliveira
Rocco A. Servedio
Li-Yang Tan
|
|
+
|
Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms
|
2014
|
Siu-On Chan
Ilias Diakonikolas
Rocco A. Servedio
Xiaorui Sun
|
|
+
PDF
Chat
|
New Algorithms and Lower Bounds for Monotonicity Testing
|
2014
|
Xi Chen
Rocco A. Servedio
Li-Yang Tan
|
|
+
PDF
Chat
|
Deterministic Approximate Counting for Juntas of Degree-2 Polynomial Threshold Functions
|
2014
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
PDF
Chat
|
Efficient density estimation via piecewise polynomial approximation
|
2014
|
Siu-On Chan
Ilias Diakonikolas
Rocco A. Servedio
Xiaorui Sun
|
|
+
PDF
Chat
|
Efficient deterministic approximate counting for low-degree polynomial threshold functions
|
2014
|
Anindya De
Rocco A. Servedio
|
|
+
PDF
Chat
|
Nearly Optimal Solutions for the Chow Parameters Problem and Low-Weight Approximation of Halfspaces
|
2014
|
Anindya De
Ilias Diakonikolas
Vitaly Feldman
Rocco A. Servedio
|
|
+
|
Learning circuits with few negations
|
2014
|
Eric Blais
Clément L. Canonne
Igor Carboni Oliveira
Rocco A. Servedio
Li-Yang Tan
|
|
+
PDF
Chat
|
None
|
2014
|
Ilias Diakonikolas
Rocco A. Servedio
Li-Yang Tan
Andrew Wan
|
|
+
|
New algorithms and lower bounds for monotonicity testing
|
2014
|
Xi Chen
Rocco A. Servedio
Li-Yang Tan
|
|
+
|
Boolean function monotonicity testing requires (almost) $n^{1/2}$ non-adaptive queries
|
2014
|
Xi Chen
Anindya De
Rocco A. Servedio
Li-Yang Tan
|
|
+
|
Near-Optimal Density Estimation in Near-Linear Time Using Variable-Width Histograms
|
2014
|
Siu On Chan
Ilias Diakonikolas
Rocco A. Servedio
Xiaorui Sun
|
|
+
PDF
Chat
|
A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage
|
2013
|
Constantinos Daskalakis
Anindya De
Ilias Diakonikolas
Ankur Moitra
Rocco A. Servedio
|
|
+
|
Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions
|
2013
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Deterministic Approximate Counting for Degree-2 Polynomial Threshold Functions.
|
2013
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
PDF
Chat
|
Learning mixtures of structured distributions over discrete domains
|
2013
|
Siu-On Chan
Ilias Diakonikolas
Xiaorui Sun
Rocco A. Servedio
|
|
+
PDF
Chat
|
Testing <i>k</i>-Modal Distributions: Optimal Algorithms via Reductions
|
2013
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
Gregory Valiant
Paul Valiant
|
|
+
PDF
Chat
|
A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry
|
2013
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Deterministic Approximate Counting for Degree-$2$ Polynomial Threshold Functions
|
2013
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Deterministic Approximate Counting for Juntas of Degree-$2$ Polynomial Threshold Functions
|
2013
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Efficient deterministic approximate counting for low degree polynomial threshold functions.
|
2013
|
Anindya De
Rocco A. Servedio
|
|
+
|
Efficient Density Estimation via Piecewise Polynomial Approximation
|
2013
|
Siu-On Chan
Ilias Diakonikolas
Rocco A. Servedio
Xiaorui Sun
|
|
+
|
Efficient deterministic approximate counting for low-degree polynomial threshold functions
|
2013
|
Anindya De
Rocco A. Servedio
|
|
+
|
A Polynomial-time Approximation Scheme for Fault-tolerant Distributed Storage
|
2013
|
Constantinos Daskalakis
Anindya De
Ilias Diakonikolas
Ankur Moitra
Rocco A. Servedio
|
|
+
|
The Inverse Shapley Value Problem
|
2012
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Testing probability distributions using conditional samples
|
2012
|
Clément L. Canonne
Dana Ron
Rocco A. Servedio
|
|
+
PDF
Chat
|
Improved Approximation of Linear Threshold Functions
|
2012
|
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
PDF
Chat
|
Nearly optimal solutions for the chow parameters problem and low-weight approximation of halfspaces
|
2012
|
Anindya De
Ilias Diakonikolas
Vitaly Feldman
Rocco A. Servedio
|
|
+
PDF
Chat
|
Learning poisson binomial distributions
|
2012
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
On the Distribution of the Fourier Spectrum of Halfspaces
|
2012
|
Ilias Diakonikolas
Ragesh Jaiswal
Rocco A. Servedio
Li-Yang Tan
Andrew Wan
|
|
+
PDF
Chat
|
Private Data Release via Learning Thresholds
|
2012
|
Moritz Hardt
Guy N. Rothblum
Rocco A. Servedio
|
|
+
PDF
Chat
|
Learning <i>k</i>-Modal Distributions via Testing
|
2012
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
The Inverse Shapley Value Problem
|
2012
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Inverse problems in approximate uniform generation
|
2012
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
PDF
Chat
|
The Inverse Shapley Value Problem
|
2012
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
A robust Khintchine-Kahane
|
2012
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces
|
2012
|
Anindya De
Ilias Diakonikolas
Vitaly Feldman
Rocco A. Servedio
|
|
+
|
A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry
|
2012
|
Anindya De
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Learning mixtures of structured distributions over discrete domains
|
2012
|
Siu-On Chan
Ilias Diakonikolas
Rocco A. Servedio
Xiaorui Sun
|
|
+
|
On the Distribution of the Fourier Spectrum of Halfspaces
|
2012
|
Ilias Diakonikolas
Ragesh Jaiswal
Rocco A. Servedio
Li-Yang Tan
Andrew Wan
|
|
+
|
Testing probability distributions using conditional samples
|
2012
|
Clément L. Canonne
Dana Ron
Rocco A. Servedio
|
|
+
|
Tight Bounds on Proper Equivalence Query Learning of DNF
|
2011
|
Lisa Hellerstein
Devorah Kletenik
Linda Sellie
Rocco A. Servedio
|
|
+
|
Learning Poisson Binomial Distributions
|
2011
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
PDF
Chat
|
Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions
|
2011
|
Ilias Diakonikolas
Ryan O’Donnell
Rocco A. Servedio
Yi Wu
|
|
+
|
Learning transformed product distributions
|
2011
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Tight Bounds on Proper Equivalence Query Learning of DNF
|
2011
|
Lisa Hellerstein
Devorah Kletenik
Linda Sellie
Rocco A. Servedio
|
|
+
|
Learning transformed product distributions
|
2011
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Private Data Release via Learning Thresholds
|
2011
|
Moritz Hardt
Guy N. Rothblum
Rocco A. Servedio
|
|
+
|
Testing $k$-Modal Distributions: Optimal Algorithms via Reductions
|
2011
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
Gregory Valiant
Paul Valiant
|
|
+
|
Learning $k$-Modal Distributions via Testing
|
2011
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Learning Poisson Binomial Distributions
|
2011
|
Constantinos Daskalakis
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
PDF
Chat
|
A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions
|
2010
|
Ilias Diakonikolas
Rocco A. Servedio
Li-Yang Tan
Andrew Wan
|
|
+
|
Hardness Results for Agnostically Learning Low-Degree Polynomial Threshold Functions
|
2010
|
Ilias Diakonikolas
Ryan O’Donnell
Rocco A. Servedio
Yi Wu
|
|
+
PDF
Chat
|
Improved Approximation of Linear Threshold Functions
|
2009
|
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Improved Approximation of Linear Threshold Functions
|
2009
|
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
|
Average sensitivity and noise sensitivity of polynomial threshold functions
|
2009
|
Ilias Diakonikolas
Prasad Raghavendra
Rocco A. Servedio
Li-Yang Tan
|
|
+
|
A regularity lemma, and low-weight approximators, for low-degree polynomial threshold functions
|
2009
|
Ilias Diakonikolas
Rocco A. Servedio
Li-Yang Tan
Andrew Wan
|
|
+
|
Bounded Independence Fools Halfspaces
|
2009
|
Ilias Diakonikolas
Parikshit Gopalan
Ragesh Jaiswal
Rocco A. Servedio
Emanuele Viola
|
|
+
PDF
Chat
|
Computational Complexity, 2009. CCC '09. 24th Annual IEEE Conference on
|
2009
|
Ilias Diakonikolas
Rocco A. Servedio
|
|
+
PDF
Chat
|
Learning unions of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" display="inline" overflow="scroll"><mml:mi>ω</mml:mi><mml:mrow><mml:mo>(</mml:mo><mml:mn>1</mml:mn><mml:mo>)</mml:mo></mml:mrow></mml:math>-dimensional rectangles
|
2008
|
Alp Atıcı
Rocco A. Servedio
|
|
+
PDF
Chat
|
Efficiently Testing Sparse GF(2) Polynomials
|
2008
|
Ilias Diakonikolas
Homin K. Lee
Kevin Matulef
Rocco A. Servedio
Andrew Wan
|
|
+
|
Efficiently Testing Sparse GF(2) Polynomials
|
2008
|
Ilias Diakonikolas
Homin K. Lee
Kevin Matulef
Rocco A. Servedio
Andrew Wan
|
|
+
PDF
Chat
|
Quantum Algorithms for Learning and Testing Juntas
|
2007
|
Alp Atıcı
Rocco A. Servedio
|
|
+
|
PAC Learning Mixtures of Axis-Aligned Gaussians with No Separation Assumption
|
2006
|
Jon Feldman
Ryan O’Donnell
Rocco A. Servedio
|
|
+
PDF
Chat
|
Learning Unions of ω(1)-Dimensional Rectangles
|
2006
|
Alp Atıcı
Rocco A. Servedio
|
|
+
PDF
Chat
|
Improved Bounds on Quantum Learning Algorithms
|
2005
|
Alp Atıcı
Rocco A. Servedio
|
|
+
PDF
Chat
|
Efficiency versus Convergence of Boolean Kernels for On-Line Learning Algorithms
|
2005
|
Roni Khardon
Dan Roth
Rocco A. Servedio
|
|
+
PDF
Chat
|
Computing sparse permanents faster
|
2005
|
Rocco A. Servedio
Andrew Wan
|
|
+
|
Every decision tree has an influential variable
|
2005
|
Ryan O’Donnell
Michael Saks
Oded Schramm
Rocco A. Servedio
|
|
+
|
Toward Attribute Efficient Learning Algorithms
|
2003
|
Adam R. Klivans
Rocco A. Servedio
|
|
+
|
Quantum versus Classical Learnability
|
2000
|
Rocco A. Servedio
Steven J. Gortler
|