Ronitt Rubinfeld

Ruidi Cao

Edward Pyne

CoRR, 2024

2023

From Big Data Theory to Big Data Practice (Dagstuhl Seminar 23071).

[BibT_eX]

[DOI]

Dagstuhl Reports, February, 2023

Testing Distributional Assumptions of Learning Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

New Partitioning Techniques and Faster Algorithms for Approximate Interval Scheduling.

[BibT_eX]

[DOI]

Spencer Compton

Slobodan Mitrovic

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

Testing Tail Weight of a Distribution Via Hazard Rate.

[BibT_eX]

[DOI]

Kavya Ravichandran

Proceedings of the International Conference on Algorithmic Learning Theory, 2023

2022

Properly learning monotone functions via local reconstruction.

[BibT_eX]

[DOI]

Jane Lange

CoRR, 2022

Exponentially Improving the Complexity of Simulating the Weisfeiler-Lehman Test with Graph Neural Networks.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, 2022

Local Access to Random Walks.

[BibT_eX]

[DOI]

Edward Pyne

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

Triangle and Four Cycle Counting with Predictions in Graph Streams.

[BibT_eX]

[DOI]

Proceedings of the Tenth International Conference on Learning Representations, 2022

Properly learning monotone functions via local correction.

[BibT_eX]

[DOI]

Jane Lange

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

Massively Parallel Algorithms for Small Subgraph Counting.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2022

Online Page Migration with ML Advice.

[BibT_eX]

[DOI]

Frederik Mallmann-Trenn

Slobodan Mitrovic

Proceedings of the International Conference on Artificial Intelligence and Statistics, 2022

2021

Learning-based Support Estimation in Sublinear Time.

[BibT_eX]

[DOI]

Proceedings of the 9th International Conference on Learning Representations, 2021

Rapid Approximate Aggregation with Distribution-Sensitive Interval Guarantees.

[BibT_eX]

[DOI]

Stephen Macke

Ilias Diakonikolas

Aditya G. Parameswaran

Proceedings of the 37th IEEE International Conference on Data Engineering, 2021

Sampling Multiple Edges Efficiently.

[BibT_eX]

[DOI]

Talya Eden

Saleet Mossel

Proceedings of the Approximation, 2021

Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time.

[BibT_eX]

[DOI]

Talya Eden

Proceedings of the Approximation, 2021

2020

Amortized Edge Sampling.

[BibT_eX]

[DOI]

Talya Eden

Saleet Mossel

CoRR, 2020

Parallel Algorithms for Small Subgraph Counting.

[BibT_eX]

[DOI]

CoRR, 2020

Local Algorithms for Sparse Spanning Graphs.

[BibT_eX]

[DOI]

Algorithmica, 2020

Improved Local Computation Algorithm for Set Cover via Sparsification.

[BibT_eX]

[DOI]

Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, 2020

Monotone Probability Distributions over the Boolean Cube Can Be Learned with Sublinear Samples.

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

Local Access to Huge Random Objects Through Partial Sampling.

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Local Computation Algorithms.

[BibT_eX]

[DOI]

Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing, 2019

Private Testing of Distributions via Sample Permutations.

[BibT_eX]

[DOI]

Proceedings of the Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, 2019

Local Computation Algorithms for Spanners.

[BibT_eX]

[DOI]

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Towards Testing Monotonicity of Distributions Over General Posets.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

Testing Mixtures of Discrete Distributions.

[BibT_eX]

[DOI]

Proceedings of the Conference on Learning Theory, 2019

Approximating the Noise Sensitivity of a Monotone Boolean Function.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2019

2018

Sampling Correctors.

[BibT_eX]

[DOI]

Clément L. Canonne

Themis Gouleakis

SIAM J. Comput., 2018

Testing Shape Restrictions of Discrete Distributions.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2018

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover.

[BibT_eX]

[DOI]

CoRR, 2018

Sublinear-Time Algorithms for Counting Star Subgraphs via Edge Sampling.

[BibT_eX]

[DOI]

Algorithmica, 2018

Set Cover in Sub-linear Time.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover.

[BibT_eX]

[DOI]

Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

Differentially Private Identity and Equivalence Testing of Discrete Distributions.

[BibT_eX]

[DOI]

Ilias Diakonikolas

Proceedings of the 35th International Conference on Machine Learning, 2018

2017

I've Seen "Enough": Incrementally Improving Visualizations to Support Rapid Decision Making.

[BibT_eX]

[DOI]

Aditya G. Parameswaran

Proc. VLDB Endow., 2017

Local-Access Generators for Basic Random Graph Models.

[BibT_eX]

[DOI]

CoRR, 2017

Differentially Private Identity and Closeness Testing of Discrete Distributions.

[BibT_eX]

[DOI]

Ilias Diakonikolas

CoRR, 2017

Local Computation Algorithms for Graphs of Non-constant Degrees.

[BibT_eX]

[DOI]

Algorithmica, 2017

Local Computation Algorithms (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Can We Locally Compute Sparse Connected Subgraphs?

[BibT_eX]

[DOI]

Proceedings of the Computer Science - Theory and Applications, 2017

Fractional Set Cover in the Streaming Model.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2017

2016

Linearity Testing/Testing Hadamard Codes.

[BibT_eX]

[DOI]

Sofya Raskhodnikova

Encyclopedia of Algorithms, 2016

A Self-Tester for Linear Functions over the Integers with an Elementary Proof of Correctness.

[BibT_eX]

[DOI]

Sheela Devadas

Theory Comput. Syst., 2016

Sublinear-Time Algorithms for Counting Star Subgraphs with Applications to Join Selectivity Estimation.

[BibT_eX]

[DOI]

Themistoklis Gouleakis

John Peebles

CoRR, 2016

Learning and Testing Junta Distributions.

[BibT_eX]

[DOI]

Eric Blais

Proceedings of the 29th Conference on Learning Theory, 2016

A Local Algorithm for Constructing Spanners in Minor-Free Graphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

Something for (Almost) Nothing: New Advances in Sublinear-Time Algorithms.

[BibT_eX]

[DOI]

Eric Blais

Proceedings of the Handbook of Big Data., 2016

2015

Rapid Sampling for Visualizations with Ordering Guarantees.

[BibT_eX]

[DOI]

Albert Kim

Eric Blais

Aditya G. Parameswaran

Samuel Madden

Proc. VLDB Endow., 2015

Constructing Near Spanning Trees with Few Local Inspections.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Brief Announcement: Local Computation Algorithms for Graphs of Non-Constant Degrees.

[BibT_eX]

[DOI]

Proceedings of the 27th ACM on Symposium on Parallelism in Algorithms and Architectures, 2015

Erratum for: Approximating and Testing k-Histogram Distributions in Sub-linear Time.

[BibT_eX]

[DOI]

Proceedings of the 34th ACM Symposium on Principles of Database Systems, 2015

2014

Testing Similar Means.

[BibT_eX]

[DOI]

SIAM J. Discret. Math., 2014

Testing probability distributions underlying aggregated data.

[BibT_eX]

[DOI]

Clément L. Canonne

Electron. Colloquium Comput. Complex., 2014

2013

Testing Properties of Collections of Distributions.

[BibT_eX]

[DOI]

Theory Comput., 2013

Robust characterizations of k-wise independence over product spaces and related testing results.

[BibT_eX]

[DOI]

Ning Xie

Random Struct. Algorithms, 2013

Testing Closeness of Discrete Distributions.

[BibT_eX]

[DOI]

J. ACM, 2013

Sublinear Algorithms for Approximating String Compressibility.

[BibT_eX]

[DOI]

Algorithmica, 2013

A Simple Online Competitive Adaptation of Lempel-Ziv Compression with Efficient Random Access Support.

[BibT_eX]

[DOI]

Proceedings of the 2013 Data Compression Conference, 2013

Local Reconstructors and Tolerant Testers for Connectivity and Diameter.

[BibT_eX]

[DOI]

Andrea Campagna

Alan Guo

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2013

2012

Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2012

Taming big probability distributions.

[BibT_eX]

[DOI]

XRDS, 2012

A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Space-efficient local computation algorithms.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Approximating and testing k-histogram distributions in sub-linear time.

[BibT_eX]

[DOI]

Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, 2012

2011

Sublinear Time Algorithms.

[BibT_eX]

[DOI]

Asaf Shapira

SIAM J. Discret. Math., 2011

Sublinear Time Algorithms for Earth Mover's Distance.

[BibT_eX]

[DOI]

Theory Comput. Syst., 2011

Approximating and Testing k-Histogram Distributions in Sub-linear time.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2011

Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity

[BibT_eX]

[DOI]

CoRR, 2011

Fast Local Computation Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 2011

Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity.

[BibT_eX]

[DOI]

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

A local decision test for sparse polynomials.

[BibT_eX]

[DOI]

Elena Grigorescu

Kyomin Jung

Inf. Process. Lett., 2010

Testing monotonicity of distributions over general partial orders.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Improved Recommendations via (More) Collaboration.

[BibT_eX]

[DOI]

Proceedings of the 13th International Workshop on the Web and Databases 2010, 2010

Maintaining a large matching and a small vertex cover.

[BibT_eX]

[DOI]

Krzysztof Onak

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Dynamic Approximate Vertex Cover and Maximum Matching.

[BibT_eX]

[DOI]

Krzysztof Onak

Proceedings of the Property Testing - Current Research and Surveys, 2010

Testing (Subclasses of) Halfspaces.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

Sublinear Algorithms in the External Memory Model.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

Testing Non-uniform k-Wise Independent Distributions over Product Spaces.

[BibT_eX]

[DOI]

Ning Xie

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

Testing monotone high-dimensional distributions.

[BibT_eX]

[DOI]

Rocco A. Servedio

Random Struct. Algorithms, 2009

External Sampling.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 36th International Colloquium, 2009

Testing ±1-weight halfspace.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2009

2008

Linearity Testing/Testing Hadamard Codes.

[BibT_eX]

[DOI]

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

08341 Executive Summary - Sublinear Algorithms.

[BibT_eX]

[DOI]

Proceedings of the Sublinear Algorithms, 17.08. - 22.08.2008, 2008

08341 Abstracts Collection - Sublinear Algorithms.

[BibT_eX]

[DOI]

Artur Czumaj

S. Muthu Muthukrishnan

Christian Sohler

Proceedings of the Sublinear Algorithms, 17.08. - 22.08.2008, 2008

2007

Testing Halfspaces.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Testing for Concise Representations.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Testing k-wise and almost k-wise independence.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

2006

Tolerant property testing and distance approximation.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2006

2005

Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

Approximating the Minimum Spanning Tree Weight in Sublinear Time.

[BibT_eX]

[DOI]

Bernard Chazelle

Luca Trevisan

SIAM J. Comput., 2005

The Complexity of Approximating the Entropy.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

Fast approximate PCPs for multidimensional bin-packing problems.

[BibT_eX]

[DOI]

Tugkan Batu

Patrick White

Inf. Comput., 2005

Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

05291 Abstracts Collection -- Sublinear Algorithms.

[BibT_eX]

[DOI]

Artur Czumaj

S. Muthu Muthukrishnan

Christian Sohler

Proceedings of the Sublinear Algorithms, 17.07. - 22.07.2005, 2005

2004

Fast approximate probabilistically checkable proofs.

[BibT_eX]

[DOI]

Inf. Comput., 2004

Non-Abelian Homomorphism Testing, and Distributions Close to their Self-Convolutions

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2004

Sublinear algorithms for testing monotone and unimodal distributions.

[BibT_eX]

[DOI]

Tugkan Batu

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

The Bloomier filter: an efficient data structure for static support lookup tables.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

2003

Algorithms column: sublinear time algorithms.

[BibT_eX]

[DOI]

SIGACT News, 2003

On Testing Convexity and Submodularity.

[BibT_eX]

[DOI]

SIAM J. Comput., 2003

Testing membership in parenthesis languages.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2003

A sublinear algorithm for weakly approximating edit distance.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Sublinear-time approximation of Euclidean minimum spanning tree.

[BibT_eX]

[DOI]

Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

2002

Monotonicity testing over general poset domains.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

2001

Checking Approximate Computations of Polynomials and Functional Equations.

[BibT_eX]

[DOI]

SIAM J. Comput., 2001

Testing Parenthesis Languages.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2001

Selective private function evaluation with applications to private statistics.

[BibT_eX]

[DOI]

Proceedings of the Twentieth Annual ACM Symposium on Principles of Distributed Computing, 2001

Testing Random Variables for Independence and Identity.

[BibT_eX]

[DOI]

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

Learning Polynomials with Queries: The Highly Noisy Case.

[BibT_eX]

[DOI]

Oded Goldreich

Madhu Sudan

SIAM J. Discret. Math., 2000

Spot-Checkers.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2000

Random walks with "back buttons" (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, 2000

Testing that distributions are close.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual Symposium on Foundations of Computer Science, 2000

1999

On the Robustness of Functional Equations.

[BibT_eX]

[DOI]

SIAM J. Comput., 1999

Fast Approximate PCPs.

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

1998

Reconstructing Algebraic Functions from Mixed Data.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

1997

Exactly Learning Automata of Small Cover Time.

[BibT_eX]

[DOI]

Mach. Learn., 1997

Efficient Learning of Typical Finite Automata from Random Walks.

[BibT_eX]

[DOI]

Inf. Comput., 1997

Learning Distributions from Random Walks.

[BibT_eX]

[DOI]

Proceedings of the Tenth Annual Conference on Computational Learning Theory, 1997

1996

Robust Characterizations of Polynomials with Applications to Program Testing.

[BibT_eX]

[DOI]

Madhu Sudan

SIAM J. Comput., 1996

Designing Checkers for Programs that Run in Parallel.

[BibT_eX]

[DOI]

Algorithmica, 1996

Short Paths in Expander Graphs.

[BibT_eX]

[DOI]

Jon M. Kleinberg

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

Approximate Checking of Polynomials and Functional Equations (extended abstract).

[BibT_eX]

[DOI]

Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995

Learning Fallible Deterministic Finite Automata.

[BibT_eX]

[DOI]

Mach. Learn., 1995

Efficient Algorithms for Learning to Play Repeated Games Against Computationally Bounded Adversaries.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

On Learning Bounded-Width Branching Programs.

[BibT_eX]

[DOI]

Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

1994

On the learnability of discrete distributions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

A new modular interpolation algorithm for factoring multivariate polynominals.

[BibT_eX]

[DOI]

Richard Zippel

Proceedings of the Algorithmic Number Theory, First International Symposium, 1994

1993

Self-Testing/Correcting with Applications to Numerical Problems.

[BibT_eX]

[DOI]

Manuel Blum

Michael Luby

J. Comput. Syst. Sci., 1993

Learning Fallible Finite State Automata.

[BibT_eX]

[DOI]

Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993

1992

On the Time and Space Complexity of Computation Using Write-Once Memory Or Is Pen Really Much Worse Than Pencil?

[BibT_eX]

[DOI]

Sandy Irani

Moni Naor

Math. Syst. Theory, 1992

Batch Checking with Applications to Linear Functions.

[BibT_eX]

[DOI]

Inf. Process. Lett., 1992

Self-Testing Polynomial Functions Efficiently and Over Rational Domains.

[BibT_eX]

[DOI]

Madhu Sudan

Proceedings of the Third Annual ACM/SIGACT-SIAM Symposium on Discrete Algorithms, 1992

1991

A Competitive 2-Server Algorithm.

[BibT_eX]

[DOI]

Sandy Irani

Inf. Process. Lett., 1991

Self-Testing/Correcting for Polynomials and for Approximate Functions

[BibT_eX]

[DOI]

Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, 1991

Interactive Proofs with Space Bounded Provers.

[BibT_eX]

[DOI]

Joe Kilian

Proceedings of the Advances in Cryptology, 1991

1990

The Cover Time of a Regular Expander is O(n log n).

[BibT_eX]

[DOI]

Inf. Process. Lett., 1990

1989

Reversing Trains: A Turn of the Century Sorting Problem.

[BibT_eX]

[DOI]

J. Algorithms, 1989

Program Result Checking against Adaptive Programs and in Cryptographic Settings.

[BibT_eX]

[DOI]

Manuel Blum

Michael Luby