Black, Hadley; Chakrabarty, Deeparnab; Seshadhri, C. Domain reduction for monotonicity testing: a \(o(d)\) tester for Boolean functions in \(d\)-dimensions. (English) Zbl 07304145 Chawla, Shuchi (ed.), Proceedings of the 31st annual ACM-SIAM symposium on discrete algorithms, SODA 2020, Salt Lake City, UT, USA, January 5–8, 2020. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1975-1994 (2020). MSC: 68Wxx PDFBibTeX XMLCite \textit{H. Black} et al., in: Proceedings of the 31st annual ACM-SIAM symposium on discrete algorithms, SODA 2020, Salt Lake City, UT, USA, January 5--8, 2020. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1975--1994 (2020; Zbl 07304145) Full Text: DOI arXiv
Baleshzar, Roksana; Chakrabarty, Deeparnab; Pallavoor, Ramesh Krishnan S.; Raskhodnikova, Sofya; Seshadhri, C. Optimal unateness testers for real-valued functions: adaptivity helps. (English) Zbl 1462.68235 Theory Comput. 16, Paper No. 3, 36 p. (2020). MSC: 68W20 26-08 PDFBibTeX XMLCite \textit{R. Baleshzar} et al., Theory Comput. 16, Paper No. 3, 36 p. (2020; Zbl 1462.68235) Full Text: DOI arXiv
Chakrabarty, Deeparnab; Seshadhri, C. Adaptive Boolean monotonicity testing in total influence time. (English) Zbl 07559063 Blum, Avrim (ed.), 10th innovations in theoretical computer science conference, ITCS 2019, January 10–12, 2019, San Diego, CA, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 124, Article 20, 7 p. (2019). MSC: 68Qxx PDFBibTeX XMLCite \textit{D. Chakrabarty} and \textit{C. Seshadhri}, LIPIcs -- Leibniz Int. Proc. Inform. 124, Article 20, 7 p. (2019; Zbl 07559063) Full Text: DOI arXiv
Black, Hadley; Chakrabarty, Deeparnab; Seshadhri, C. A \(o(d) \cdot \operatorname{polylog} n\) monotonicity tester for Boolean functions over the hypergrid \([n]^d\). (English) Zbl 1403.68328 Czumaj, Artur (ed.), Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7–10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-503-1/ebook). 2133-2151 (2018). MSC: 68W20 PDFBibTeX XMLCite \textit{H. Black} et al., in: Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7--10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2133--2151 (2018; Zbl 1403.68328) Full Text: arXiv Link
Baleshzar, Roksana; Chakrabarty, Deeparnab; Pallavoor, Ramesh Krishnan S.; Raskhodnikova, Sofya; Seshadhri, C. Optimal unateness testers for real-valued functions: adaptivity helps. (English) Zbl 1441.68279 Chatzigiannakis, Ioannis (ed.) et al., 44th international colloquium on automata, languages, and programming, ICALP 2017, Warsaw, Poland July 10–14, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 80, Article 5, 14 p. (2017). MSC: 68W20 26-08 PDFBibTeX XMLCite \textit{R. Baleshzar} et al., LIPIcs -- Leibniz Int. Proc. Inform. 80, Article 5, 14 p. (2017; Zbl 1441.68279) Full Text: DOI
Chakrabarty, Deeparnab; Dixit, Kashyap; Jha, Madhav; Seshadhri, C. Property testing on product distributions: optimal testers for bounded derivative properties. (English) Zbl 1445.68340 ACM Trans. Algorithms 13, No. 2, Article No. 20, 30 p. (2017). MSC: 68W20 68P05 PDFBibTeX XMLCite \textit{D. Chakrabarty} et al., ACM Trans. Algorithms 13, No. 2, Article No. 20, 30 p. (2017; Zbl 1445.68340) Full Text: DOI
Chakrabarty, D.; Seshadhri, C. An \(o(n)\) monotonicity tester for Boolean functions over the hypercube. (English) Zbl 1339.68308 SIAM J. Comput. 45, No. 2, 461-472 (2016). MSC: 68W20 68Q25 90C27 PDFBibTeX XMLCite \textit{D. Chakrabarty} and \textit{C. Seshadhri}, SIAM J. Comput. 45, No. 2, 461--472 (2016; Zbl 1339.68308) Full Text: DOI
Chakrabarty, Deeparnab; Dixit, Kashyap; Jha, Madhav; Seshadhri, C. Property testing on product distributions: optimal testers for bounded derivative properties. (English) Zbl 1371.68321 Indyk, Piotr (ed.), Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4–6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-61197-374-7; 978-1-61197-373-0/ebook). 1809-1828 (2015). MSC: 68W20 68P05 PDFBibTeX XMLCite \textit{D. Chakrabarty} et al., in: Proceedings of the 26th annual ACM-SIAM symposium on discrete algorithms, SODA 2015, Portland, San Diego, CA, January 4--6, 2015. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1809--1828 (2015; Zbl 1371.68321) Full Text: DOI arXiv
Chakrabarty, Deeparnab; Seshadhri, C. An optimal lower bound for monotonicity testing over hypergrids. (English) Zbl 1319.68098 Theory Comput. 10, Paper No. 17, 453-464 (2014). MSC: 68Q17 68W20 PDFBibTeX XMLCite \textit{D. Chakrabarty} and \textit{C. Seshadhri}, Theory Comput. 10, Paper No. 17, 453--464 (2014; Zbl 1319.68098) Full Text: DOI
Chakrabarty, Deeparnab; Seshadhri, C. Optimal bounds for monotonicity and Lipschitz testing over hypercubes and hypergrids. (English) Zbl 1293.90055 Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 419-428 (2013). MSC: 90C27 68Q17 68W20 PDFBibTeX XMLCite \textit{D. Chakrabarty} and \textit{C. Seshadhri}, in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC '13. Palo Alto, CA, USA, June 1--4, 2013. New York, NY: Association for Computing Machinery (ACM). 419--428 (2013; Zbl 1293.90055) Full Text: DOI arXiv
Chakrabarty, Deeparnab; Seshadhri, C. A \(o(n)\) monotonicity tester for Boolean functions over the hypercube. (English) Zbl 1293.90054 Proceedings of the 45th annual ACM symposium on theory of computing, STOC ’13. Palo Alto, CA, USA, June 1–4, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-2029-0). 411-418 (2013). MSC: 90C27 68Q25 68W20 PDFBibTeX XMLCite \textit{D. Chakrabarty} and \textit{C. Seshadhri}, in: Proceedings of the 45th annual ACM symposium on theory of computing, STOC '13. Palo Alto, CA, USA, June 1--4, 2013. New York, NY: Association for Computing Machinery (ACM). 411--418 (2013; Zbl 1293.90054) Full Text: DOI arXiv
Chakrabarty, Deeparnab; Seshadhri, C. An optimal lower bound for monotonicity testing over hypergrids. (English) Zbl 1405.68127 Raghavendra, Prasad (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 16th international workshop, APPROX 2013, and 17th international workshop, RANDOM 2013, Berkeley, CA, USA, August 21–23, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40327-9/pbk). Lecture Notes in Computer Science 8096, 425-435 (2013). MSC: 68Q17 68W20 PDFBibTeX XMLCite \textit{D. Chakrabarty} and \textit{C. Seshadhri}, Lect. Notes Comput. Sci. 8096, 425--435 (2013; Zbl 1405.68127) Full Text: DOI arXiv