Dana Ron

254 papers A* 55A 6B 1C 2Misc 1Journal 152Unranked 25
YearRankTypeTitle / Venue / Authors
2025 A* conf
Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time.
STOC
Talya Eden, Reut Levi, Dana Ron, Ronitt Rubinfeld
2025 J jnl
Approximately Counting and Sampling Hamiltonian Motifs in Sublinear Time.
CoRR
Talya Eden, Reut Levi, Dana Ron, Ronitt Rubinfeld
2025 J jnl
Characterizing and Testing Configuration Stability in Two-Dimensional Threshold Cellular Automata.
CoRR
Yonatan Nakar, Dana Ron
2025 A* conf
Let's Try to Be More Tolerant: On Tolerant Property Testing and Distance Approximation (Invited Talk).
ICALP
Dana Ron
2025 — ch.
One-Sided Error Testing of Monomials and Affine Subspaces.
Computational Complexity and Local Algorithms
Oded Goldreich, Dana Ron
2024 J jnl
Sample-Based Distance-Approximation for Subsequence-Freeness.
Algorithmica
Omer Cohen Sidon, Dana Ron
2024 J jnl
Testing C
CoRR
Talya Eden, Reut Levi, Dana Ron
2024 A* conf
Testing C_k-Freeness in Bounded-Arboricity Graphs.
ICALP
Talya Eden, Reut Levi, Dana Ron
2023 J jnl
A Lower Bound on the Complexity of Testing Grained Distributions.
Comput. Complex.
Oded Goldreich, Dana Ron
2023 A* conf
Sample-Based Distance-Approximation for Subsequence-Freeness.
ICALP
Omer Cohen Sidon, Dana Ron
2023 J jnl
Sample-based distance-approximation for subsequence-freeness.
CoRR
Omer Cohen Sidon, Dana Ron
2023 J jnl
Testing Distributions of Huge Objects.
TheoretiCS
Oded Goldreich, Dana Ron
2022 A* conf
Almost Optimal Bounds for Sublinear-Time Sampling of k-Cliques in Bounded Arboricity Graphs.
ICALP
Talya Eden, Dana Ron, Will Rosenbaum
2022 A* conf
Approximating the Arboricity in Sublinear Time.
SODA
Talya Eden, Saleet Mossel, Dana Ron
2022 J jnl
Optimal Distribution-Free Sample-Based Testing of Subsequence-Freeness with One-Sided Error.
ACM Trans. Comput. Theory
Dana Ron, Asaf Rosin
2022 A conf
Testing Distributions of Huge Objects.
ITCS
Oded Goldreich, Dana Ron
2022 J jnl
Testing Distributions of Huge Objects.
CoRR
Oded Goldreich, Dana Ron
2022 — conf
The Structure of Configurations in One-Dimensional Majority Cellular Automata: From Cell Stability to Configuration Periodicity.
ACRI
Yonatan Nakar, Dana Ron
2022 J jnl
The Structure of Configurations in One-Dimensional Majority Cellular Automata: From Cell Stability to Configuration Periodicity.
CoRR
Yonatan Nakar, Dana Ron
2021 J jnl
A Lower Bound on the Complexity of Testing Grained Distributions.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2021 J jnl
Approximating the Arboricity in Sublinear Time.
CoRR
Talya Eden, Saleet Mossel, Dana Ron
2021 A* conf
On Efficient Distance Approximation for Graph Properties.
SODA
Nimrod Fiat, Dana Ron
2021 A* conf
Optimal Distribution-Free Sample-Based Testing of Subsequence-Freeness.
SODA
Dana Ron, Asaf Rosin
2021 J jnl
Property Testing of the Boolean and Binary Rank.
Theory Comput. Syst.
Michal Parnas, Dana Ron, Adi Shraibman
2021 J jnl
Property testing of planarity in the CONGEST model.
Distributed Comput.
Reut Levi, Moti Medina, Dana Ron
2021 J jnl
Testing Distributions of Huge Objects.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2021 A* conf
Testing Dynamic Environments: Back to Basics.
ICALP
Yonatan Nakar, Dana Ron
2021 J jnl
Testing Dynamic Environments: Back to Basics.
CoRR
Yonatan Nakar, Dana Ron
2020 — ch.
A Probabilistic Error-Correcting Scheme that Provides Partial Secrecy.
Computational Complexity and Property Testing
Scott E. Decatur, Oded Goldreich, Dana Ron
2020 J jnl
Almost Optimal Bounds for Sublinear-Time Sampling of k-Cliques: Sampling Cliques is Harder Than Counting.
CoRR
Talya Eden, Dana Ron, Will Rosenbaum
2020 — conf
Almost Optimal Distribution-Free Sample-Based Testing of k-Modality.
APPROX-RANDOM
Dana Ron, Asaf Rosin
2020 A* conf
Faster sublinear approximation of the number of
SODA
Talya Eden, Dana Ron, C. Seshadhri
2020 J jnl
Local Algorithms for Sparse Spanning Graphs.
Algorithmica
Reut Levi, Dana Ron, Ronitt Rubinfeld
2020 J jnl
On Approximating the Number of k-Cliques in Sublinear Time.
SIAM J. Comput.
Talya Eden, Dana Ron, C. Seshadhri
2020 J jnl
On Efficient Distance Approximation for Graph Properties.
CoRR
Nimrod Fiat, Dana Ron
2020 — ch.
On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition).
Computational Complexity and Property Testing
Oded Goldreich, Dana Ron
2020 J jnl
One-Sided Error Testing of Monomials and Affine Subspaces.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2020 J jnl
Testing Bounded Arboricity.
ACM Trans. Algorithms
Talya Eden, Reut Levi, Dana Ron
2020 J jnl
The Subgraph Testing Model.
ACM Trans. Comput. Theory
Oded Goldreich, Dana Ron
2019 J jnl
Property testing of the Boolean and binary rank.
CoRR
Michal Parnas, Dana Ron, Adi Shraibman
2019 J jnl
Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection.
SIAM J. Discret. Math.
Talya Eden, Dana Ron, C. Seshadhri
2019 — ch.
Sublinear-Time Algorithms for Approximating Graph Parameters.
Computing and Software Science
Dana Ron
2019 A* conf
The Arboricity Captures the Complexity of Sampling Edges.
ICALP
Talya Eden, Dana Ron, Will Rosenbaum
2019 J jnl
The Arboricity Captures the Complexity of Sampling Edges.
CoRR
Talya Eden, Dana Ron, Will Rosenbaum
2019 A conf
The Subgraph Testing Model.
ITCS
Oded Goldreich, Dana Ron
2019 J jnl
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism.
ACM Trans. Comput. Theory
Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron
2018 J jnl
Best of two local models: Centralized local and distributed local algorithms.
Inf. Comput.
Guy Even, Moti Medina, Dana Ron
2018 J jnl
Faster sublinear approximations of k-cliques for low arboricity graphs.
CoRR
Talya Eden, Dana Ron, C. Seshadhri
2018 A* conf
On approximating the number of k-cliques in sublinear time.
STOC
Talya Eden, Dana Ron, C. Seshadhri
2018 — conf
On the Testability of Graph Partition Properties.
APPROX-RANDOM
Yonatan Nakar, Dana Ron
2018 J jnl
On the Testability of Graph Partition Properties.
Electron. Colloquium Comput. Complex.
Yonatan Nakar, Dana Ron
2018 A* conf
Property Testing of Planarity in the CONGEST model.
PODC
Reut Levi, Moti Medina, Dana Ron
2018 J jnl
Property Testing of Planarity in the CONGEST model.
CoRR
Reut Levi, Moti Medina, Dana Ron
2018 A* conf
Provable and Practical Approximations for the Degree Distribution using Sublinear Graph Samples.
WWW
Talya Eden, Shweta Jain, Ali Pinar, Dana Ron, C. Seshadhri
2018 A* conf
Testing bounded arboricity.
SODA
Talya Eden, Reut Levi, Dana Ron
2018 J jnl
The Subgraph Testing Model.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2018 A* conf
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism.
SODA
Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron
2017 J jnl
Approximately Counting Triangles in Sublinear Time.
SIAM J. Comput.
Talya Eden, Amit Levi, Dana Ron, C. Seshadhri
2017 J jnl
Constructing near spanning trees with few local inspections.
Random Struct. Algorithms
Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira
2017 J jnl
On Approximating the Number of $k$-cliques in Sublinear Time.
CoRR
Talya Eden, Dana Ron, C. Seshadhri
2017 J jnl
On Learning and Testing Dynamic Environments.
J. ACM
Oded Goldreich, Dana Ron
2017 J jnl
Provable and practical approximations for the degree distribution using sublinear graph samples.
CoRR
Talya Eden, Shweta Jain, Ali Pinar, Dana Ron, C. Seshadhri
2017 A* conf
Sublinear Time Estimation of Degree Distribution Moments: The Degeneracy Connection.
ICALP
Talya Eden, Dana Ron, C. Seshadhri
2017 J jnl
Testing bounded arboricity.
CoRR
Talya Eden, Reut Levi, Dana Ron
2016 — conf
A Local Algorithm for Constructing Spanners in Minor-Free Graphs.
APPROX-RANDOM
Reut Levi, Dana Ron, Ronitt Rubinfeld
2016 J jnl
A Local Algorithm for Constructing Spanners in Minor-Free Graphs.
CoRR
Reut Levi, Dana Ron, Ronitt Rubinfeld
2016 — ch.
Estimating Simple Graph Parameters in Sublinear Time.
Encyclopedia of Algorithms
Oded Goldreich, Dana Ron
2016 J jnl
On Sample-Based Testers.
ACM Trans. Comput. Theory
Oded Goldreich, Dana Ron
2016 J jnl
Sublinear Time Estimation of Degree Distribution Moments: The Arboricity Connection.
CoRR
Talya Eden, Dana Ron, C. Seshadhri
2016 — ch.
Testing Bipartiteness in the Dense-Graph Model.
Encyclopedia of Algorithms
Oded Goldreich, Dana Ron
2016 — ch.
Testing Bipartiteness of Graphs in Sublinear Time.
Encyclopedia of Algorithms
Oded Goldreich, Dana Ron
2016 J jnl
The Power of an Example: Hidden Set Size Approximation Using Group Queries and Conditional Sampling.
ACM Trans. Comput. Theory
Dana Ron, Gilad Tsur
2016 J jnl
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism.
CoRR
Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron
2016 J jnl
Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism.
Electron. Colloquium Comput. Complex.
Eric Blais, Clément L. Canonne, Talya Eden, Amit Levi, Dana Ron
2015 J jnl
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor.
ACM Trans. Algorithms
Reut Levi, Dana Ron
2015 A* conf
Approximately Counting Triangles in Sublinear Time.
FOCS
Talya Eden, Amit Levi, Dana Ron, C. Seshadhri
2015 J jnl
Approximately Counting Triangles in Sublinear Time.
CoRR
Talya Eden, Amit Levi, Dana Ron
2015 J jnl
Approximately Counting Triangles in Sublinear Time.
Electron. Colloquium Comput. Complex.
Talya Eden, Amit Levi, Dana Ron
2015 J jnl
Constructing Near Spanning Trees with Few Local Inspections.
CoRR
Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira
2015 J jnl
Constructing Near Spanning Trees with Few Local Inspections.
Electron. Colloquium Comput. Complex.
Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira
2015 Misc conf
Distributed Maximum Matching in Bounded Degree Graphs.
ICDCN
Guy Even, Moti Medina, Dana Ron
2015 J jnl
Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities.
Algorithmica
Dana Ron, Rocco A. Servedio
2015 A conf
On Sample-Based Testers.
ITCS
Oded Goldreich, Dana Ron
2015 J jnl
Testing Probability Distributions using Conditional Samples.
SIAM J. Comput.
Clément L. Canonne, Dana Ron, Rocco A. Servedio
2014 J jnl
Best of Two Local Models: Local Centralized and Local Distributed Algorithms.
CoRR
Guy Even, Moti Medina, Dana Ron
2014 A conf
Deterministic Stateless Centralized Local Algorithms for Bounded Degree Graphs.
ESA
Guy Even, Moti Medina, Dana Ron
2014 J jnl
Distributed Maximum Matching in Bounded Degree Graphs.
CoRR
Guy Even, Moti Medina, Dana Ron
2014 J jnl
Finding cycles and trees in sublinear time.
Random Struct. Algorithms
Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler
2014 — conf
Local Algorithms for Sparse Spanning Graphs.
APPROX-RANDOM
Reut Levi, Dana Ron, Ronitt Rubinfeld
2014 J jnl
Local Algorithms for Sparse Spanning Graphs.
CoRR
Reut Levi, Dana Ron, Ronitt Rubinfeld
2014 A* conf
On Learning and Testing Dynamic Environments.
FOCS
Oded Goldreich, Dana Ron
2014 J jnl
On Learning and Testing Dynamic Environments.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2014 J jnl
Testing Properties of Sparse Images.
ACM Trans. Algorithms
Dana Ron, Gilad Tsur
2014 J jnl
Testing Similar Means.
SIAM J. Discret. Math.
Reut Levi, Dana Ron, Ronitt Rubinfeld
2014 A* conf
Testing equivalence between distributions using conditional samples.
SODA
Clément L. Canonne, Dana Ron, Rocco A. Servedio
2014 J jnl
The Power of an Example: Hidden Set Size Approximation Using Group Queries and Conditional Sampling.
CoRR
Dana Ron, Gilad Tsur
2013 J jnl
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor
CoRR
Reut Levi, Dana Ron
2013 — conf
A Quasi-Polynomial Time Partition Oracle for Graphs with an Excluded Minor.
ICALP (1)
Reut Levi, Dana Ron
2013 B conf
A Simple Online Competitive Adaptation of Lempel-Ziv Compression with Efficient Random Access Support.
DCC
Akashnil Dutta, Reut Levi, Dana Ron, Ronitt Rubinfeld
2013 J jnl
A simple online competitive adaptation of Lempel-Ziv compression with efficient random access support
CoRR
Akashnil Dutta, Reut Levi, Dana Ron, Ronitt Rubinfeld
2013 J jnl
Comparing the strength of query types in property testing: The case of k-colorability.
Comput. Complex.
Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron
2013 A* conf
Exponentially Improved Algorithms and Lower Bounds for Testing Signed Majorities.
SODA
Dana Ron, Rocco A. Servedio
2013 J jnl
Exponentially improved algorithms and lower bounds for testing signed majorities.
Electron. Colloquium Comput. Complex.
Dana Ron, Rocco A. Servedio
2013 J jnl
On Approximating the Number of Relevant Variables in a Function.
ACM Trans. Comput. Theory
Dana Ron, Gilad Tsur
2013 J jnl
On Sample-Based Testers.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2013 A conf
On the possibilities and limitations of pseudodeterministic algorithms.
ITCS
Oded Goldreich, Shafi Goldwasser, Dana Ron
2013 J jnl
Sublinear Algorithms for Approximating String Compressibility.
Algorithmica
Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith
2013 J jnl
Testing Properties of Collections of Distributions.
Theory Comput.
Reut Levi, Dana Ron, Ronitt Rubinfeld
2012 A* conf
A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size.
SODA
Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld
2012 J jnl
Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity.
ACM Trans. Comput. Theory
Dana Ron, Ronitt Rubinfeld, Muli Safra, Alex Samorodnitsky, Omri Weinstein
2012 J jnl
Finding Cycles and Trees in Sublinear Time.
Electron. Colloquium Comput. Complex.
Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler
2012 J jnl
On the possibilities and limitations of pseudodeterministic algorithms.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Shafi Goldwasser, Dana Ron
2012 — conf
Testing Similar Means.
ICALP (1)
Reut Levi, Dana Ron, Ronitt Rubinfeld
2012 J jnl
Testing Similar Means.
Electron. Colloquium Comput. Complex.
Reut Levi, Dana Ron, Ronitt Rubinfeld
2012 J jnl
Testing computability by width-two OBDDs.
Theor. Comput. Sci.
Dana Ron, Gilad Tsur
2012 J jnl
Testing probability distributions using conditional samples
CoRR
Clément L. Canonne, Dana Ron, Rocco A. Servedio
2012 J jnl
Testing probability distributions using conditional samples.
Electron. Colloquium Comput. Complex.
Clément L. Canonne, Dana Ron, Rocco A. Servedio
2011 J jnl
A Near-Optimal Sublinear-Time Algorithm for Approximating the Minimum Vertex Cover Size
CoRR
Krzysztof Onak, Dana Ron, Michal Rosen, Ronitt Rubinfeld
2011 J jnl
Algorithmic Aspects of Property Testing in the Dense Graphs Model.
SIAM J. Comput.
Oded Goldreich, Dana Ron
2011 — conf
Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity.
APPROX-RANDOM
Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein
2011 J jnl
Approximating the Influence of a monotone Boolean function in O(\sqrt{n}) query complexity
CoRR
Dana Ron, Ronitt Rubinfeld, Muli Safra, Omri Weinstein
2011 J jnl
Counting Stars and Other Small Subgraphs in Sublinear-Time.
SIAM J. Discret. Math.
Mira Gonen, Dana Ron, Yuval Shavitt
2011 J jnl
Distribution-Free Testing for Monomials with a Sublinear Number of Queries.
Theory Comput.
Elya Dolev, Dana Ron
2011 — conf
On Approximating the Number of Relevant Variables in a Function.
APPROX-RANDOM
Dana Ron, Gilad Tsur
2011 J jnl
On Approximating the Number of Relevant Variables in a Function.
Electron. Colloquium Comput. Complex.
Dana Ron, Gilad Tsur
2011 J jnl
On Proximity-Oblivious Testing.
SIAM J. Comput.
Oded Goldreich, Dana Ron
2011 — ch.
On Testing Expansion in Bounded-Degree Graphs.
Studies in Complexity and Cryptography
Oded Goldreich, Dana Ron
2011 J jnl
Testing Computability by Width-Two OBDDs.
Electron. Colloquium Comput. Complex.
Dana Ron, Gilad Tsur
2011 J jnl
Testing Eulerianity and connectivity in directed sparse graphs.
Theor. Comput. Sci.
Yaron Orenstein, Dana Ron
2011 A conf
Testing Properties of Collections of Distributions.
ICS
Reut Levi, Dana Ron, Ronitt Rubinfeld
2010 — ch.
Algorithmic Aspects of Property Testing in the Dense Graphs Model.
Property Testing
Oded Goldreich, Dana Ron
2010 J jnl
Approximating the distance to monotonicity in high dimensions.
ACM Trans. Algorithms
Shahar Fattal, Dana Ron
2010 — ch.
Comparing the Strength of Query Types in Property Testing: The Case of Testing
Property Testing
Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron
2010 A* conf
Counting Stars and Other Small Subgraphs in Sublinear Time.
SODA
Mira Gonen, Dana Ron, Yuval Shavitt
2010 — conf
Distribution-Free Testing Algorithms for Monomials with a Sublinear Number of Queries.
APPROX-RANDOM
Elya Dolev, Dana Ron
2010 J jnl
Finding Cycles and Trees in Sublinear Time
CoRR
Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler
2010 J jnl
On the Benefits of Adaptivity in Property Testing of Dense Graphs.
Algorithmica
Mira Gonen, Dana Ron
2010 C conf
Testing Computability by Width-2 OBDDs Where the Variable Order is Unknown.
CIAC
Dana Ron, Gilad Tsur
2010 J jnl
Testing Properties of Collections of Distributions.
Electron. Colloquium Comput. Complex.
Reut Levi, Dana Ron, Ronitt Rubinfeld
2010 A* conf
Testing Properties of Sparse Images.
FOCS
Gilad Tsur, Dana Ron
2009 — conf
Algorithmic Aspects of Property Testing in the Dense Graphs Model.
APPROX-RANDOM
Oded Goldreich, Dana Ron
2009 J jnl
Algorithmic and Analysis Techniques in Property Testing.
Found. Trends Theor. Comput. Sci.
Dana Ron
2009 J jnl
Approximating the distance to properties in bounded-degree and general sparse graphs.
ACM Trans. Algorithms
Sharon Marko, Dana Ron
2009 J jnl
Counting Stars and Other Small Subgraphs in Sublinear Time.
Electron. Colloquium Comput. Complex.
Dana Ron, Mira Gonen, Yuval Shavitt
2009 A* conf
On proximity oblivious testing.
STOC
Oded Goldreich, Dana Ron
2009 J jnl
Scheduling with conflicts: online and offline algorithms.
J. Sched.
Guy Even, Magnús M. Halldórsson, Lotem Kaplan, Dana Ron
2009 J jnl
Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem.
SIAM J. Comput.
Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam D. Smith
2009 — conf
Testing Computability by Width Two OBDDs.
APPROX-RANDOM
Dana Ron, Gilad Tsur
2008 J jnl
Algorithmic Aspects of Property Testing in the Dense Graphs Model.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2008 J jnl
Approximating average parameters of graphs.
Random Struct. Algorithms
Oded Goldreich, Dana Ron
2008 A* conf
Comparing the strength of query types in property testing: the case of testing
SODA
Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron
2008 J jnl
Finding a dense-core in Jellyfish graphs.
Comput. Networks
Mira Gonen, Dana Ron, Udi Weinsberg, Avishai Wool
2008 J jnl
On Proximity Oblivious Testing.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2008 J jnl
Property Testing: A Learning Theory Perspective.
Found. Trends Mach. Learn.
Dana Ron
2008 J jnl
Testing Triangle-Freeness in General Graphs.
SIAM J. Discret. Math.
Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron
2007 J jnl
Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms.
Theor. Comput. Sci.
Michal Parnas, Dana Ron
2007 C conf
Finding a Dense-Core in Jellyfish Graphs.
WAW
Mira Gonen, Dana Ron, Udi Weinsberg, Avishai Wool
2007 — conf
On the Benefits of Adaptivity in Property Testing of Dense Graphs.
APPROX-RANDOM
Mira Gonen, Dana Ron
2007 A* conf
Property Testing: A Learning Theory Perspective.
COLT
Dana Ron
2007 A* conf
Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem.
FOCS
Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam D. Smith
2007 J jnl
Sublinear Algorithms for Approximating String Compressibility
CoRR
Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith
2007 — conf
Sublinear Algorithms for Approximating String Compressibility.
APPROX-RANDOM
Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Adam D. Smith
2007 J jnl
The hardness of the Expected Decision Depth problem.
Inf. Process. Lett.
Dana Ron, Amir Rosenfeld, Salil P. Vadhan
2006 — conf
Approximating Average Parameters of Graphs.
APPROX-RANDOM
Oded Goldreich, Dana Ron
2006 — conf
Distance Approximation in Bounded-Degree and General Sparse Graphs.
APPROX-RANDOM
Sharon Marko, Dana Ron
2006 J jnl
Testing Polynomials over General Fields.
SIAM J. Comput.
Tali Kaufman, Dana Ron
2006 A* conf
Testing triangle-freeness in general graphs.
SODA
Noga Alon, Tali Kaufman, Michael Krivelevich, Dana Ron
2006 J jnl
Tolerant property testing and distance approximation.
J. Comput. Syst. Sci.
Michal Parnas, Dana Ron, Ronitt Rubinfeld
2005 J jnl
A characterization of low-weight words that span generalized reed-muller codes.
IEEE Trans. Inf. Theory
Tali Kaufman, Dana Ron
2005 — conf
Approximating Average Parameters of Graphs.
Sublinear Algorithms
Oded Goldreich, Dana Ron
2005 J jnl
Approximating Average Parameters of Graphs.
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2005 J jnl
On Approximating the Minimum Vertex Cover in Sublinear Time and the Connection to Distributed Algorithms
Electron. Colloquium Comput. Complex.
Michal Parnas, Dana Ron
2005 J jnl
Sublinear Algorithms for Approximating String Compressibility and the Distribution Support Size
Electron. Colloquium Comput. Complex.
Sofya Raskhodnikova, Dana Ron, Ronitt Rubinfeld, Amir Shpilka, Adam D. Smith
2005 J jnl
Testing Reed-Muller codes.
IEEE Trans. Inf. Theory
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
2004 J jnl
A New Conceptual Clustering Framework.
Mach. Learn.
Nina Mishra, Dana Ron, Ram Swaminathan
2004 — ed.
Approximation, Randomization, and Combinatorial Optimization, Algorithms and Techniques, 7th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2004, and 8th International Workshop on Randomization and Computation, RANDOM 2004, Cambridge, MA, USA, August 22-24, 2004, Proceedings
APPROX-RANDOM
Klaus Jansen, Sanjeev Khanna, José D. P. Rolim, Dana Ron
2004 J jnl
On Estimating the Average Degree of a Graph
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2004 A* conf
Testing Polynomials over General Fields.
FOCS
Tali Kaufman, Dana Ron
2004 J jnl
Testing juntas.
J. Comput. Syst. Sci.
Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky
2004 J jnl
Testing of Clustering.
SIAM Rev.
Noga Alon, Seannie Dar, Michal Parnas, Dana Ron
2004 J jnl
Tight Bounds for Testing Bipartiteness in General Graphs.
SIAM J. Comput.
Tali Kaufman, Michael Krivelevich, Dana Ron
2004 J jnl
Tolerant Property Testing and Distance Approximation
Electron. Colloquium Comput. Complex.
Michal Parnas, Dana Ron, Ronitt Rubinfeld
2003 J jnl
Bounds on Linear Codes for Network Multicast
Electron. Colloquium Comput. Complex.
Meir Feder, Dana Ron, Ami Tavory
2003 J jnl
Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks.
SIAM J. Comput.
Guy Even, Zvi Lotker, Dana Ron, Shakhar Smorodinsky
2003 A* conf
On Finding Large Conjunctive Clusters.
COLT
Nina Mishra, Dana Ron, Ram Swaminathan
2003 J jnl
On Testing Convexity and Submodularity.
SIAM J. Comput.
Michal Parnas, Dana Ron, Ronitt Rubinfeld
2003 — conf
Testing Low-Degree Polynomials over GF(2(.
RANDOM-APPROX
Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, Dana Ron
2003 J jnl
Testing membership in parenthesis languages.
Random Struct. Algorithms
Michal Parnas, Dana Ron, Ronitt Rubinfeld
2003 J jnl
Testing metric properties.
Inf. Comput.
Michal Parnas, Dana Ron
2003 J jnl
Testing of Clustering.
SIAM J. Discret. Math.
Noga Alon, Seannie Dar, Michal Parnas, Dana Ron
2003 — conf
Tight Bounds for Testing Bipartiteness in General Graphs.
RANDOM-APPROX
Tali Kaufman, Michael Krivelevich, Dana Ron
2002 A* conf
Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks.
FOCS
Guy Even, Zvi Lotker, Dana Ron, Shakhar Smorodinsky
2002 — conf
On Testing Convexity and Submodularity.
RANDOM
Michal Parnas, Dana Ron, Ronitt Rubinfeld
2002 J jnl
Property Testing in Bounded Degree Graphs.
Algorithmica
Oded Goldreich, Dana Ron
2002 J jnl
Testing Basic Boolean Formulae.
SIAM J. Discret. Math.
Michal Parnas, Dana Ron, Alex Samorodnitsky
2002 A* conf
Testing Juntas.
FOCS
Eldar Fischer, Guy Kindler, Dana Ron, Shmuel Safra, Alex Samorodnitsky
2002 J jnl
Testing properties of directed graphs: acyclicity and connectivity.
Random Struct. Algorithms
Michael A. Bender, Dana Ron
2002 J jnl
Testing the diameter of graphs.
Random Struct. Algorithms
Michal Parnas, Dana Ron
2002 J jnl
The Power of a Pebble: Exploring and Mapping Directed Graphs.
Inf. Comput.
Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, Salil P. Vadhan
2001 J jnl
Errata for: "On randomized one-round communication complexity".
Comput. Complex.
Ilan Kremer, Noam Nisan, Dana Ron
2001 J jnl
On Disjoint Chains of Subsets.
J. Comb. Theory A
Eric Lehman, Dana Ron
2001 J jnl
Proclaiming Dictators and Juntas or Testing Boolean Formulae
Electron. Colloquium Comput. Complex.
Michal Parnas, Dana Ron, Alex Samorodnitsky
2001 — conf
Proclaiming Dictators and Juntas or Testing Boolean Formulae.
RANDOM-APPROX
Michal Parnas, Dana Ron, Alex Samorodnitsky
2001 — conf
Testing Parenthesis Languages.
RANDOM-APPROX
Michal Parnas, Dana Ron, Ronitt Rubinfeld
2001 A* conf
Testing metric properties.
STOC
Michal Parnas, Dana Ron
2000 J jnl
Chinese remaindering with errors.
IEEE Trans. Inf. Theory
Oded Goldreich, Dana Ron, Madhu Sudan
2000 J jnl
On Testing Expansion in Bounded-Degree Graphs
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron
2000 A* conf
Testing Acyclicity of Directed Graphs in Sublinear Time.
ICALP
Michael A. Bender, Dana Ron
2000 J jnl
Testing Monotonicity.
Comb.
Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron, Alex Samorodnitsky
2000 J jnl
Testing Problems with Sublearning Sample Complexity.
J. Comput. Syst. Sci.
Michael J. Kearns, Dana Ron
2000 A* conf
Testing of Clustering.
FOCS
Noga Alon, Seannie Dar, Michal Parnas, Dana Ron
1999 J jnl
A Sublinear Bipartiteness Tester for Bounded Degree Graphs.
Comb.
Oded Goldreich, Dana Ron
1999 J jnl
Algorithmic Stability and Sanity-Check Bounds for Leave-One-Out Cross-Validation.
Neural Comput.
Michael J. Kearns, Dana Ron
1999 A* conf
Chinese Remaindering with Errors.
STOC
Oded Goldreich, Dana Ron, Madhu Sudan
1999 J jnl
Chinese Remaindering with Errors.
IACR Cryptol. ePrint Arch.
Oded Goldreich, Dana Ron, Madhu Sudan
1999 J jnl
Computational Sample Complexity.
SIAM J. Comput.
Scott E. Decatur, Oded Goldreich, Dana Ron
1999 — conf
Improved Testing Algorithms for Monotonicity.
RANDOM-APPROX
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky
1999 J jnl
Improved Testing Algorithms for Monotonicity.
Electron. Colloquium Comput. Complex.
Yevgeniy Dodis, Oded Goldreich, Eric Lehman, Sofya Raskhodnikova, Dana Ron, Alex Samorodnitsky
1999 J jnl
On Randomized One-Round Communication Complexity.
Comput. Complex.
Ilan Kremer, Noam Nisan, Dana Ron
1999 — conf
Testing the Diameter of Graphs.
RANDOM-APPROX
Michal Parnas, Dana Ron
1998 A* conf
A Sublinear Bipartiteness Tester for Bunded Degree Graphs.
STOC
Oded Goldreich, Dana Ron
1998 J jnl
Chinese Remaindering with Errors
Electron. Colloquium Comput. Complex.
Oded Goldreich, Dana Ron, Madhu Sudan
1998 J jnl
Guest Editor's Introduction.
Mach. Learn.
Dana Ron
1998 J jnl
On the Learnability and Usage of Acyclic Probabilistic Finite Automata.
J. Comput. Syst. Sci.
Dana Ron, Yoram Singer, Naftali Tishby
1998 J jnl
Property Testing and its Connection to Learning and Approximation.
J. ACM
Oded Goldreich, Shafi Goldwasser, Dana Ron
1998 A* conf
Testing Monotonicity.
FOCS
Oded Goldreich, Shafi Goldwasser, Eric Lehman, Dana Ron
1998 A* conf
Testing Problems with Sub-Learning Sample Complexity.
COLT
Michael J. Kearns, Dana Ron
1998 A* conf
The Power of a Pebble: Exploring and Mapping Directed Graphs.
STOC
Michael A. Bender, Antonio Fernández, Dana Ron, Amit Sahai, Salil P. Vadhan
1997 J jnl
A Probabilistic Error-Correcting Scheme.
IACR Cryptol. ePrint Arch.
Scott E. Decatur, Oded Goldreich, Dana Ron
1997 A* conf
Algorithmic Stability and Sanity-Check Bounds for Leave-one-Out Cross-Validation.
COLT
Michael J. Kearns, Dana Ron
1997 J jnl
An Experimental and Theoretical Comparison of Model Selection Methods.
Mach. Learn.
Michael J. Kearns, Yishay Mansour, Andrew Y. Ng, Dana Ron
1997 J jnl
Computational Sample Complexity
Electron. Colloquium Comput. Complex.
Scott E. Decatur, Oded Goldreich, Dana Ron
1997 A* conf
Computational Sample Complexity.
COLT
Scott E. Decatur, Oded Goldreich, Dana Ron
1997 J jnl
Efficient Learning of Typical Finite Automata from Random Walks.
Inf. Comput.
Yoav Freund, Michael J. Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie
1997 J jnl
Exactly Learning Automata of Small Cover Time.
Mach. Learn.
Dana Ron, Ronitt Rubinfeld
1997 J jnl
On Universal Learning Algorithms.
Inf. Process. Lett.
Oded Goldreich, Dana Ron
1997 A* conf
Property Testing in Bounded Degree Graphs.
STOC
Oded Goldreich, Dana Ron
1996 J jnl
Agreement in the Presence of Faults, on Networks of Bounded Degree.
Inf. Process. Lett.
Michael Ben-Or, Dana Ron
1996 A* conf
Property Testing and Its Connection to Learning and Approximation.
FOCS
Oded Goldreich, Shafi Goldwasser, Dana Ron
1996 J jnl
Property Testing and its connection to Learning and Approximation
Electron. Colloquium Comput. Complex.
Oded Goldreich, Shafi Goldwasser, Dana Ron
1996 J jnl
The Power of Amnesia: Learning Probabilistic Automata with Variable Memory Length.
Mach. Learn.
Dana Ron, Yoram Singer, Naftali Tishby
1995 A* conf
An Experimental and Theoretical Comparison of Model Selection Methods.
COLT
Michael J. Kearns, Yishay Mansour, Andrew Y. Ng, Dana Ron
1995 — —
Automata learning and its applications.
Dana Ron
1995 A* conf
Efficient Algorithms for Learning to Play Repeated Games Against Computationally Bounded Adversaries.
FOCS
Yoav Freund, Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire
1995 A* conf
Exactly Learning Automata with Small Cover Time.
COLT
Dana Ron, Ronitt Rubinfeld
1995 J jnl
Learning Fallible Deterministic Finite Automata.
Mach. Learn.
Dana Ron, Ronitt Rubinfeld
1995 A* conf
Learning to Model Sequences Generated by Switching Distributions.
COLT
Yoav Freund, Dana Ron
1995 A* conf
On randomized one-round communication complexity.
STOC
Ilan Kremer, Noam Nisan, Dana Ron
1995 A* conf
On the Learnability and Usage of Acyclic Probabilistic Finite Automata.
COLT
Dana Ron, Yoram Singer, Naftali Tishby
1994 A* conf
Learning Probabilistic Automata with Variable Memory Length.
COLT
Dana Ron, Yoram Singer, Naftali Tishby
1994 A* conf
On the learnability of discrete distributions.
STOC
Michael J. Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie
1993 A* conf
Efficient learning of typical finite automata from random walks.
STOC
Yoav Freund, Michael J. Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, Linda Sellie
1993 A* conf
Learning Fallible Finite State Automata.
COLT
Dana Ron, Ronitt Rubinfeld
1993 — conf
The Power of Amnesia.
NIPS
Dana Ron, Yoram Singer, Naftali Tishby