Search results for "property testing"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
4	Oded Goldreich, Shafi Goldwasser, Dana Ron	Property Testing and Its Connection to Learning and Approximation.	FOCS	1996	DBLP DOI BibTeX RDF	unknown function, property testing algorithm, graph property testing, k-colorable graph, /spl rho/-clique, input graph, testing, approximation, querying, assertions, probabilistic algorithm, learning theory, property testing
3	Oded Goldreich, Dana Ron	Algorithmic Aspects of Property Testing in the Dense Graphs Model.	Property Testing	2010	DBLP DOI BibTeX RDF
3	Oded Goldreich	A Brief Introduction to Property Testing.	Property Testing	2010	DBLP DOI BibTeX RDF
3	Ilan Newman	Property Testing of Massively Parametrized Problems - A Survey.	Property Testing	2010	DBLP DOI BibTeX RDF
3	Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg	Hierarchy Theorems for Property Testing.	Property Testing	2010	DBLP DOI BibTeX RDF
3	Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron	Comparing the Strength of Query Types in Property Testing: The Case of Testing k-Colorability.	Property Testing	2010	DBLP DOI BibTeX RDF
3	Madhu Sudan	Invariance in Property Testing.	Property Testing	2010	DBLP DOI BibTeX RDF
3	Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg	Hierarchy Theorems for Property Testing.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF	Monotone Graph Properties, Graph Blow-up, One-Sided vs Two-Sided Error, Adaptivity vs Non-adaptivity, Property Testing, Graph Properties
3	Sophie Laplante, Richard Lassaigne, Frédéric Magniez, Sylvain Peyronnet, Michel de Rougemont	Probabilistic abstraction for model checking: An approach based on property testing.	ACM Trans. Comput. Log.	2007	DBLP DOI BibTeX RDF	Approximate verification, probabilistic abstraction, model checking, property testing, probabilistic verification
2	Oded Goldreich (eds.)	Property Testing - Current Research and Surveys [outgrow of a workshop at the Institute for Computer Science (ITCS) at Tsinghua University, January 2010]	Property Testing	2010	DBLP DOI BibTeX RDF
2	Eric Blais	Testing Juntas: A Brief Survey.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Oded Goldreich	The Program of the Mini-Workshop.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Irit Dinur, Prahladh Harsha	Composition of Low-Error 2-Query PCPs Using Decodable PCPs.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Victor Chen	Query-Efficient Dictatorship Testing with Perfect Completeness.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Krzysztof Onak	Sublinear Graph Approximation Algorithms.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak	Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Alexandr Andoni, Piotr Indyk, Krzysztof Onak, Ronitt Rubinfeld	Sublinear Algorithms in the External Memory Model.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Swastik Kopparty, Shubhangi Saraf	Some Recent Results on Local Testing of Sparse Linear Codes.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Oded Goldreich	Short Locally Testable Codes and Proofs: A Survey in Two Parts.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Rocco A. Servedio	Testing by Implicit Learning: A Brief Survey.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Oded Goldreich	Introduction to Testing Graph Properties.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Sofya Raskhodnikova	Transitive-Closure Spanners: A Survey.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio	Testing (Subclasses of) Halfspaces.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Krzysztof Onak, Ronitt Rubinfeld	Dynamic Approximate Vertex Cover and Maximum Matching.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Arnab Bhattacharyya, Swastik Kopparty, Grant Schoenebeck, Madhu Sudan, David Zuckerman	Optimal Testing of Reed-Muller Codes.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Michal Adamaszek, Artur Czumaj, Christian Sohler	Testing Monotone Continuous Distributions on High-Dimensional Real Cubes.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Noga Alon	On Constant Time Approximation of Parameters of Bounded Degree Graphs.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Michael Saks, C. Seshadhri	Local Property Reconstruction and Monotonicity.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Tali Kaufman, Avi Wigderson	Symmetric LDPC Codes and Local Testing.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Artur Czumaj, Christian Sohler	Sublinear-time Algorithms.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Eli Ben-Sasson	Limitation on the Rate of Families of Locally Testable Codes.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie	Testing Linear-Invariant Non-linear Properties: A Short Report.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Asaf Shapira	Green's Conjecture and Testing Linear Invariant Properties.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Frank Hellweg, Melanie Schmidt, Christian Sohler	Testing Euclidean Spanners.	Property Testing	2010	DBLP DOI BibTeX RDF
2	Zvika Brakerski, Boaz Patt-Shamir	Distributed discovery of large near-cliques.	PODC	2009	DBLP DOI BibTeX RDF	randomized algorithms, communication networks, property testing, clique
2	Charles Jordan, Thomas Zeugmann	Relational Properties Expressible with One Universal Quantifier Are Testable.	SAGA	2009	DBLP DOI BibTeX RDF	logic, property testing
2	Ido Ben-Eliezer, Tali Kaufman, Michael Krivelevich, Dana Ron	Comparing the strength of query types in property testing: the case of testing k-colorability.	SODA	2008	DBLP DOI BibTeX RDF
2	Yoshifumi Inui, François Le Gall	Quantum Property Testing of Group Solvability.	LATIN	2008	DBLP DOI BibTeX RDF
2	Tali Kaufman, Madhu Sudan	Algebraic property testing: the role of invariance.	STOC	2008	DBLP DOI BibTeX RDF	error-correcting codes, locally testable codes, sublinear time algorithms
2	László Lovász	Some Mathematics Behind Graph Property Testing.	Discovery Science	2008	DBLP DOI BibTeX RDF
2	Itai Benjamini, Oded Schramm, Asaf Shapira	Every minor-closed property of sparse graphs is testable.	STOC	2008	DBLP DOI BibTeX RDF	minor closed properties, graph algorithms, property testing
2	Artur Czumaj, Christian Sohler	Testing Euclidean minimum spanning trees in the plane.	ACM Transactions on Algorithms	2008	DBLP DOI BibTeX RDF	Euclidean minimum spanning tree, randomized algorithms, property testing
2	Elena Grigorescu, Tali Kaufman, Madhu Sudan	2-Transitivity Is Insufficient for Local Testability.	IEEE Conference on Computational Complexity	2008	DBLP DOI BibTeX RDF	error correcting codes, property testing, sublinear time algorithms
2	Shirley Halevy, Eyal Kushilevitz	Distribution-Free Connectivity Testing for Sparse Graphs.	Algorithmica	2008	DBLP DOI BibTeX RDF	Distribution-free testing, Connectivity testing, Properties of sparse graphs, Property testing
2	Frédéric Magniez, Michel de Rougemont	Property Testing of Regular Tree Languages.	Algorithmica	2007	DBLP DOI BibTeX RDF	Edit distance with moves, Property testing, Regular trees languages
2	Oded Goldreich, Or Sheffet	On the Randomness Complexity of Property Testing.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF
2	Mira Gonen, Dana Ron	On the Benefits of Adaptivity in Property Testing of Dense Graphs.	APPROX-RANDOM	2007	DBLP DOI BibTeX RDF
2	Dana Ron	Property Testing: A Learning Theory Perspective.	COLT	2007	DBLP DOI BibTeX RDF
2	Vojtech Rödl, Mathias Schacht	Property testing in hypergraphs and the removal lemma.	STOC	2007	DBLP DOI BibTeX RDF	hereditary properties, removal lemma, hypergraphs, property testing, regularity lemma
2	Hesham Hallal, Sergiy Boroday, Alexandre Petrenko, Andreas Ulrich	A formal approach to property testing in causally consistent distributed traces.	Formal Asp. Comput.	2006	DBLP DOI BibTeX RDF	Distributed systems, Monitoring, SDL, Trace analysis, System validation, Passive testing
2	Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira	A combinatorial characterization of the testable graph properties: it's all about regularity.	STOC	2006	DBLP DOI BibTeX RDF	characterization, property testing, regularity lemma
2	Nir Ailon, Bernard Chazelle	Information Theory in Property Testing and Monotonicity Testing in Higher Dimension.	STACS	2005	DBLP DOI BibTeX RDF
2	Beate Bollig	Property Testing and the Branching Program Size of Boolean Functions.	FCT	2005	DBLP DOI BibTeX RDF
2	Noga Alon, Asaf Shapira	Every monotone graph property is testable.	STOC	2005	DBLP DOI BibTeX RDF	monotone properties, property testing, regularity lemma
2	Eldar Fischer, Ilan Newman	Testing versus estimation of graph properties.	STOC	2005	DBLP DOI BibTeX RDF	property testing, regularity lemma, graph properties, distance approximation
2	Harry Buhrman, Lance Fortnow, Ilan Newman, Hein Röhrig	Quantum property testing.	SODA	2003	DBLP DOI BibTeX RDF
2	Hesham Hallal, Sergiy Boroday, Andreas Ulrich, Alexandre Petrenko	An Automata-Based Approach to Property Testing in Event Traces.	TestCom	2003	DBLP DOI BibTeX RDF	distributed traces, monitoring, SDL, passive testing, property checking
2	Shirley Halevy, Eyal Kushilevitz	Distribution-Free Property Testing.	RANDOM-APPROX	2003	DBLP DOI BibTeX RDF
2	Oded Goldreich, Dana Ron	Property Testing in Bounded Degree Graphs.	Algorithmica	2002	DBLP DOI BibTeX RDF	Approximation algorithms, Randomized algorithms, Graph algorithms, Property testing
2	Sophie Laplante, Richard Lassaigne, Frédéric Magniez, Sylvain Peyronnet, Michel de Rougemont	Probabilistic Abstraction for Model Checking: An Approach Based on Property Testing.	LICS	2002	DBLP DOI BibTeX RDF
2	Eldar Fischer, Eric Lehman, Ilan Newman, Sofya Raskhodnikova, Ronitt Rubinfeld, Alex Samorodnitsky	Monotonicity testing over general poset domains.	STOC	2002	DBLP DOI BibTeX RDF	algorithms, property testing, monotone functions
2	Artur Czumaj, Christian Sohler	Property Testing with Geometric Queries.	ESA	2001	DBLP DOI BibTeX RDF
2	Eldar Fischer, Ilan Newman	Testing of matrix properties.	STOC	2001	DBLP DOI BibTeX RDF	matrix properties, property testing
2	Amit Chakrabarti, Subhash Khot, Yaoyun Shi	Evasiveness of Subgraph Containment and Related Properties.	STACS	2001	DBLP DOI BibTeX RDF	Decision Tree Complexity, Monotone Graph Properties, Graph Property Testing, Evasiveness
2	Artur Czumaj, Christian Sohler, Martin Ziegler	Property Testing in Computational Geometry.	ESA	2000	DBLP DOI BibTeX RDF
1	Yuichi Yoshida, Hiro Ito	Property Testing on k-Vertex-Connectivity of Graphs.	Algorithmica	2012	DBLP DOI BibTeX RDF
1	Oded Goldreich, Michael Krivelevich, Ilan Newman, Eyal Rozenberg	Hierarchy Theorems for Property Testing.	Computational Complexity	2012	DBLP DOI BibTeX RDF
1	László Lovász, Katalin Vesztergombi	Nondeterministic graph property testing	CoRR	2012	DBLP BibTeX RDF
1	Eric Blais, Joshua Brody, Kevin Matulef	Property Testing Lower Bounds via Communication Complexity.	Electronic Colloquium on Computational Complexity (ECCC)	2011	DBLP BibTeX RDF
1	Igor Kleiner, Daniel Keren, Ilan Newman, Oren Ben-Zwi	Applying Property Testing to an Image Partitioning Problem.	IEEE Trans. Pattern Anal. Mach. Intell.	2011	DBLP DOI BibTeX RDF
1	Yoshifumi Inui, François Le Gall	Quantum Property Testing of Group Solvability.	Algorithmica	2011	DBLP DOI BibTeX RDF
1	François Le Gall, Yuichi Yoshida	Property Testing for Cyclic Groups and Beyond	CoRR	2011	DBLP BibTeX RDF
1	Oded Goldreich, Dana Ron	Algorithmic Aspects of Property Testing in the Dense Graphs Model.	SIAM J. Comput.	2011	DBLP DOI BibTeX RDF
1	Oded Goldreich	A Brief Introduction to Property Testing.	Studies in Complexity and Cryptography	2011	DBLP DOI BibTeX RDF
1	Oded Goldreich	On the Average-Case Complexity of Property Testing.	Studies in Complexity and Cryptography	2011	DBLP DOI BibTeX RDF
1	François Le Gall, Yuichi Yoshida	Property Testing for Cyclic Groups and Beyond.	COCOON	2011	DBLP DOI BibTeX RDF
1	Andris Ambainis, Andrew M. Childs, Yi-Kai Liu	Quantum Property Testing for Bounded-Degree Graphs.	APPROX-RANDOM	2011	DBLP DOI BibTeX RDF
1	Victor Chen, Madhu Sudan, Ning Xie	Property Testing via Set-Theoretic Operations.	ICS	2011	DBLP BibTeX RDF
1	Eric Blais, Joshua Brody, Kevin Matulef	Property Testing Lower Bounds via Communication Complexity.	IEEE Conference on Computational Complexity	2011	DBLP DOI BibTeX RDF
1	Mathieu Raffinot	Consecutive Ones Property Testing: Cut or Swap.	CiE	2011	DBLP DOI BibTeX RDF
1	Victor Chen, Madhu Sudan, Ning Xie	Property Testing via Set-Theoretic Operations.	Electronic Colloquium on Computational Complexity (ECCC)	2010	DBLP BibTeX RDF
1	Madhu Sudan	Invariance in Property Testing.	Electronic Colloquium on Computational Complexity (ECCC)	2010	DBLP BibTeX RDF
1	Mira Gonen, Dana Ron	On the Benefits of Adaptivity in Property Testing of Dense Graphs.	Algorithmica	2010	DBLP DOI BibTeX RDF
1	Oded Goldreich, Or Sheffet	On The Randomness Complexity of Property Testing.	Computational Complexity	2010	DBLP BibTeX RDF
1	Andris Ambainis, Andrew M. Childs, Yi-Kai Liu	Quantum property testing for bounded-degree graphs	CoRR	2010	DBLP BibTeX RDF
1	Victor Chen, Madhu Sudan, Ning Xie	Property Testing via Set-Theoretic Operations	CoRR	2010	DBLP BibTeX RDF
1	Sourav Chakraborty, Eldar Fischer, Arie Matsliah, Ronald de Wolf	New Results on Quantum Property Testing	CoRR	2010	DBLP BibTeX RDF
1	Mathieu Raffinot	Consecutive ones property testing: cut or swap	CoRR	2010	DBLP BibTeX RDF
1	Artur Czumaj	Local Graph Exploration and Fast Property Testing.	ESA	2010	DBLP DOI BibTeX RDF
1	Carlos Hoppen, Yoshiharu Kohayakawa, Carlos Gustavo T. de A. Moreira, Rudini Menezes Sampaio	Property Testing and Parameter Testing for Permutations.	SODA	2010	DBLP BibTeX RDF
1	Sourav Chakraborty, Eldar Fischer, Arie Matsliah, Ronald de Wolf	New Results on Quantum Property Testing.	FSTTCS	2010	DBLP DOI BibTeX RDF
1	Swastik Kopparty, Shubhangi Saraf	Local list-decoding and testing of random linear codes from high error.	STOC	2010	DBLP DOI BibTeX RDF	dual-BCH codes, noisy parity, random codes, property testing, list-decoding, sublinear-time algorithms
1	Eric Blais, Ryan O'Donnell	Lower Bounds for Testing Function Isomorphism.	IEEE Conference on Computational Complexity	2010	DBLP DOI BibTeX RDF	lower bounds, Boolean functions, property testing
1	Dana Ron	Algorithmic and Analysis Techniques in Property Testing.	Foundations and Trends in Theoretical Computer Science	2009	DBLP DOI BibTeX RDF
1	Oded Goldreich, Dana Ron	Algorithmic Aspects of Property Testing in the Dense Graphs Model.	APPROX-RANDOM	2009	DBLP DOI BibTeX RDF
1	Eric Blais	Testing juntas nearly optimally.	STOC	2009	DBLP DOI BibTeX RDF	Efron-Stein decomposition, juntas, property testing
1	Oded Goldreich, Dana Ron	On proximity oblivious testing.	STOC	2009	DBLP DOI BibTeX RDF	graph propeties, property testing
1	Asaf Shapira	Green's conjecture and testing linear-invariant properties.	STOC	2009	DBLP DOI BibTeX RDF	hypergraphs removal lemma, boolean functions, property testing
1	Yuichi Yoshida, Masaki Yamamoto, Hiro Ito	An improved constant-time approximation algorithm for maximum~matchings.	STOC	2009	DBLP DOI BibTeX RDF	constant-time approximation algorithms, minimum vertex cover, property testing, maximum matching, minimum set cover
1	Sharon Marko, Dana Ron	Approximating the distance to properties in bounded-degree and general sparse graphs.	ACM Transactions on Algorithms	2009	DBLP DOI BibTeX RDF	Sublinear approximation algorithms, property testing, graph properties, distance approximation