Modanese, Augusto Sublinear-time language recognition and decision by one-dimensional cellular automata. (English) Zbl 1518.68223 Int. J. Found. Comput. Sci. 32, No. 6, 713-731 (2021). MSC: 68Q80 68Q15 68Q25 68Q45 PDFBibTeX XMLCite \textit{A. Modanese}, Int. J. Found. Comput. Sci. 32, No. 6, 713--731 (2021; Zbl 1518.68223) Full Text: DOI
Belovs, Aleksandrs; Blais, Eric A polynomial lower bound for testing monotonicity. (English) Zbl 1522.68238 SIAM J. Comput. 50, No. 3, STOC16-406-STOC16-433 (2021). MSC: 68Q17 06E30 68Q25 68W20 PDFBibTeX XMLCite \textit{A. Belovs} and \textit{E. Blais}, SIAM J. Comput. 50, No. 3, STOC16--406-STOC16--433 (2021; Zbl 1522.68238) Full Text: DOI
Modanese, Augusto Sublinear-time language recognition and decision by one-dimensional cellular automata. (English) Zbl 1518.68222 Jonoska, Nataša (ed.) et al., Developments in language theory. 24th international conference, DLT 2020, Tampa, FL, USA, May 11–15, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12086, 251-265 (2020). MSC: 68Q80 68Q15 68Q25 68Q45 PDFBibTeX XMLCite \textit{A. Modanese}, Lect. Notes Comput. Sci. 12086, 251--265 (2020; Zbl 1518.68222) Full Text: DOI arXiv
Acharya, Jayadev; Canonne, Clément L.; Kamath, Gautam A chasm between identity and equivalence testing with conditional queries. (English) Zbl 1412.68293 Theory Comput. 14, Paper No. 19, 46 p. (2018). MSC: 68W20 60C05 60E15 68Q17 68Q25 PDFBibTeX XMLCite \textit{J. Acharya} et al., Theory Comput. 14, Paper No. 19, 46 p. (2018; Zbl 1412.68293) Full Text: DOI
Saks, M.; Seshadhri, C. Estimating the longest increasing sequence in polylogarithmic time. (English) Zbl 1370.68342 SIAM J. Comput. 46, No. 2, 774-823 (2017). MSC: 68W32 68W20 68W25 68W40 PDFBibTeX XMLCite \textit{M. Saks} and \textit{C. Seshadhri}, SIAM J. Comput. 46, No. 2, 774--823 (2017; Zbl 1370.68342) Full Text: DOI arXiv
Bennett, Janine C.; Bhagatwala, Ankit; Chen, Jacqueline H.; Pinar, Ali; Salloum, Maher; Seshadhri, C. Trigger detection for adaptive scientific workflows using percentile sampling. (English) Zbl 1386.68211 SIAM J. Sci. Comput. 38, No. 5, S240-S263 (2016). MSC: 68U20 65Y05 80A25 PDFBibTeX XMLCite \textit{J. C. Bennett} et al., SIAM J. Sci. Comput. 38, No. 5, S240--S263 (2016; Zbl 1386.68211) Full Text: DOI arXiv
Canonne, Clément L. Big data on the rise? Testing monotonicity of distributions. (English) Zbl 1441.68281 Halldórsson, Magnús M. (ed.) et al., Automata, languages, and programming. 42nd international colloquium, ICALP 2015, Kyoto, Japan, July 6–10, 2015. Proceedings. Part I. Berlin: Springer. Lect. Notes Comput. Sci. 9134, 294-305 (2015). MSC: 68W20 62R07 68Q25 PDFBibTeX XMLCite \textit{C. L. Canonne}, Lect. Notes Comput. Sci. 9134, 294--305 (2015; Zbl 1441.68281) Full Text: DOI arXiv
Tamaki, Suguru; Yoshida, Yuichi A query efficient non-adaptive long code test with perfect completeness. (English) Zbl 1341.68066 Random Struct. Algorithms 47, No. 2, 386-406 (2015). MSC: 68Q25 68W20 68W25 PDFBibTeX XMLCite \textit{S. Tamaki} and \textit{Y. Yoshida}, Random Struct. Algorithms 47, No. 2, 386--406 (2015; Zbl 1341.68066) Full Text: DOI Link
Xu, Bojian Boosting distinct random sampling for basic counting on the union of distributed streams. (English) Zbl 1329.68279 Theor. Comput. Sci. 602, 60-79 (2015). MSC: 68W15 PDFBibTeX XMLCite \textit{B. Xu}, Theor. Comput. Sci. 602, 60--79 (2015; Zbl 1329.68279) Full Text: DOI
Yoshida, Yuichi; Ito, Hiro Testing outerplanarity of bounded degree graphs. (English) Zbl 1319.68162 Algorithmica 73, No. 1, 1-20 (2015). MSC: 68R10 05C10 05C85 68W20 PDFBibTeX XMLCite \textit{Y. Yoshida} and \textit{H. Ito}, Algorithmica 73, No. 1, 1--20 (2015; Zbl 1319.68162) Full Text: DOI
Ron, Dana; Servedio, Rocco A. Exponentially improved algorithms and lower bounds for testing signed majorities. (English) Zbl 1322.68260 Algorithmica 72, No. 2, 400-429 (2015). MSC: 68W20 68Q17 68Q25 PDFBibTeX XMLCite \textit{D. Ron} and \textit{R. A. Servedio}, Algorithmica 72, No. 2, 400--429 (2015; Zbl 1322.68260) Full Text: DOI
Canonne, Clément L.; Ron, Dana; Servedio, Rocco A. Testing probability distributions using conditional samples. (English) Zbl 1328.68293 SIAM J. Comput. 44, No. 3, 540-616 (2015). MSC: 68W20 68Q17 PDFBibTeX XMLCite \textit{C. L. Canonne} et al., SIAM J. Comput. 44, No. 3, 540--616 (2015; Zbl 1328.68293) Full Text: DOI arXiv
Nikoletseas, S.; Panagopoulou, P.; Raptopoulos, C.; Spirakis, P. G. On the structure of equilibria in basic network formation. (English) Zbl 1330.91049 Theor. Comput. Sci. 590, 96-105 (2015). MSC: 91A43 PDFBibTeX XMLCite \textit{S. Nikoletseas} et al., Theor. Comput. Sci. 590, 96--105 (2015; Zbl 1330.91049) Full Text: DOI arXiv
Bhattacharyya, Arnab; Grigorescu, Elena; Shapira, Asaf A unified framework for testing linear-invariant properties. (English) Zbl 1309.62039 Random Struct. Algorithms 46, No. 2, 232-260 (2015). MSC: 62F03 68W20 05C80 05C70 PDFBibTeX XMLCite \textit{A. Bhattacharyya} et al., Random Struct. Algorithms 46, No. 2, 232--260 (2015; Zbl 1309.62039) Full Text: DOI arXiv
Weinberger, Shmuel The complexity of some topological inference problems. (English) Zbl 1308.68060 Found. Comput. Math. 14, No. 6, 1277-1285 (2014). Reviewer: G. V. Orman MSC: 68Q17 52B99 57Q99 62-07 62G99 PDFBibTeX XMLCite \textit{S. Weinberger}, Found. Comput. Math. 14, No. 6, 1277--1285 (2014; Zbl 1308.68060) Full Text: DOI
Seshadhri, C.; Vondrák, Jan Is submodularity testable? (English) Zbl 1307.68097 Algorithmica 69, No. 1, 1-25 (2014). MSC: 68W20 68Q25 90C27 PDFBibTeX XMLCite \textit{C. Seshadhri} and \textit{J. Vondrák}, Algorithmica 69, No. 1, 1--25 (2014; Zbl 1307.68097) Full Text: DOI arXiv
Czumaj, Artur; Goldreich, Oded; Ron, Dana; Seshadhri, C.; Shapira, Asaf; Sohler, Christian Finding cycles and trees in sublinear time. (English) Zbl 1307.05210 Random Struct. Algorithms 45, No. 2, 139-184 (2014). Reviewer: Vladimír Lacko (Košice) MSC: 05C85 05C38 05C12 05C83 05C05 68W20 PDFBibTeX XMLCite \textit{A. Czumaj} et al., Random Struct. Algorithms 45, No. 2, 139--184 (2014; Zbl 1307.05210) Full Text: DOI arXiv
Chang, Maw-Shang; Lin, Chuang-Chieh; Rossmanith, Peter Testing consistency of quartet topologies: a parameterized approach. (English) Zbl 1284.68647 Inf. Process. Lett. 113, No. 22-24, 852-857 (2013). MSC: 68W20 68R05 05C05 PDFBibTeX XMLCite \textit{M.-S. Chang} et al., Inf. Process. Lett. 113, No. 22--24, 852--857 (2013; Zbl 1284.68647) Full Text: DOI
Nehama, Ilan Approximately classic judgement aggregation. (English) Zbl 1294.91047 Ann. Math. Artif. Intell. 68, No. 1-3, 91-134 (2013). MSC: 91B14 PDFBibTeX XMLCite \textit{I. Nehama}, Ann. Math. Artif. Intell. 68, No. 1--3, 91--134 (2013; Zbl 1294.91047) Full Text: DOI arXiv
Ndione, Antoine; Lemay, Aurélien; Niehren, Joachim Approximate membership for regular languages modulo the edit distance. (English) Zbl 1293.68307 Theor. Comput. Sci. 487, 37-49 (2013). MSC: 68W20 68Q45 PDFBibTeX XMLCite \textit{A. Ndione} et al., Theor. Comput. Sci. 487, 37--49 (2013; Zbl 1293.68307) Full Text: DOI
Rubinfeld, Ronitt; Xie, Ning Robust characterizations of \(k\)-wise independence over product spaces and related testing results. (English) Zbl 1281.68230 Random Struct. Algorithms 43, No. 3, 265-312 (2013). MSC: 68W20 68Q87 42A16 PDFBibTeX XMLCite \textit{R. Rubinfeld} and \textit{N. Xie}, Random Struct. Algorithms 43, No. 3, 265--312 (2013; Zbl 1281.68230) Full Text: DOI
Chang, Ching-Lueh Some results on approximate 1-median selection in metric spaces. (English) Zbl 1238.68186 Theor. Comput. Sci. 426-427, 1-12 (2012). MSC: 68W25 68R10 68M10 68U05 PDFBibTeX XMLCite \textit{C.-L. Chang}, Theor. Comput. Sci. 426--427, 1--12 (2012; Zbl 1238.68186) Full Text: DOI
Yoshida, Yuichi; Ito, Hiro Property testing on \(k\)-vertex-connectivity of graphs. (English) Zbl 1239.05112 Algorithmica 62, No. 3-4, 701-712 (2012). MSC: 05C40 05C85 PDFBibTeX XMLCite \textit{Y. Yoshida} and \textit{H. Ito}, Algorithmica 62, No. 3--4, 701--712 (2012; Zbl 1239.05112) Full Text: DOI
Ron, Dana; Tsur, Gilad Testing computability by width-two OBDDs. (English) Zbl 1234.68462 Theor. Comput. Sci. 420, 64-79 (2012). MSC: 68W20 68W40 PDFBibTeX XMLCite \textit{D. Ron} and \textit{G. Tsur}, Theor. Comput. Sci. 420, 64--79 (2012; Zbl 1234.68462) Full Text: DOI
Orenstein, Yaron; Ron, Dana Testing Eulerianity and connectivity in directed sparse graphs. (English) Zbl 1238.05110 Theor. Comput. Sci. 412, No. 45, 6390-6408 (2011). MSC: 05C20 PDFBibTeX XMLCite \textit{Y. Orenstein} and \textit{D. Ron}, Theor. Comput. Sci. 412, No. 45, 6390--6408 (2011; Zbl 1238.05110) Full Text: DOI
Kiwi, Marcos; Navarro, Gonzalo; Telha, Claudio On-line approximate string matching with bounded errors. (English) Zbl 1233.68232 Theor. Comput. Sci. 412, No. 45, 6359-6370 (2011). MSC: 68W32 68Q17 PDFBibTeX XMLCite \textit{M. Kiwi} et al., Theor. Comput. Sci. 412, No. 45, 6359--6370 (2011; Zbl 1233.68232) Full Text: DOI Link
Chang, Maw-Shang; Lin, Chuang-Chieh; Rossmanith, Peter A property tester for tree-likeness of quartet topologies. (English) Zbl 1227.68115 Theory Comput. Syst. 49, No. 3, 576-587 (2011). MSC: 68W20 68W40 PDFBibTeX XMLCite \textit{M.-S. Chang} et al., Theory Comput. Syst. 49, No. 3, 576--587 (2011; Zbl 1227.68115) Full Text: DOI
Diakonikolas, Ilias; Lee, Homin K.; Matulef, Kevin; Servedio, Rocco A.; Wan, Andrew Efficiently testing sparse \(\text{GF}(2)\) polynomials. (English) Zbl 1225.68100 Algorithmica 61, No. 3, 580-605 (2011). MSC: 68Q32 68W20 11Y16 PDFBibTeX XMLCite \textit{I. Diakonikolas} et al., Algorithmica 61, No. 3, 580--605 (2011; Zbl 1225.68100) Full Text: DOI
Goldreich, Oded Contemplations on testing graph properties. (English) Zbl 1291.05195 Goldreich, Oded (ed.), Studies in complexity and cryptography. Miscellanea on the interplay between randomness and computation. In collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Halevi, Tali Kaufman, Leonid Levin, Noam Nisan, Dana Ron, Madhu Sudan, Luca Trevisan, Salil Vadhan, Avi Wigderson, David Zuckerman. Berlin: Springer (ISBN 978-3-642-22669-4/pbk). Lecture Notes in Computer Science 6650, 547-554 (2011). MSC: 05C85 68R10 68W20 PDFBibTeX XMLCite \textit{O. Goldreich}, Lect. Notes Comput. Sci. 6650, 547--554 (2011; Zbl 1291.05195) Full Text: DOI Link
Fischer, Eldar; Yahalom, Orly Testing convexity properties of tree colorings. (English) Zbl 1217.05088 Algorithmica 60, No. 4, 766-805 (2011). MSC: 05C15 05C05 05C85 68R10 68Q17 PDFBibTeX XMLCite \textit{E. Fischer} and \textit{O. Yahalom}, Algorithmica 60, No. 4, 766--805 (2011; Zbl 1217.05088) Full Text: DOI
Ben-Zwi, Oren; Ronen, Amir Local and global price of anarchy of graphical games. (English) Zbl 1208.91026 Theor. Comput. Sci. 412, No. 12-14, 1196-1207 (2011). MSC: 91A43 91A06 PDFBibTeX XMLCite \textit{O. Ben-Zwi} and \textit{A. Ronen}, Theor. Comput. Sci. 412, No. 12--14, 1196--1207 (2011; Zbl 1208.91026) Full Text: DOI
Grigorescu, Elena; Jung, Kyomin; Rubinfeld, Ronitt A local decision test for sparse polynomials. (English) Zbl 1234.68461 Inf. Process. Lett. 110, No. 20, 898-901 (2010). MSC: 68W20 68W30 PDFBibTeX XMLCite \textit{E. Grigorescu} et al., Inf. Process. Lett. 110, No. 20, 898--901 (2010; Zbl 1234.68461) Full Text: DOI Link
Gonen, Mira; Ron, Dana On the benefits of adaptivity in property testing of dense graphs. (English) Zbl 1202.68279 Algorithmica 58, No. 4, 811-830 (2010). MSC: 68R10 68Q25 PDFBibTeX XMLCite \textit{M. Gonen} and \textit{D. Ron}, Algorithmica 58, No. 4, 811--830 (2010; Zbl 1202.68279) Full Text: DOI
Saks, Michael; Seshadhri, C. Local property reconstruction and monotonicity. (English) Zbl 1310.68232 Goldreich, Oded (ed.), Property testing. Current research and surveys. Berlin: Springer (ISBN 978-3-642-16366-1/pbk). Lecture Notes in Computer Science 6390, 346-354 (2010). MSC: 68W20 68P01 68P30 PDFBibTeX XMLCite \textit{M. Saks} and \textit{C. Seshadhri}, Lect. Notes Comput. Sci. 6390, 346--354 (2010; Zbl 1310.68232) Full Text: DOI
Matulef, Kevin; O’Donnell, Ryan; Rubinfeld, Ronitt; Servedio, Rocco Testing (subclasses of) halfspaces. (English) Zbl 1309.68226 Goldreich, Oded (ed.), Property testing. Current research and surveys. Berlin: Springer (ISBN 978-3-642-16366-1/pbk). Lecture Notes in Computer Science 6390, 334-340 (2010). MSC: 68W20 68Q25 PDFBibTeX XMLCite \textit{K. Matulef} et al., Lect. Notes Comput. Sci. 6390, 334--340 (2010; Zbl 1309.68226) Full Text: DOI Link
Andoni, Alexandr; Indyk, Piotr; Onak, Krzysztof; Rubinfeld, Ronitt Sublinear algorithms in the external memory model. (English) Zbl 1309.68214 Goldreich, Oded (ed.), Property testing. Current research and surveys. Berlin: Springer (ISBN 978-3-642-16366-1/pbk). Lecture Notes in Computer Science 6390, 240-243 (2010). MSC: 68W20 60E99 62G10 68Q25 PDFBibTeX XMLCite \textit{A. Andoni} et al., Lect. Notes Comput. Sci. 6390, 240--243 (2010; Zbl 1309.68214) Full Text: DOI
Newman, Ilan Property testing of massively parametrized problems – a survey. (English) Zbl 1309.68227 Goldreich, Oded (ed.), Property testing. Current research and surveys. Berlin: Springer (ISBN 978-3-642-16366-1/pbk). Lecture Notes in Computer Science 6390, 142-157 (2010). MSC: 68W20 68R10 PDFBibTeX XMLCite \textit{I. Newman}, Lect. Notes Comput. Sci. 6390, 142--157 (2010; Zbl 1309.68227) Full Text: DOI
Czumaj, Artur; Sohler, Christian Sublinear-time algorithms. (English) Zbl 1308.68064 Goldreich, Oded (ed.), Property testing. Current research and surveys. Berlin: Springer (ISBN 978-3-642-16366-1/pbk). Lecture Notes in Computer Science 6390, 41-64 (2010). MSC: 68Q25 68R10 68U05 68W20 68W25 PDFBibTeX XMLCite \textit{A. Czumaj} and \textit{C. Sohler}, Lect. Notes Comput. Sci. 6390, 41--64 (2010; Zbl 1308.68064) Full Text: DOI
Nachmias, Asaf; Shapira, Asaf Testing the expansion of a graph. (English) Zbl 1194.68173 Inf. Comput. 208, No. 4, 309-314 (2010). MSC: 68R10 05C85 PDFBibTeX XMLCite \textit{A. Nachmias} and \textit{A. Shapira}, Inf. Comput. 208, No. 4, 309--314 (2010; Zbl 1194.68173) Full Text: DOI
Benjamini, Itai; Schramm, Oded; Shapira, Asaf Every minor-closed property of sparse graphs is testable. (English) Zbl 1223.05291 Adv. Math. 223, No. 6, 2200-2218 (2010). MSC: 05C83 PDFBibTeX XMLCite \textit{I. Benjamini} et al., Adv. Math. 223, No. 6, 2200--2218 (2010; Zbl 1223.05291) Full Text: DOI arXiv
Fu, Bin; Zhao, Zhiyu Separating sublinear time computations by approximate diameter. (English) Zbl 1206.90140 J. Comb. Optim. 18, No. 4, 393-416 (2009). MSC: 90C27 PDFBibTeX XMLCite \textit{B. Fu} and \textit{Z. Zhao}, J. Comb. Optim. 18, No. 4, 393--416 (2009; Zbl 1206.90140) Full Text: DOI
Alon, Noga; Shapira, Asaf; Sudakov, Benny Additive approximation for edge-deletion problems. (English) Zbl 1185.05132 Ann. Math. (2) 170, No. 1, 371-411 (2009). MSC: 05C85 05C35 05C50 68Q25 68R10 68W25 PDFBibTeX XMLCite \textit{N. Alon} et al., Ann. Math. (2) 170, No. 1, 371--411 (2009; Zbl 1185.05132) Full Text: DOI arXiv Link
Fu, Bin; Zhao, Zhiyu Separating sublinear time computations by approximate diameter. (English) Zbl 1168.68591 Yang, Boting (ed.) et al., Combinatorial optimization and applications. Second international conference, COCOA 2008, St. John’s, NL, Canada, August 21–24, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85096-0/pbk). Lecture Notes in Computer Science 5165, 79-88 (2008). MSC: 68U05 68Q25 68W05 68W20 68W25 PDFBibTeX XMLCite \textit{B. Fu} and \textit{Z. Zhao}, Lect. Notes Comput. Sci. 5165, 79--88 (2008; Zbl 1168.68591) Full Text: DOI
Kaufman, Tali; Litsyn, Simon; Xie, Ning Breaking the \(\epsilon \)-soundness bound of the linearity test over GF(2). (English) Zbl 1159.68006 Goel, Ashish (ed.) et al., Approximation, randomization and combinatorial optimization. Algorithms and techniques. 11th international workshop, APPROX 2008, and 12th international workshop, RANDOM 2008, Boston, MA, USA, August 25–27, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85362-6/pbk). Lecture Notes in Computer Science 5171, 498-511 (2008). MSC: 68P30 68Q17 94B25 PDFBibTeX XMLCite \textit{T. Kaufman} et al., Lect. Notes Comput. Sci. 5171, 498--511 (2008; Zbl 1159.68006) Full Text: DOI
Alon, Noga; Shapira, Asaf A separation theorem in property testing. (English) Zbl 1174.05063 Combinatorica 28, No. 3, 261-281 (2008). MSC: 05C35 05D99 68R05 PDFBibTeX XMLCite \textit{N. Alon} and \textit{A. Shapira}, Combinatorica 28, No. 3, 261--281 (2008; Zbl 1174.05063) Full Text: DOI
Ailon, Nir; Chazelle, Bernard; Comandur, Seshadhri; Liu, Ding Property-preserving data reconstruction. (English) Zbl 1147.68017 Algorithmica 51, No. 2, 160-182 (2008). MSC: 68P05 68Q25 PDFBibTeX XMLCite \textit{N. Ailon} et al., Algorithmica 51, No. 2, 160--182 (2008; Zbl 1147.68017) Full Text: DOI
Jordan, Skip; Zeugmann, Thomas Indistinguishability and first-order logic. (English) Zbl 1139.68392 Agrawal, Manindra (ed.) et al., Theory and applications of models of computation. 5th international conference, TAMC 2008, Xi’an, China, April 25–29, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79227-7/pbk). Lecture Notes in Computer Science 4978, 94-104 (2008). MSC: 68R10 03C07 68Q19 PDFBibTeX XMLCite \textit{S. Jordan} and \textit{T. Zeugmann}, Lect. Notes Comput. Sci. 4978, 94--104 (2008; Zbl 1139.68392) Full Text: DOI
Halevy, Shirley; Kushilevitz, Eyal Distribution-free connectivity testing for sparse graphs. (English) Zbl 1138.68044 Algorithmica 51, No. 1, 24-48 (2008). MSC: 68R10 05C40 05C85 PDFBibTeX XMLCite \textit{S. Halevy} and \textit{E. Kushilevitz}, Algorithmica 51, No. 1, 24--48 (2008; Zbl 1138.68044) Full Text: DOI
Ben-Zwi, Oren; Ronen, Amir The local and global price of anarchy of graphical games. (English) Zbl 1136.91339 Monien, Burkhard (ed.) et al., Algorithmic game theory. First international symposium, SAGT 2008, Paderborn, Germany, April 30–May 2, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-79308-3/pbk). Lecture Notes in Computer Science 4997, 255-266 (2008). MSC: 91A43 PDFBibTeX XMLCite \textit{O. Ben-Zwi} and \textit{A. Ronen}, Lect. Notes Comput. Sci. 4997, 255--266 (2008; Zbl 1136.91339) Full Text: DOI
Ben-Zwi, Oren; Lachish, Oded; Newman, Ilan Lower bounds for testing Euclidean minimum spanning trees. (English) Zbl 1189.90129 Inf. Process. Lett. 102, No. 6, 219-225 (2007). MSC: 90C27 90C35 PDFBibTeX XMLCite \textit{O. Ben-Zwi} et al., Inf. Process. Lett. 102, No. 6, 219--225 (2007; Zbl 1189.90129) Full Text: DOI
Fischer, Eldar; Newman, Ilan Testing of matrix-poset properties. (English) Zbl 1164.94004 Combinatorica 27, No. 3, 293-327 (2007). Reviewer: Liviu Goras (Iasi) MSC: 94A20 68R05 68Q99 PDFBibTeX XMLCite \textit{E. Fischer} and \textit{I. Newman}, Combinatorica 27, No. 3, 293--327 (2007; Zbl 1164.94004) Full Text: DOI
Parnas, Michal; Ron, Dana Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms. (English) Zbl 1188.68358 Theor. Comput. Sci. 381, No. 1-3, 183-196 (2007). MSC: 68W25 05C70 05C85 68W15 PDFBibTeX XMLCite \textit{M. Parnas} and \textit{D. Ron}, Theor. Comput. Sci. 381, No. 1--3, 183--196 (2007; Zbl 1188.68358) Full Text: DOI
Ailon, Nir; Chazelle, Bernard Information theory in property testing and monotonicity testing in higher dimension. (English) Zbl 1171.68492 Inf. Comput. 204, No. 11, 1704-1717 (2006). MSC: 68Q25 68W20 94A15 PDFBibTeX XMLCite \textit{N. Ailon} and \textit{B. Chazelle}, Inf. Comput. 204, No. 11, 1704--1717 (2006; Zbl 1171.68492) Full Text: DOI
Parnas, Michal; Ron, Dana; Rubinfeld, Ronitt Tolerant property testing and distance approximation. (English) Zbl 1100.68109 J. Comput. Syst. Sci. 72, No. 6, 1012-1042 (2006). MSC: 68T20 68W25 68M15 PDFBibTeX XMLCite \textit{M. Parnas} et al., J. Comput. Syst. Sci. 72, No. 6, 1012--1042 (2006; Zbl 1100.68109) Full Text: DOI
Bollig, Beate A large lower bound on the query complexity of a simple Boolean function. (English) Zbl 1177.68251 Inf. Process. Lett. 95, No. 4, 423-428 (2005). MSC: 68W20 68Q17 68Q25 PDFBibTeX XMLCite \textit{B. Bollig}, Inf. Process. Lett. 95, No. 4, 423--428 (2005; Zbl 1177.68251) Full Text: DOI
Alon, Noga; Shapira, Asaf Testing subgraphs in directed graphs. (English) Zbl 1084.68087 J. Comput. Syst. Sci. 69, No. 3, 354-382 (2004). MSC: 68R10 05C20 PDFBibTeX XMLCite \textit{N. Alon} and \textit{A. Shapira}, J. Comput. Syst. Sci. 69, No. 3, 354--382 (2004; Zbl 1084.68087) Full Text: DOI
Fischer, Eldar; Kindler, Guy; Ron, Dana; Safra, Shmuel; Samorodnitsky, Alex Testing juntas. (English) Zbl 1076.68112 J. Comput. Syst. Sci. 68, No. 4, 753-787 (2004). MSC: 68W20 68Q17 68Q25 60G50 PDFBibTeX XMLCite \textit{E. Fischer} et al., J. Comput. Syst. Sci. 68, No. 4, 753--787 (2004; Zbl 1076.68112) Full Text: DOI
Parnas, Michal; Ron, Dana Testing metric properties. (English) Zbl 1076.68034 Inf. Comput. 187, No. 2, 155-195 (2003). MSC: 68Q25 68W20 54E35 PDFBibTeX XMLCite \textit{M. Parnas} and \textit{D. Ron}, Inf. Comput. 187, No. 2, 155--195 (2003; Zbl 1076.68034) Full Text: DOI