# Dana Ron

According to our database1, Dana Ron authored at least 132 papers between 1993 and 2019.

Collaborative distances:
• Dijkstra number2 of four.
• Erdős number3 of two.

Book
In proceedings
Article
PhD thesis
Other

## Bibliography

2019
The Subgraph Testing Model.
Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

The Arboricity Captures the Complexity of Sampling Edges.
Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018
Best of two local models: Centralized local and distributed local algorithms.
Inf. Comput., 2018

Provable and Practical Approximations for the Degree Distribution using Sublinear Graph Samples.
Proceedings of the 2018 World Wide Web Conference on World Wide Web, 2018

On approximating the number of k-cliques in sublinear time.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Testing bounded arboricity.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism.
Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

Property Testing of Planarity in the CONGEST model.
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, 2018

On the Testability of Graph Partition Properties.
Proceedings of the Approximation, 2018

2017
Constructing near spanning trees with few local inspections.
Random Struct. Algorithms, 2017

Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection.
Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

2016
Testing Bipartiteness of Graphs in Sublinear Time.
Encyclopedia of Algorithms, 2016

Testing Bipartiteness in the Dense-Graph Model.
Encyclopedia of Algorithms, 2016

Estimating Simple Graph Parameters in Sublinear Time.
Encyclopedia of Algorithms, 2016

The Power of an Example: Hidden Set Size Approximation Using Group Queries and Conditional Sampling.
TOCT, 2016

A Local Algorithm for Constructing Spanners in Minor-Free Graphs.
Proceedings of the Approximation, 2016

2015
Testing Probability Distributions using Conditional Samples.
SIAM J. Comput., 2015

Constructing Near Spanning Trees with Few Local Inspections.
Electronic Colloquium on Computational Complexity (ECCC), 2015

Approximately Counting Triangles in Sublinear Time.
Electronic Colloquium on Computational Complexity (ECCC), 2015

On Sample-Based Testers.
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, 2015

Distributed Maximum Matching in Bounded Degree Graphs.
Proceedings of the 2015 International Conference on Distributed Computing and Networking, 2015

Approximately Counting Triangles in Sublinear Time.
Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

2014
Testing Properties of Sparse Images.
ACM Trans. Algorithms, 2014

Finding cycles and trees in sublinear time.
Random Struct. Algorithms, 2014

Testing equivalence between distributions using conditional samples.
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

On Learning and Testing Dynamic Environments.
Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

Deterministic Stateless Centralized Local Algorithms for Bounded Degree Graphs.
Proceedings of the Algorithms - ESA 2014, 2014

Local Algorithms for Sparse Spanning Graphs.
Proceedings of the Approximation, 2014

2013
Comparing the strength of query types in property testing: The case of k-colorability.
Computational Complexity, 2013

Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities.
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

On the possibilities and limitations of pseudodeterministic algorithms.
Proceedings of the Innovations in Theoretical Computer Science, 2013

A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor.
Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

A Simple Online Competitive Adaptation of Lempel-Ziv Compression with Efficient Random Access Support.
Proceedings of the 2013 Data Compression Conference, 2013

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

Finding Cycles and Trees in Sublinear Time.
Electronic Colloquium on Computational Complexity (ECCC), 2012

Testing probability distributions using conditional samples.
Electronic Colloquium on Computational Complexity (ECCC), 2012

A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size.
Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

Testing Similar Means.
Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011
Distribution-Free Testing for Monomials with a Sublinear Number of Queries.
Theory of Computing, 2011

Testing Eulerianity and connectivity in directed sparse graphs.
Theor. Comput. Sci., 2011

Testing Properties of Collections of Distributions.
Proceedings of the Innovations in Computer Science, 2011

On Approximating the Number of Relevant Variables in a Function.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity.
Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

On Testing Expansion in Bounded-Degree Graphs.
Proceedings of the Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, 2011

2010
Approximating the distance to monotonicity in high dimensions.
ACM Trans. Algorithms, 2010

Counting Stars and Other Small Subgraphs in Sublinear Time.
Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

Testing Properties of Sparse Images.
Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

Testing Computability by Width-2 OBDDs Where the Variable Order is Unknown.
Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries.
Proceedings of the Approximation, 2010

2009
Approximating the distance to properties in bounded-degree and general sparse graphs.
ACM Trans. Algorithms, 2009

Scheduling with conflicts: online and offline algorithms.
J. Scheduling, 2009

Algorithmic and Analysis Techniques in Property Testing.
Foundations and Trends in Theoretical Computer Science, 2009

Counting Stars and Other Small Subgraphs in Sublinear Time.
Electronic Colloquium on Computational Complexity (ECCC), 2009

On proximity oblivious testing.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Testing Computability by Width Two OBDDs.
Proceedings of the Approximation, 2009

Algorithmic Aspects of Property Testing in the Dense Graphs Model.
Proceedings of the Approximation, 2009

2008
Comparing the strength of query types in property testing: the case of testing k-colorability.
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

2007
Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms.
Theor. Comput. Sci., 2007

The hardness of the Expected Decision Depth problem.
Inf. Process. Lett., 2007

Finding a Dense-Core in Jellyfish Graphs.
Proceedings of the Algorithms and Models for the Web-Graph, 5th International Workshop, 2007

Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem.
Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), 2007

Property Testing: A Learning Theory Perspective.
Proceedings of the Learning Theory, 20th Annual Conference on Learning Theory, 2007

Sublinear Algorithms for Approximating String Compressibility.
Proceedings of the Approximation, 2007

On the Benefits of Adaptivity in Property Testing of Dense Graphs.
Proceedings of the Approximation, 2007

2006
Tolerant property testing and distance approximation.
J. Comput. Syst. Sci., 2006

Testing triangle-freeness in general graphs.
Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Distance Approximation in Bounded-Degree and General Sparse Graphs.
Proceedings of the Approximation, 2006

Approximating Average Parameters of Graphs.
Proceedings of the Approximation, 2006

2005
A characterization of low-weight words that span generalized reed-muller codes.
IEEE Trans. Information Theory, 2005

Testing Reed-Muller codes.
IEEE Trans. Information Theory, 2005

Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size
Electronic Colloquium on Computational Complexity (ECCC), 2005

On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms
Electronic Colloquium on Computational Complexity (ECCC), 2005

Approximating Average Parameters of Graphs.
Proceedings of the Sublinear Algorithms, 17.07. - 22.07.2005, 2005

2004
A New Conceptual Clustering Framework.
Machine Learning, 2004

On Estimating the Average Degree of a Graph
Electronic Colloquium on Computational Complexity (ECCC), 2004

Tolerant Property Testing and Distance Approximation
Electronic Colloquium on Computational Complexity (ECCC), 2004

Testing Polynomials over General Fields.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003
Testing membership in parenthesis languages.
Random Struct. Algorithms, 2003

Bounds on Linear Codes for Network Multicast
Electronic Colloquium on Computational Complexity (ECCC), 2003

Tight Bounds for Testing Bipartiteness in General Graphs.
Proceedings of the Approximation, 2003

Testing Low-Degree Polynomials over GF(2(.
Proceedings of the Approximation, 2003

On Finding Large Conjunctive Clusters.
Proceedings of the Computational Learning Theory and Kernel Machines, 2003

2002
Testing Basic Boolean Formulae.
SIAM J. Discrete Math., 2002

Testing properties of directed graphs: acyclicity and connectivity.
Random Struct. Algorithms, 2002

On Testing Convexity and Submodularity.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

Testing Juntas.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001
On Disjoint Chains of Subsets.
J. Comb. Theory, Ser. A, 2001

Proclaiming Dictators and Juntas or Testing Boolean Formulae
Electronic Colloquium on Computational Complexity (ECCC), 2001

Errata for: "On randomized one-round communication complexity".
Computational Complexity, 2001

Testing metric properties.
Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Proclaiming Dictators and Juntas or Testing Boolean Formulae.
Proceedings of the Approximation, 2001

Testing Parenthesis Languages.
Proceedings of the Approximation, 2001

2000
Testing Problems with Sublearning Sample Complexity.
J. Comput. Syst. Sci., 2000

On Testing Expansion in Bounded-Degree Graphs
Electronic Colloquium on Computational Complexity (ECCC), 2000

Testing Monotonicity.
Combinatorica, 2000

Testing Acyclicity of Directed Graphs in Sublinear Time.
Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

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

1999
A Sublinear Bipartiteness Tester for Bounded Degree Graphs.
Combinatorica, 1999

Chinese Remaindering with Errors.
Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Testing the Diameter of Graphs.
Proceedings of the Randomization, 1999

Improved Testing Algorithms for Monotonicity.
Proceedings of the Randomization, 1999

1998
Guest Editor's Introduction.
Machine Learning, 1998

Chinese Remaindering with Errors
Electronic Colloquium on Computational Complexity (ECCC), 1998

A Sublinear Bipartiteness Tester for Bunded Degree Graphs.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

The Power of a Pebble: Exploring and Mapping Directed Graphs.
Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Testing Monotonicity.
Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Testing Problems with Sub-Learning Sample Complexity.
Proceedings of the Eleventh Annual Conference on Computational Learning Theory, 1998

1997
Exactly Learning Automata of Small Cover Time.
Machine Learning, 1997

On Universal Learning Algorithms.
Inf. Process. Lett., 1997

A Probabilistic Error-Correcting Scheme.
IACR Cryptology ePrint Archive, 1997

Computational Sample Complexity
Electronic Colloquium on Computational Complexity (ECCC), 1997

Property Testing in Bounded Degree Graphs.
Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, 1997

Algorithmic Stability and Sanity-Check Bounds for Leave-one-Out Cross-Validation.
Proceedings of the Tenth Annual Conference on Computational Learning Theory, 1997

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

1996
The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length.
Machine Learning, 1996

Agreement in the Presence of Faults, on Networks of Bounded Degree.
Inf. Process. Lett., 1996

Property Testing and its connection to Learning and Approximation
Electronic Colloquium on Computational Complexity (ECCC), 1996

Property Testing and Its Connection to Learning and Approximation.
Proceedings of the 37th Annual Symposium on Foundations of Computer Science, 1996

1995
Learning Fallible Deterministic Finite Automata.
Machine Learning, 1995

On randomized one-round communication complexity.
Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, 1995

Efficient Algorithms for Learning to Play Repeated Games Against Computationally Bounded Adversaries.
Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

On the Learnability and Usage of Acyclic Probabilistic Finite Automata.
Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

Exactly Learning Automata with Small Cover Time.
Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

An Experimental and Theoretical Comparison of Model Selection Methods.
Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

Learning to Model Sequences Generated by Switching Distributions.
Proceedings of the Eigth Annual Conference on Computational Learning Theory, 1995

Automata learning and its applications.
PhD thesis, 1995

1994
On the learnability of discrete distributions.
Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

Learning Probabilistic Automata with Variable Memory Length.
Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

1993
Efficient learning of typical finite automata from random walks.
Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, 1993

The Power of Amnesia.
Proceedings of the Advances in Neural Information Processing Systems 6, 1993

Learning Fallible Finite State Automata.
Proceedings of the Sixth Annual ACM Conference on Computational Learning Theory, 1993