Dana Ron

According to our database, Dana Ron authored at least 145 papers between 1993 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Sample-Based Distance-Approximation for Subsequence-Freeness.

Omer Cohen Sidon, Dana Ron

Algorithmica, August, 2024

Testing C_k-freeness in bounded-arboricity graphs.

Talya Eden, Reut Levi, Dana Ron

CoRR, 2024

Testing C_k-Freeness in Bounded-Arboricity Graphs.

Talya Eden, Reut Levi, Dana Ron

Proceedings of the 51st International Colloquium on Automata, Languages, and Programming, 2024

2023

A Lower Bound on the Complexity of Testing Grained Distributions.

Oded Goldreich, Dana Ron

Comput. Complex., December, 2023

2022

Optimal Distribution-Free Sample-Based Testing of Subsequence-Freeness with One-Sided Error.

Dana Ron, Asaf Rosin

ACM Trans. Comput. Theory, 2022

Approximating the Arboricity in Sublinear Time.

Talya Eden, Saleet Mossel, Dana Ron

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

Almost Optimal Bounds for Sublinear-Time Sampling of k-Cliques in Bounded Arboricity Graphs.

Talya Eden, Dana Ron, Will Rosenbaum

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

The Structure of Configurations in One-Dimensional Majority Cellular Automata: From Cell Stability to Configuration Periodicity.

Yonatan Nakar, Dana Ron

Proceedings of the Cellular Automata, 2022

2021

Property Testing of the Boolean and Binary Rank.

Michal Parnas, Dana Ron, Adi Shraibman

Theory Comput. Syst., 2021

Testing Distributions of Huge Objects.

Oded Goldreich, Dana Ron

Electron. Colloquium Comput. Complex., 2021

Property testing of planarity in the CONGEST model.

Reut Levi, Moti Medina, Dana Ron

Distributed Comput., 2021

Optimal Distribution-Free Sample-Based Testing of Subsequence-Freeness.

Dana Ron, Asaf Rosin

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

On Efficient Distance Approximation for Graph Properties.

Nimrod Fiat, Dana Ron

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

Testing Dynamic Environments: Back to Basics.

Yonatan Nakar, Dana Ron

Proceedings of the 48th International Colloquium on Automata, Languages, and Programming, 2021

2020

A Probabilistic Error-Correcting Scheme that Provides Partial Secrecy.

Scott E. Decatur, Oded Goldreich, Dana Ron

Proceedings of the Computational Complexity and Property Testing, 2020

On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition).

Oded Goldreich, Dana Ron

Proceedings of the Computational Complexity and Property Testing, 2020

Testing Bounded Arboricity.

Talya Eden, Reut Levi, Dana Ron

ACM Trans. Algorithms, 2020

On Approximating the Number of k-Cliques in Sublinear Time.

Talya Eden, Dana Ron, C. Seshadhri

SIAM J. Comput., 2020

One-Sided Error Testing of Monomials and Affine Subspaces.

Oded Goldreich, Dana Ron

Electron. Colloquium Comput. Complex., 2020

Almost Optimal Bounds for Sublinear-Time Sampling of k-Cliques: Sampling Cliques is Harder Than Counting.

Talya Eden, Dana Ron, Will Rosenbaum

CoRR, 2020

Local Algorithms for Sparse Spanning Graphs.

Reut Levi, Dana Ron, Ronitt Rubinfeld

Algorithmica, 2020

Faster sublinear approximation of the number of <i>k</i>-cliques in low-arboricity graphs.

Talya Eden, Dana Ron, C. Seshadhri

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

Almost Optimal Distribution-Free Sample-Based Testing of k-Modality.

Dana Ron, Asaf Rosin

Proceedings of the Approximation, 2020

2019

Sublinear-Time Algorithms for Approximating Graph Parameters.

Dana Ron

Proceedings of the Computing and Software Science - State of the Art and Perspectives, 2019

Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection.

Talya Eden, Dana Ron, C. Seshadhri

SIAM J. Discret. Math., 2019

The Arboricity Captures the Complexity of Sampling Edges.

Talya Eden, Dana Ron, Will Rosenbaum

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 2019

2018

Best of two local models: Centralized local and distributed local algorithms.

Guy Even, Moti Medina, Dana Ron

Inf. Comput., 2018

On the Testability of Graph Partition Properties.

Yonatan Nakar, Dana Ron

Electron. Colloquium Comput. Complex., 2018

The Subgraph Testing Model.

Oded Goldreich, Dana Ron

Electron. Colloquium Comput. Complex., 2018

Faster sublinear approximations of k-cliques for low arboricity graphs.

Talya Eden, Dana Ron, C. Seshadhri

CoRR, 2018

Provable and Practical Approximations for the Degree Distribution using Sublinear Graph Samples.

Talya Eden, Shweta Jain, Ali Pinar, Dana Ron, C. Seshadhri

Proceedings of the 2018 World Wide Web Conference on World Wide Web, 2018

2017

Approximately Counting Triangles in Sublinear Time.

Talya Eden, Amit Levi, Dana Ron, C. Seshadhri

SIAM J. Comput., 2017

Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection.

Talya Eden, Dana Ron, C. Seshadhri

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

2016

Testing Bipartiteness of Graphs in Sublinear Time.

Oded Goldreich, Dana Ron

Encyclopedia of Algorithms, 2016

Testing Bipartiteness in the Dense-Graph Model.

Oded Goldreich, Dana Ron

Encyclopedia of Algorithms, 2016

Estimating Simple Graph Parameters in Sublinear Time.

Oded Goldreich, Dana Ron

Encyclopedia of Algorithms, 2016

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

Dana Ron, Gilad Tsur

ACM Trans. Comput. Theory, 2016

Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism.

Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron

Electron. Colloquium Comput. Complex., 2016

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

Reut Levi, Dana Ron, Ronitt Rubinfeld

Proceedings of the Approximation, 2016

2015

A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor.

Reut Levi, Dana Ron

ACM Trans. Algorithms, 2015

Testing Probability Distributions using Conditional Samples.

Clément L. Canonne, Dana Ron, Rocco A. Servedio

SIAM J. Comput., 2015

Constructing Near Spanning Trees with Few Local Inspections.

Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira

Electron. Colloquium Comput. Complex., 2015

Approximately Counting Triangles in Sublinear Time.

Talya Eden, Amit Levi, Dana Ron

Electron. Colloquium Comput. Complex., 2015

Distributed Maximum Matching in Bounded Degree Graphs.

Guy Even, Moti Medina, Dana Ron

Proceedings of the 2015 International Conference on Distributed Computing and Networking, 2015

2014

Testing Properties of Sparse Images.

Dana Ron, Gilad Tsur

ACM Trans. Algorithms, 2014

On Learning and Testing Dynamic Environments.

Oded Goldreich, Dana Ron

Electron. Colloquium Comput. Complex., 2014

Best of Two Local Models: Local Centralized and Local Distributed Algorithms.

Guy Even, Moti Medina, Dana Ron

CoRR, 2014

Testing equivalence between distributions using conditional samples.

Clément L. Canonne, Dana Ron, Rocco A. Servedio

Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, 2014

Deterministic Stateless Centralized Local Algorithms for Bounded Degree Graphs.

Guy Even, Moti Medina, Dana Ron

Proceedings of the Algorithms - ESA 2014, 2014

2013

Exponentially improved algorithms and lower bounds for testing signed majorities.

Dana Ron, Rocco A. Servedio

Electron. Colloquium Comput. Complex., 2013

On Sample-Based Testers.

Oded Goldreich, Dana Ron

Electron. Colloquium Comput. Complex., 2013

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

Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron

Comput. Complex., 2013

Sublinear Algorithms for Approximating String Compressibility.

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith

Algorithmica, 2013

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

Akashnil Dutta, Reut Levi, Dana Ron, Ronitt Rubinfeld

Proceedings of the 2013 Data Compression Conference, 2013

2012

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

Dana Ron, Ronitt Rubinfeld, Muli Safra, Alex Samorodnitsky, Omri Weinstein

ACM Trans. Comput. Theory, 2012

Testing computability by width-two OBDDs.

Dana Ron, Gilad Tsur

Theor. Comput. Sci., 2012

Testing Similar Means.

Reut Levi, Dana Ron, Ronitt Rubinfeld

Electron. Colloquium Comput. Complex., 2012

On the possibilities and limitations of pseudodeterministic algorithms.

Oded Goldreich, Shafi Goldwasser, Dana Ron

Electron. Colloquium Comput. Complex., 2012

Finding Cycles and Trees in Sublinear Time.

Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler

Electron. Colloquium Comput. Complex., 2012

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

Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld

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

2011

Distribution-Free Testing for Monomials with a Sublinear Number of Queries.

Elya Dolev, Dana Ron

Theory Comput., 2011

Testing Eulerianity and connectivity in directed sparse graphs.

Yaron Orenstein, Dana Ron

Theor. Comput. Sci., 2011

On Proximity-Oblivious Testing.

Oded Goldreich, Dana Ron

SIAM J. Comput., 2011

Algorithmic Aspects of Property Testing in the Dense Graphs Model.

Oded Goldreich, Dana Ron

SIAM J. Comput., 2011

On Approximating the Number of Relevant Variables in a Function.

Dana Ron, Gilad Tsur

Electron. Colloquium Comput. Complex., 2011

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

Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein

CoRR, 2011

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

Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein

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

On Testing Expansion in Bounded-Degree Graphs.

Oded Goldreich, Dana Ron

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.

Shahar Fattal, Dana Ron

ACM Trans. Algorithms, 2010

Testing Properties of Collections of Distributions.

Reut Levi, Dana Ron, Ronitt Rubinfeld

Electron. Colloquium Comput. Complex., 2010

On the Benefits of Adaptivity in Property Testing of Dense Graphs.

Mira Gonen, Dana Ron

Algorithmica, 2010

Algorithmic Aspects of Property Testing in the Dense Graphs Model.

Oded Goldreich, Dana Ron

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

Comparing the Strength of Query Types in Property Testing: The Case of Testing <i>k</i>-Colorability.

Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron

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

Testing Computability by Width-2 OBDDs Where the Variable Order is Unknown.

Dana Ron, Gilad Tsur

Proceedings of the Algorithms and Complexity, 7th International Conference, 2010

Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries.

Elya Dolev, Dana Ron

Proceedings of the Approximation, 2010

2009

Approximating the distance to properties in bounded-degree and general sparse graphs.

Sharon Marko, Dana Ron

ACM Trans. Algorithms, 2009

Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem.

Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam D. Smith

SIAM J. Comput., 2009

Scheduling with conflicts: online and offline algorithms.

Guy Even, Magnús M. Halldórsson, Lotem Kaplan, Dana Ron

J. Sched., 2009

Algorithmic and Analysis Techniques in Property Testing.

Dana Ron

Found. Trends Theor. Comput. Sci., 2009

Counting Stars and Other Small Subgraphs in Sublinear Time.

Dana Ron, Mira Gonen, Yuval Shavitt

Electron. Colloquium Comput. Complex., 2009

2008

Testing Triangle-Freeness in General Graphs.

Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron

SIAM J. Discret. Math., 2008

Property Testing: A Learning Theory Perspective.

Dana Ron

Found. Trends Mach. Learn., 2008

Finding a dense-core in Jellyfish graphs.

Mira Gonen, Dana Ron, Udi Weinsberg, Avishai Wool

Comput. Networks, 2008

Comparing the strength of query types in property testing: the case of testing <i>k</i>-colorability.

Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron

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.

Michal Parnas, Dana Ron

Theor. Comput. Sci., 2007

The hardness of the Expected Decision Depth problem.

Dana Ron, Amir Rosenfeld, Salil P. Vadhan

Inf. Process. Lett., 2007

2006

Testing Polynomials over General Fields.

Tali Kaufman, Dana Ron

SIAM J. Comput., 2006

Tolerant property testing and distance approximation.

Michal Parnas, Dana Ron, Ronitt Rubinfeld

J. Comput. Syst. Sci., 2006

Distance Approximation in Bounded-Degree and General Sparse Graphs.

Sharon Marko, Dana Ron

Proceedings of the Approximation, 2006

2005

A characterization of low-weight words that span generalized reed-muller codes.

Tali Kaufman, Dana Ron

IEEE Trans. Inf. Theory, 2005

Testing Reed-Muller codes.

Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron

IEEE Trans. Inf. Theory, 2005

Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size

Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam D. Smith

Electron. Colloquium Comput. Complex., 2005

Approximating Average Parameters of Graphs.

Oded Goldreich, Dana Ron

Electron. Colloquium Comput. Complex., 2005

2004

Testing of Clustering.

Noga Alon, Seannie Dar, Michal Parnas, Dana Ron

SIAM Rev., 2004

Tight Bounds for Testing Bipartiteness in General Graphs.

Tali Kaufman, Michael Krivelevich, Dana Ron

SIAM J. Comput., 2004

A New Conceptual Clustering Framework.

Nina Mishra, Dana Ron, Ram Swaminathan

Mach. Learn., 2004

Testing juntas.

Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky

J. Comput. Syst. Sci., 2004

On Estimating the Average Degree of a Graph

Oded Goldreich, Dana Ron

Electron. Colloquium Comput. Complex., 2004

2003

On Testing Convexity and Submodularity.

Michal Parnas, Dana Ron, Ronitt Rubinfeld

SIAM J. Comput., 2003

Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks.

Guy Even, Zvi Lotker, Dana Ron, Shakhar Smorodinsky

SIAM J. Comput., 2003

Testing membership in parenthesis languages.

Michal Parnas, Dana Ron, Ronitt Rubinfeld

Random Struct. Algorithms, 2003

Testing metric properties.

Michal Parnas, Dana Ron

Inf. Comput., 2003

Bounds on Linear Codes for Network Multicast

Meir Feder, Dana Ron, Ami Tavory

Electron. Colloquium Comput. Complex., 2003

Testing Low-Degree Polynomials over GF(2(.

Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron

Proceedings of the Approximation, 2003

On Finding Large Conjunctive Clusters.

Nina Mishra, Dana Ron, Ram Swaminathan

Proceedings of the Computational Learning Theory and Kernel Machines, 2003

2002

Testing Basic Boolean Formulae.

Michal Parnas, Dana Ron, Alex Samorodnitsky

SIAM J. Discret. Math., 2002

Testing the diameter of graphs.

Michal Parnas, Dana Ron

Random Struct. Algorithms, 2002

Testing properties of directed graphs: acyclicity and connectivity.

Michael A. Bender, Dana Ron

Random Struct. Algorithms, 2002

The Power of a Pebble: Exploring and Mapping Directed Graphs.

Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, Salil P. Vadhan

Inf. Comput., 2002

Property Testing in Bounded Degree Graphs.

Oded Goldreich, Dana Ron

Algorithmica, 2002

2001

On Disjoint Chains of Subsets.

Eric Lehman, Dana Ron

J. Comb. Theory A, 2001

Proclaiming Dictators and Juntas or Testing Boolean Formulae

Michal Parnas, Dana Ron, Alex Samorodnitsky

Electron. Colloquium Comput. Complex., 2001

Errata for: "On randomized one-round communication complexity".

Ilan Kremer, Noam Nisan, Dana Ron

Comput. Complex., 2001

Testing Parenthesis Languages.

Michal Parnas, Dana Ron, Ronitt Rubinfeld

Proceedings of the Approximation, 2001

2000

Testing Problems with Sublearning Sample Complexity.

Michael J. Kearns, Dana Ron

J. Comput. Syst. Sci., 2000

On Testing Expansion in Bounded-Degree Graphs

Oded Goldreich, Dana Ron

Electron. Colloquium Comput. Complex., 2000

Testing Monotonicity.

Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, Alex Samorodnitsky

Comb., 2000

Testing Acyclicity of Directed Graphs in Sublinear Time.

Michael A. Bender, Dana Ron

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

1999

Computational Sample Complexity.

Scott E. Decatur, Oded Goldreich, Dana Ron

SIAM J. Comput., 1999

Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation.

Michael J. Kearns, Dana Ron

Neural Comput., 1999

Improved Testing Algorithms for Monotonicity.

Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky

Electron. Colloquium Comput. Complex., 1999

A Sublinear Bipartiteness Tester for Bounded Degree Graphs.

Oded Goldreich, Dana Ron

Comb., 1999

On Randomized One-Round Communication Complexity.

Ilan Kremer, Noam Nisan, Dana Ron

Comput. Complex., 1999

1998

Guest Editor's Introduction.

Dana Ron

Mach. Learn., 1998

On the Learnability and Usage of Acyclic Probabilistic Finite Automata.

Dana Ron, Yoram Singer, Naftali Tishby

J. Comput. Syst. Sci., 1998

Chinese Remaindering with Errors

Oded Goldreich, Dana Ron, Madhu Sudan

Electron. Colloquium Comput. Complex., 1998

A Sublinear Bipartiteness Tester for Bunded Degree Graphs.

Oded Goldreich, Dana Ron

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Testing Monotonicity.

Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron

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

Testing Problems with Sub-Learning Sample Complexity.

Michael J. Kearns, Dana Ron

Proceedings of the Eleventh Annual Conference on Computational Learning Theory, 1998

1997

Exactly Learning Automata of Small Cover Time.

Dana Ron, Ronitt Rubinfeld

Mach. Learn., 1997

An Experimental and Theoretical Comparison of Model Selection Methods.

Michael J. Kearns, Yishay Mansour, Andrew Y. Ng, Dana Ron

Mach. Learn., 1997

On Universal Learning Algorithms.

Oded Goldreich, Dana Ron

Inf. Process. Lett., 1997

Efficient Learning of Typical Finite Automata from Random Walks.

Yoav Freund, Michael J. Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie

Inf. Comput., 1997

A Probabilistic Error-Correcting Scheme.

Scott E. Decatur, Oded Goldreich, Dana Ron

IACR Cryptol. ePrint Arch., 1997

1996

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

Dana Ron, Yoram Singer, Naftali Tishby

Mach. Learn., 1996

Agreement in the Presence of Faults, on Networks of Bounded Degree.

Michael Ben-Or, Dana Ron

Inf. Process. Lett., 1996

Property Testing and its connection to Learning and Approximation

Oded Goldreich, Shafi Goldwasser, Dana Ron

Electron. Colloquium Comput. Complex., 1996

1995

Learning Fallible Deterministic Finite Automata.

Dana Ron, Ronitt Rubinfeld

Mach. Learn., 1995

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

Yoav Freund, Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire

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

Learning to Model Sequences Generated by Switching Distributions.

Yoav Freund, Dana Ron

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

Automata learning and its applications.

Dana Ron

PhD thesis, 1995

1994

On the learnability of discrete distributions.

Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie

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

Learning Probabilistic Automata with Variable Memory Length.

Dana Ron, Yoram Singer, Naftali Tishby

Proceedings of the Seventh Annual ACM Conference on Computational Learning Theory, 1994

1993

The Power of Amnesia.

Dana Ron, Yoram Singer, Naftali Tishby

Proceedings of the Advances in Neural Information Processing Systems 6, 1993

Learning Fallible Finite State Automata.

Dana Ron, Ronitt Rubinfeld

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