the optimal polynomial order sequential testing in r

Ron (2008) Property testing: A learning theory perspective.įoundations and Trends in Machine Learning 1 ( 3), pp. 307–402. Srinivasan (1997) Randomized distributed edge coloring via an extension of the chernoff-hoeffding bounds. International Workshop, RANDOM 2010, Barcelona, Spain, September AlgorithmsĪnd Techniques, 13th International Workshop, APPROX 2010, and 14th Kabanets (2010) Constructive proofs of concentration bounds.Īpproximation, Randomization, and Combinatorial Optimization. Servedio (2007) On PAC learning algorithms for rich boolean function classes. Goldreich (2017) Introduction to property testing. Goldreich (Ed.) (2010) Property testing - current research and surveys. Simon (1992) On learning ring-sum-expansions. Grabmeier (1993) Applying coding theory to sparse interpolation. Wan (2011) Efficiently testing sparse GF(2) polynomials. In 48th Annual IEEE Symposium on Foundations of Computer Science (FOCSĢ007), October 20-23, 2007, Providence, RI, USA, Proceedings, Wan (2007) Testing for concise representations. On zero-testing and interpolation of k-sparse multivariate polynomials over finite fields. ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part In Automata, Languages and Programming - 38th International Colloquium, Matsliah (2011) Efficient sample extractors for juntas with applications. Bshouty (2019) Almost optimal testers for concise representations.Įlectronic Colloquium on Computational Complexity (ECCC) 26, pp. 156.Įxternal Links: Link Cited by: Almost Optimal Proper Learning and Testing Polynomials, Bshouty (1997) On learning multivariate polynomials under the uniform distribution. Simple learning algorithms for decision trees and multivariate polynomials. Goldreich (2022) On properties that are non-trivial to test.Įlectronic Colloquium on Computational Complexity (ECCC) 13. Rubinfeld (1993) Self-testing/correcting with applications to numerical problems. Theory, COLT 1990, University of Rochester, Rochester, NY, USA,Īugust 6-8, 1990, M. Proceedings of the Third Annual Workshop on Computational Learning Singh (1990) Learning functions of k terms. In Proceedings of the 26th Annual IEEE Conference on ComputationalĬomplexity, CCC 2011, San Jose, California, USA, June 8-10, 2011, Matulef (2011) Property testing lower bounds via communication complexity. In Learning Theory, 19th Annual Conference on Learning Theory, COLTĢ006, Pittsburgh, PA, USA, June 22-25, 2006, Proceedings, G. Mazzawi (2006) On optimal learning algorithms for multiplicity automata. Varricchio (1996) Learning multivariate polynomials from substitution and equivalence queries.Įlectron. Varricchio (2000) Learning functions represented as multiplicity automata. Angluin (1987) Queries and concept learning. Replacing the uniform distribution with the distribution D p in the above algorithm gives the query complexity in ( 1).īy ( 12), ( 13), and ( 14), the result follows. We show that to maximize this probability, we need to choose p = 1 − ( log s ) / d. In this paper, we study the probability P r D p when a is chosen according to the product distribution D p, where each a i is equal to 1 with probability p and is 0 with probability 1 − p. Therefore, this algorithm makes O ( 2 d log n ) queries. The number of nonzero entries in a ∗ x is on average n / 2. To find a positive assignment in a degree d polynomial from uniformly at random assignments, we need to make, on average, 2 d queries. Then f ( a ∗ x ) = ∏ a i = 1 x i is a monomial of f. Then recursively do the same for f ( a ∗ x ), where a ∗ x = ( a 1 x 1, a 2 x 2, …, a n x n ), until no more a with smaller Hamming weight can be found. The previous algorithm in chooses uniformly at random assignments until it finds a positive assignment a, i.e., f ( a ) = 1. The best-known algorithm for this problem has query complexity Q ′ = 2 d log n ≈ p o l y ( s / ϵ ) log n. Q = 2 d H 2 ( log s d ) ( 1 − o s ( 1 ) ) log n = s log ( log ( s / ϵ ) / log s ) + O ( 1 ) log n

The optimal polynomial order sequential testing in r