×

Found 12 Documents (Results 1–12)

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
Full Text: DOI arXiv

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
Full Text: DOI arXiv

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
Full Text: arXiv Link

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
Full Text: DOI

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
Full Text: DOI arXiv

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
Full Text: DOI arXiv

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
Full Text: DOI arXiv

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
Full Text: DOI arXiv

Filter Results by …

Document Type

all top 5

Year of Publication

Main Field