Published in: LIPIcs, Volume 55, 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
Mahdi Cheraghchi, Elena Grigorescu, Brendan Juba, Karl Wimmer, and Ning Xie. AC^0 o MOD_2 Lower Bounds for the Boolean Inner Product. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 35:1-35:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{cheraghchi_et_al:LIPIcs.ICALP.2016.35, author = {Cheraghchi, Mahdi and Grigorescu, Elena and Juba, Brendan and Wimmer, Karl and Xie, Ning}, title = {{AC^0 o MOD\underline2 Lower Bounds for the Boolean Inner Product}}, booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)}, pages = {35:1--35:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-013-2}, ISSN = {1868-8969}, year = {2016}, volume = {55}, editor = {Chatzigiannakis, Ioannis and Mitzenmacher, Michael and Rabani, Yuval and Sangiorgi, Davide}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2016.35}, URN = {urn:nbn:de:0030-drops-63150}, doi = {10.4230/LIPIcs.ICALP.2016.35}, annote = {Keywords: Boolean analysis, circuit complexity, lower bounds} }
Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)
Arnab Bhattacharyya, Victor Chen, Madhu Sudan, and Ning Xie. Testing Linear-Invariant Non-Linear Properties. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 135-146, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{bhattacharyya_et_al:LIPIcs.STACS.2009.1823, author = {Bhattacharyya, Arnab and Chen, Victor and Sudan, Madhu and Xie, Ning}, title = {{Testing Linear-Invariant Non-Linear Properties}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {135--146}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1823}, URN = {urn:nbn:de:0030-drops-18235}, doi = {10.4230/LIPIcs.STACS.2009.1823}, annote = {Keywords: } }
Published in: Dagstuhl Seminar Proceedings, Volume 8341, Sublinear Algorithms (2008)
Tali Kaufman, Simon Litsyn, and Ning Xie. Breaking the $\epsilon$-Soundness Bound of the Linearity Test over GF(2). In Sublinear Algorithms. Dagstuhl Seminar Proceedings, Volume 8341, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)
@InProceedings{kaufman_et_al:DagSemProc.08341.3, author = {Kaufman, Tali and Litsyn, Simon and Xie, Ning}, title = {{Breaking the \$\backslashepsilon\$-Soundness Bound of the Linearity Test over GF(2)}}, booktitle = {Sublinear Algorithms}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2008}, volume = {8341}, editor = {Artur Czumaj and S. Muthu Muthukrishnan and Ronitt Rubinfeld and Christian Sohler}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.08341.3}, URN = {urn:nbn:de:0030-drops-16971}, doi = {10.4230/DagSemProc.08341.3}, annote = {Keywords: Linearity test, Fourier analysis, coding theory} }
Feedback for Dagstuhl Publishing