{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T22:50:54Z","timestamp":1725490254690},"publisher-location":"Berlin, Heidelberg","reference-count":23,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540742074"},{"type":"electronic","value":"9783540742081"}],"license":[{"start":{"date-parts":[[2007,1,1]],"date-time":"2007-01-01T00:00:00Z","timestamp":1167609600000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2007]]},"DOI":"10.1007\/978-3-540-74208-1_36","type":"book-chapter","created":{"date-parts":[[2007,8,27]],"date-time":"2007-08-27T10:52:26Z","timestamp":1188211946000},"page":"494-508","source":"Crossref","is-referenced-by-count":3,"title":["Distribution-Free Testing Lower Bounds for Basic Boolean Functions"],"prefix":"10.1007","author":[{"given":"Dana","family":"Glasner","sequence":"first","affiliation":[]},{"given":"Rocco A.","family":"Servedio","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"36_CR1","doi-asserted-by":"publisher","first-page":"1704","DOI":"10.1016\/j.ic.2006.06.001","volume":"204","author":"N. Ailon","year":"2006","unstructured":"Ailon, N., Chazelle, B.: Information theory in property testing and monotonicity testing in higher dimension. Information and Computation\u00a0204, 1704\u20131717 (2006)","journal-title":"Information and Computation"},{"key":"36_CR2","doi-asserted-by":"crossref","unstructured":"Alon, N., Kaufman, T., Krivelevich, M., Litsyn, S., Ron, D.: Testing low-degree polynomials over GF(2). In: Proceedings of RANDOM-APPROX, pp. 188\u2013199 (2003)","DOI":"10.1007\/978-3-540-45198-3_17"},{"key":"36_CR3","unstructured":"Alon, N., Shapira, A.: Homomorphisms in Graph Property Testing - A Survey. Topics in Discrete Mathematics (to appear, 2007), available at http:\/\/www.math.tau.ac.il\/~asafico\/nesetril.pdf"},{"key":"36_CR4","doi-asserted-by":"publisher","first-page":"549","DOI":"10.1016\/0022-0000(93)90044-W","volume":"47","author":"M. Blum","year":"1993","unstructured":"Blum, M., Luby, M., Rubinfeld, R.: Self-testing\/correcting with applications to numerical problems. J. Comp. Sys. Sci.\u00a047, 549\u2013595 (1993) (Earlier version in STOC 1990)","journal-title":"J. Comp. Sys. Sci."},{"key":"36_CR5","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Lee, H., Matulef, K., Onak, K., Rubinfeld, R., Servedio, R., Wan, A.: Testing for concise representations. Submitted for publication (2007)","DOI":"10.1109\/FOCS.2007.32"},{"key":"36_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/978-3-540-48413-4_10","volume-title":"Randomization, Approximation, and Combinatorial Optimization. Algorithms and Techniques","author":"Y. Dodis","year":"1999","unstructured":"Dodis, Y., Goldreich, O., Lehman, E., Raskhodnikova, S., Ron, D., Samorodnitsky, A.: Improved testing algorithms for monotonocity. In: Hochbaum, D.S., Jansen, K., Rolim, J.D.P., Sinclair, A. (eds.) RANDOM 1999 and APPROX 1999. LNCS, vol.\u00a01671, pp. 97\u2013108. Springer, Heidelberg (1999)"},{"key":"36_CR7","first-page":"97","volume":"75","author":"E. Fischer","year":"2001","unstructured":"Fischer, E.: The art of uninformed decisions: A primer to property testing. Computational Complexity Column of The Bulletin of the European Association for Theoretical Computer Science\u00a075, 97\u2013126 (2001)","journal-title":"Computational Complexity Column of The Bulletin of the European Association for Theoretical Computer Science"},{"key":"36_CR8","unstructured":"Fischer, E., Kindler, G., Ron, D., Safra, S., Samorodnitsky, A.: Testing juntas. In: Proceedings of the 43rd IEEE Symposium on Foundations of Computer Science, pp. 103\u2013112 (2002)"},{"key":"36_CR9","first-page":"474","volume-title":"Proc. 34th Annual ACM Symposium on the Theory of Computing","author":"E. Fischer","year":"2002","unstructured":"Fischer, E., Lehman, E., Newman, I., Raskhodnikova, S., Rubinfeld, R., Samrodnitsky, A.: Monotonicity testing over general poset domains. In: Proc. 34th Annual ACM Symposium on the Theory of Computing, pp. 474\u2013483. ACM Press, New York (2002)"},{"key":"36_CR10","doi-asserted-by":"crossref","unstructured":"Glasner, D., Servedio, R.: Distribution-free testing lower bounds for basic boolean functions (2007), http:\/\/www.cs.columbia.edu\/rocco\/papers\/random07.html","DOI":"10.1007\/978-3-540-74208-1_36"},{"key":"36_CR11","doi-asserted-by":"crossref","unstructured":"Goldreich, O.: Combinatorial property testing \u2013 a survey. In: Randomized Methods in Algorithms Design, AMS-DIMACS, pp. 45\u201361 (1998)","DOI":"10.1090\/dimacs\/043\/04"},{"key":"36_CR12","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1145\/285055.285060","volume":"45","author":"O. Goldreich","year":"1998","unstructured":"Goldreich, O., Goldwaser, S., Ron, D.: Property testing and its connection to learning and approximation. Journal of the ACM\u00a045, 653\u2013750 (1998)","journal-title":"Journal of the ACM"},{"issue":"3","key":"36_CR13","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s004930070011","volume":"20","author":"O. Goldreich","year":"2000","unstructured":"Goldreich, O., Goldwasser, S., Lehman, E., Ron, D., Samordinsky, A.: Testing monotonicity. Combinatorica\u00a020(3), 301\u2013337 (2000)","journal-title":"Combinatorica"},{"key":"36_CR14","doi-asserted-by":"crossref","unstructured":"Halevy, S., Kushilevitz, E.: Distribution-Free Property Testing. In: Proceedings of the Seventh International Workshop on Randomization and Computation, pp. 302\u2013317 (2003)","DOI":"10.1007\/978-3-540-45198-3_26"},{"key":"36_CR15","doi-asserted-by":"crossref","unstructured":"Halevy, S., Kushilevitz, E.: Distribution-Free Connectivity Testing. In: Proceedings of the Eighth International Workshop on Randomization and Computation, pp. 393\u2013404 (2004)","DOI":"10.1007\/978-3-540-27821-4_35"},{"key":"36_CR16","doi-asserted-by":"crossref","unstructured":"Halevy, S., Kushilevitz, E.: A lower bound for distribution-free monotonicity testing. In: Proceedings of the Ninth International Workshop on Randomization and Computation, pp. 330\u2013341 (2005)","DOI":"10.1007\/11538462_28"},{"key":"36_CR17","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An introduction to computational learning theory","author":"M. Kearns","year":"1994","unstructured":"Kearns, M., Vazirani, U.: An introduction to computational learning theory. MIT Press, Cambridge (1994)"},{"key":"36_CR18","unstructured":"Matulef, K., O\u2019Donnell, R., Rubinfeld, R., Servedio, R.: Testing Halfspaces. (Manuscript, 2007)"},{"key":"36_CR19","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1137\/S0895480101407444","volume":"16","author":"M. Parnas","year":"2002","unstructured":"Parnas, M., Ron, D., Samorodnitsky, A.: Testing basic boolean formulae. SIAM J. Disc. Math.\u00a016, 20\u201346 (2002)","journal-title":"SIAM J. Disc. Math."},{"key":"36_CR20","volume-title":"Handbook of Randomized Computing","author":"D. Ron","year":"2001","unstructured":"Ron, D.: Property testing (a tutorial). In: Rajasekaran, S., Pardalos, P.M., Reif, J.H., Rolim, J.D.P. (eds.) Handbook of Randomized Computing, vol.\u00a0II, Kluwer, Dordrecht (2001)"},{"key":"36_CR21","unstructured":"Rubinfeld, R.: Sublinear time algorithms (2006), available at http:\/\/theory.csail.mit.edu\/~ronitt\/papers\/icm.ps"},{"key":"36_CR22","doi-asserted-by":"publisher","first-page":"252","DOI":"10.1137\/S0097539793255151","volume":"25","author":"R. Rubinfeld","year":"1996","unstructured":"Rubinfeld, R., Sudan, M.: Robust characterizations of polynomials with applications to program testing. SIAM J. on Comput.\u00a025, 252\u2013271 (1996)","journal-title":"SIAM J. on Comput."},{"key":"36_CR23","doi-asserted-by":"crossref","unstructured":"Tur\u00e1n, G.: Lower bounds for PAC learning with queries. In: COLT 1993. Proc. 6th Annual Conference on Computational Learning Theory, pp. 384\u2013391 (2002)","DOI":"10.1145\/168304.168382"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-74208-1_36","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,2]],"date-time":"2019-05-02T12:29:46Z","timestamp":1556800186000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-74208-1_36"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007]]},"ISBN":["9783540742074","9783540742081"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-74208-1_36","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2007]]}}}