Research graph
References from Property Testing: A Learning Theory Perspective. Local targets link to admitted publications; unresolved targets remain external evidence.
“Information theory in property testing and monotonicity testing in higher dimensions”
10.1016/j.ic.2006.06.001 · 2006 · External reference
“Estimating the distance to a monotone function”
2004 · External reference
“Testing subgraphs of large graphs”
10.1002/rsa.10056 · 2002 · External reference
“Testing k-wise and almost k-wise independence”
10.1145/1250790.1250863 · 2007 · External reference
“Testing of clustering”
10.1137/s0895480102410973 · 2003 · External reference
“The algorithmic aspects of the regularity lemma”
10.1006/jagm.1994.1005 · 1994 · External reference
“Efficient testing of large graphs”
10.1007/s004930070001 · 2000 · External reference
“Testing of bipartite graph properties”
10.1137/050627915 · 2007 · External reference
“A combinatorial characterization of the testable graph properties: It’s all about regularity”
10.1145/1132516.1132555 · 2006 · External reference
“Testing triangle freeness in general graphs”
10.1145/1109557.1109589 · 2006 · External reference
“Testing k-colorability”
10.1137/s0895480199358655 · 2002 · External reference
“Testing Reed-Muller codes”
10.1109/tit.2005.856958 · 2005 · External reference
“Regular languages are testable with a constant number of queries”
10.1137/s0097539700366528 · 2001 · External reference
“Testing satisfiability”
10.1016/s0196-6774(03)00019-1 · 2003 · External reference
“Testing subgraphs in directed graphs”
10.1016/j.jcss.2004.04.008 · 2004 · External reference
“A characterization of easily testable induced subgraphs”
10.1017/s0963548306007759 · 2005 · External reference
“A characterization of the (natural) graph properties testable with one-sided error”
2005 · External reference
“Every monotone graph property is testable”
2005 · External reference
“Linear equations, arithmetic progressions and hypergraph property testing”
10.4086/toc.2005.v001a009 · 2005 · External reference
“Queries and concept learning”
10.1023/a:1022821128753 · 1988 · External reference
“Probabilistic checkable proofs: A new characterization of NP”
10.1145/273865.273901 · 1998 · External reference
“Improved low-degree testing and its applications”
1997 · External reference
“Checking computations in polylogarithmic time”
10.1145/103418.103428 · 1991 · External reference
10.1007/bf01200056 · 1991 · Admitted local publication
“The complexity of approximating the entropy”
10.1137/s0097539702403645 · 2005 · External reference
“A sublinear algorithm for weakly approximating edit distance”
10.1145/780542.780590 · 2003 · External reference
“Testing random variables for independence and identity”
2001 · External reference
“Testing that distributions are close”
10.1109/sfcs.2000.892113 · 2000 · External reference
“Sublinear algorithms for testing monotone and unimodal distributions”
10.1145/1007352.1007414 · 2004 · External reference
“Fast approximate PCPs for multidimensional bin-packing problems”
10.1016/j.ic.2004.10.001 · 2005 · External reference
“Learning functions represented as multiplicity automata”
10.1145/337244.337257 · 2000 · External reference
“Linearity testing over characteristic two”
10.1109/18.556674 · 1996 · External reference
“Can finite samples detect singularities of real-valued functions?”
10.1145/129712.129749 · 1992 · External reference
“Comparing the strength of query types in property testing: The case of testing k-colorability”
2008 · External reference
“A deterministic algorithm for sparse multivariate polynomial interpolation”
10.1145/62212.62241 · 1988 · External reference
“3CNF properties are hard to test”
10.1137/s0097539704445445 · 2005 · External reference
“Testing properties of directed graphs: Acyclicity and connectivity”
10.1002/rsa.10023 · 2002 · External reference
“An optimal learning algorithm for multiplicity automata”
2006 · External reference
“On learning monotone Boolean functions”
10.1109/sfcs.1998.743491 · 1998 · External reference
“Learning in the presence of finitely or infinitely many irrelevant attributes”
10.1006/jcss.1995.1004 · 1995 · External reference
“Learning functions of k terms”
1990 · External reference
“Self-Testing/Correcting with applications to numerical problems”
1993 · External reference
“Occam’s razor”
10.1016/0020-0190(87)90114-1 · 1987 · External reference
“A lower bound for testing 3-colorability in bounded-degree graphs”
10.1109/sfcs.2002.1181886 · 2002 · External reference
“Lower bounds for testing bipartiteness in dense graphs”
2004 · External reference
“Property testing and the branching program size”
2005 · External reference
“Functions that have read-once branching programs of quadratic size are not necessarily testable”
10.1016/s0020-0190(03)00230-8 · 2003 · External reference
“Graph limits and parameter testing”
10.1145/1132516.1132556 · 2006 · External reference
“On learning multivariate polynomials under the uniform distribution”
10.1016/s0020-0190(97)00021-5 · 1996 · External reference
“More efficient PAC-learning of DNF with membership queries under the uniform distribution”
10.1145/307400.307472 · 1999 · External reference
“Simple learning algorithms for decision trees and multivariate polynomials”
10.1137/s009753979732058x · 2002 · External reference
“Approximating the minimum spanning tree weight in sublinear time”
2001 · External reference
“A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations”
10.1214/aoms/1177729330 · 1952 · External reference
“A lower bound for testing juntas”
10.1016/j.ipl.2004.01.023 · 2006 · External reference
“On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields”
10.1016/0304-3975(91)90157-w · 1991 · External reference
“Testing hereditary properties of non-expanding bounded-degree graphs”
2007 · External reference
“Sublinear-time approximation for clustering via random sampling”
10.1007/978-3-540-27836-8_35 · 2004 · External reference
“Abstract combinatorial programs and efficient property testers”
10.1137/s009753970444199x · 2005 · External reference
“Testing hypergraph colorability”
2005 · External reference
“Testing expansion in bounded-degree graphs”
2007 · External reference
“Testing for concise representations”
2007 · External reference
“Efficient testing sparse GF(2) polynomials”
10.1007/978-3-540-70575-8_41 · 2008 · External reference
“Improved testing algorithms for monotonocity”
1999 · External reference
“Spot-checkers”
10.1006/jcss.1999.1692 · 2000 · External reference
“Approximating the distance to monotonicity in high dimensions”
2007 · External reference
“Approximating Clique is almost NP-complete”
10.1145/226643.226652 · 1996 · External reference
“On the strength of comparisons in property testing”
10.1016/j.ic.2003.09.003 · 2004 · External reference
“The difficulty of testing for isomorphism against a graph that is given in advance”
10.1137/s009753970445603 · 2005 · External reference
“Testing graphs for colorability properties”
10.1002/rsa.20037 · 2005 · External reference
“Tolerant versus intolerant testing for Boolean properties”
10.4086/toc.2006.v002a009 · 2006 · External reference
“Testing juntas”
10.1016/j.jcss.2003.11.004 · 2004 · External reference
“Monotonicity testing over general poset domains”
10.1145/509907.509977 · 2002 · External reference
“Approximate hypergraph partitioning and applications”
2007 · External reference
“Testing versus estimation of graph properties”
10.1137/060652324 · 2007 · External reference
“Functions that have read-twice constant width branching programs are not necessarily testable”
10.1002/rsa.10110 · 2004 · External reference
“On learning ring-sum expansions”
10.1137/0221014 · 1992 · External reference
“Some improvements to total degree tests”
10.1109/istcs.1995.377032 · 1995 · External reference
“Self testing/correcting for polynomials and for approximate functions”
1991 · External reference
“Distribution-free testing lower bounds for basic Boolean functions”
2007 · External reference
“Short locally testable codes and proofs (a survey)”
2005 · External reference
“Testing monotonicity”
10.1007/s004930070011 · 2000 · External reference
“Property testing and its connection to learning and approximation”
10.1145/285055.285060 · 1998 · External reference
“A sublinear bipartite tester for bounded degree graphs”
10.1007/s004930050060 · 1999 · External reference
“On testing expansion in bounded-degree graphs”
2000 · External reference
“Property testing in bounded degree graphs”
10.1007/s00453-001-0078-7 · 2002 · External reference
“Three theorems regarding testing graph properties”
10.1002/rsa.10078 · 2003 · External reference
“Probabilistic encryption”
10.1016/0022-0000(84)90070-9 · 1984 · External reference
“On the benefits of adaptivity in property testing of dense graphs”
2007 · External reference
“Fast parallel algorithms for sparse multivariate polynomial interpolation over finite fields”
10.1137/0219073 · 1990 · External reference
“Finding relevant variables in PAC model with membership queries”
1999 · External reference
“Tolerant locally testable codes”
2005 · External reference
“Distribution-free property testing”
2003 · External reference
“Distribution-free connectivity testing”
2004 · External reference
“A lower bound for distribution-free monotonicity testing”
2005 · External reference
“Distribution-free property testing”
10.1137/050645804 · 2007 · External reference
“Probability inequalities for sums of bounded random variables”
10.1080/01621459.1963.10500830 · 1963 · External reference
“A sublinear-time approximation scheme for clustering in metric spaces”
10.1109/sffcs.1999.814587 · 1999 · External reference
“An efficient membership-query algorithm for learning DNF with respect to the uniform distribution”
10.1006/jcss.1997.1533 · 1997 · External reference
“Testing low-degree polynomials over prime fields”
10.1109/focs.2004.64 · 2004 · External reference
“Testing expansion in bounded degree graphs”
2007 · External reference
“Tight bounds for testing bipartiteness in general graphs”
10.1137/s0097539703436424 · 2004 · External reference
“Breaking the e-soundness bound of the linearity test over GF(2)”
2007 · External reference
“Testing polynomials over general fields”
10.1137/s0097539704445615 · 2006 · External reference
“Learning Boolean formulae”
10.1145/195613.195656 · 1995 · External reference
“Testing problems with sub-learning sample complexity”
10.1006/jcss.1999.1656 · 2000 · External reference
“Cryptographic limitations on learning boolean formulae and finite automata”
10.1145/174644.174647 · 1994 · External reference
“Toward efficient agnostic learning”
10.1023/a:1022615600103 · 1994 · External reference
Unresolved reference
1987 · External reference
“Boosting and hard-core sets”
10.1109/sffcs.1999.814638 · 1999 · External reference
“Efficient testing of hypergraphs”
2002 · External reference
“Active learning using arbitrary binary valued queries”
10.1023/a:1022627018023 · 1993 · External reference
“On probably correct classification of concepts”
10.1145/168304.168318 · 1993 · External reference
Unresolved reference
2005 · External reference
“Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm”
10.1023/a:1022869011914 · 1987 · External reference
“Randomized interpolation and approximation of sparse polynomials”
10.1137/s0097539792239291 · 1995 · External reference
“Distance approximation in bounded-degree and general sparse graphs”
2006 · External reference
“Testing Halfspaces”
2007 · External reference
“Sublinear time approximate clustering”
2001 · External reference
“Learning juntas”
10.1016/j.jcss.2004.04.002 · 2004 · External reference
“Testing the expansion of a graph”
2007 · External reference
“Testing membership in languages that have small width branching programs”
10.1137/s009753970038211x · 2002 · External reference
“Testing the diameter of graphs”
10.1002/rsa.10013 · 2002 · External reference
“On testing convexity and submodularity”
10.1137/s0097539702414026 · 2003 · External reference
“Tolerant property testing and distance approximation”
10.1016/j.jcss.2006.03.002 · 2006 · External reference
“Testing basic Boolean formulae”
10.1137/s0895480101407444 · 2002 · External reference
“Strong lower bounds for approximating distributions support size and the distinct elements problem”
2007 · External reference
“Interpolation and approximation of sparse multivariate polynomials over GF(2)”
10.1137/0220019 · 1991 · External reference
“Robust characterization of polynomials with applications to program testing”
10.1137/s0097539793255151 · 1996 · External reference
“Learning sparse multivariate polynomials over a field with queries and counterexamples”
10.1006/jcss.1996.0017 · 1996 · External reference
“Derandomizing homomorphism testing in general groups”
10.1145/1007352.1007421 · 2004 · External reference
Efficient checking of polynomials and proofs and the hardness of approximation problems
1992 · External reference
“Regular partitions of graphs”
1978 · External reference
“Optimal attribute-efficient learning of disjunction, parity and threshold functions”
10.1007/3-540-62685-9_15 · 1997 · External reference
“A theory of the learnable”
10.1145/1968.1972 · 1984 · External reference
“Testing symmetric properties of distributions”
10.1145/1374376.1374432 · 2008 · External reference
Unresolved reference
1998 · External reference
“Probably almost discriminative learning”
10.1023/a:1022870506888 · 1995 · External reference
“Probabilistic algorithms for sparse polynomials”
1978 · External reference
“Interpolating polynomials from their values”
10.1016/s0747-7171(08)80018-1 · 1990 · External reference
