Dana Ron
According to our database^{1},
Dana Ron
authored at least 132 papers
between 1993 and 2019.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at orcid.org
On csauthors.net:
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 kcliques in sublinear time.
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018
Testing bounded arboricity.
Proceedings of the TwentyNinth Annual ACMSIAM Symposium on Discrete Algorithms, 2018
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism.
Proceedings of the TwentyNinth Annual ACMSIAM 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 DenseGraph 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 MinorFree 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 SampleBased 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 TwentyFifth Annual ACMSIAM 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 kcolorability.
Computational Complexity, 2013
Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities.
Proceedings of the TwentyFourth Annual ACMSIAM Symposium on Discrete Algorithms, 2013
On the possibilities and limitations of pseudodeterministic algorithms.
Proceedings of the Innovations in Theoretical Computer Science, 2013
A QuasiPolynomial 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 LempelZiv 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 nearoptimal sublineartime algorithm for approximating the minimum vertex cover size.
Proceedings of the TwentyThird Annual ACMSIAM Symposium on Discrete Algorithms, 2012
Testing Similar Means.
Proceedings of the Automata, Languages, and Programming  39th International Colloquium, 2012
2011
DistributionFree 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 BoundedDegree 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 TwentyFirst Annual ACMSIAM 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 Width2 OBDDs Where the Variable Order is Unknown.
Proceedings of the Algorithms and Complexity, 7th International Conference, 2010
DistributionFree Testing Algorithms for Monomials with a Sublinear Number of Queries.
Proceedings of the Approximation, 2010
2009
Approximating the distance to properties in boundeddegree 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 kcolorability.
Proceedings of the Nineteenth Annual ACMSIAM 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 DenseCore in Jellyfish Graphs.
Proceedings of the Algorithms and Models for the WebGraph, 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 trianglefreeness in general graphs.
Proceedings of the Seventeenth Annual ACMSIAM Symposium on Discrete Algorithms, 2006
Distance Approximation in BoundedDegree and General Sparse Graphs.
Proceedings of the Approximation, 2006
Approximating Average Parameters of Graphs.
Proceedings of the Approximation, 2006
2005
A characterization of lowweight words that span generalized reedmuller codes.
IEEE Trans. Information Theory, 2005
Testing ReedMuller 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 LowDegree 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
ConflictFree 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 oneround 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 BoundedDegree 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 ThirtyFirst 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 SubLearning 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 ErrorCorrecting 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 TwentyNinth Annual ACM Symposium on the Theory of Computing, 1997
Algorithmic Stability and SanityCheck Bounds for LeaveoneOut CrossValidation.
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 oneround communication complexity.
Proceedings of the TwentySeventh 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 TwentySixth 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 TwentyFifth 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