Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)
Yuval Dagan, Yuval Filmus, Daniel Kane, and Shay Moran. The Entropy of Lies: Playing Twenty Questions with a Liar. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 1:1-1:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{dagan_et_al:LIPIcs.ITCS.2021.1, author = {Dagan, Yuval and Filmus, Yuval and Kane, Daniel and Moran, Shay}, title = {{The Entropy of Lies: Playing Twenty Questions with a Liar}}, booktitle = {12th Innovations in Theoretical Computer Science Conference (ITCS 2021)}, pages = {1:1--1:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-177-1}, ISSN = {1868-8969}, year = {2021}, volume = {185}, editor = {Lee, James R.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.1}, URN = {urn:nbn:de:0030-drops-135400}, doi = {10.4230/LIPIcs.ITCS.2021.1}, annote = {Keywords: entropy, twenty questions, algorithms, sorting} }
Published in: LIPIcs, Volume 102, 33rd Computational Complexity Conference (CCC 2018)
Daniel Kane and Sankeerth Rao. A PRG for Boolean PTF of Degree 2 with Seed Length Subpolynomial in epsilon and Logarithmic in n. In 33rd Computational Complexity Conference (CCC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 102, pp. 2:1-2:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{kane_et_al:LIPIcs.CCC.2018.2, author = {Kane, Daniel and Rao, Sankeerth}, title = {{A PRG for Boolean PTF of Degree 2 with Seed Length Subpolynomial in epsilon and Logarithmic in n}}, booktitle = {33rd Computational Complexity Conference (CCC 2018)}, pages = {2:1--2:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-069-9}, ISSN = {1868-8969}, year = {2018}, volume = {102}, editor = {Servedio, Rocco A.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2018.2}, URN = {urn:nbn:de:0030-drops-88861}, doi = {10.4230/LIPIcs.CCC.2018.2}, annote = {Keywords: Pseudorandomness, Polynomial Threshold Functions} }
Published in: Dagstuhl Seminar Proceedings, Volume 9111, Computational Geometry (2009)
Daniel Kane, Gregory Nathan Price, and Erik Demaine. A Pseudopolynomial Algorithm for Alexandrov's Theorem. In Computational Geometry. Dagstuhl Seminar Proceedings, Volume 9111, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)
@InProceedings{kane_et_al:DagSemProc.09111.2, author = {Kane, Daniel and Price, Gregory Nathan and Demaine, Erik}, title = {{A Pseudopolynomial Algorithm for Alexandrov's Theorem}}, booktitle = {Computational Geometry}, pages = {1--22}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2009}, volume = {9111}, editor = {Pankaj Kumar Agarwal and Helmut Alt and Monique Teillaud}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09111.2}, URN = {urn:nbn:de:0030-drops-20328}, doi = {10.4230/DagSemProc.09111.2}, annote = {Keywords: Folding, metrics, pseudopolynomial, algorithms} }
Published in: LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Daniel M. Kane and Richard Ryan Williams. The Orthogonal Vectors Conjecture for Branching Programs and Formulas. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 48:1-48:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{kane_et_al:LIPIcs.ITCS.2019.48, author = {Kane, Daniel M. and Williams, Richard Ryan}, title = {{The Orthogonal Vectors Conjecture for Branching Programs and Formulas}}, booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)}, pages = {48:1--48:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-095-8}, ISSN = {1868-8969}, year = {2019}, volume = {124}, editor = {Blum, Avrim}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.48}, URN = {urn:nbn:de:0030-drops-101418}, doi = {10.4230/LIPIcs.ITCS.2019.48}, annote = {Keywords: fine-grained complexity, orthogonal vectors, branching programs, symmetric functions, Boolean formulas} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Daniel M. Kane, Shachar Lovett, and Shay Moran. Generalized Comparison Trees for Point-Location Problems. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 82:1-82:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{kane_et_al:LIPIcs.ICALP.2018.82, author = {Kane, Daniel M. and Lovett, Shachar and Moran, Shay}, title = {{Generalized Comparison Trees for Point-Location Problems}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {82:1--82:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.82}, URN = {urn:nbn:de:0030-drops-90862}, doi = {10.4230/LIPIcs.ICALP.2018.82}, annote = {Keywords: linear decision trees, comparison queries, point location problems} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Ilias Diakonikolas, Daniel M. Kane, and Vladimir Nikishkin. Near-Optimal Closeness Testing of Discrete Histogram Distributions. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{diakonikolas_et_al:LIPIcs.ICALP.2017.8, author = {Diakonikolas, Ilias and Kane, Daniel M. and Nikishkin, Vladimir}, title = {{Near-Optimal Closeness Testing of Discrete Histogram Distributions}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {8:1--8:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.8}, URN = {urn:nbn:de:0030-drops-74937}, doi = {10.4230/LIPIcs.ICALP.2017.8}, annote = {Keywords: distribution testing, histograms, closeness testing} }
Published in: LIPIcs, Volume 33, 30th Conference on Computational Complexity (CCC 2015)
Daniel M. Kane. A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian Setting. In 30th Conference on Computational Complexity (CCC 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 33, pp. 567-581, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{kane:LIPIcs.CCC.2015.567, author = {Kane, Daniel M.}, title = {{A Polylogarithmic PRG for Degree 2 Threshold Functions in the Gaussian Setting}}, booktitle = {30th Conference on Computational Complexity (CCC 2015)}, pages = {567--581}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-81-1}, ISSN = {1868-8969}, year = {2015}, volume = {33}, editor = {Zuckerman, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2015.567}, URN = {urn:nbn:de:0030-drops-50534}, doi = {10.4230/LIPIcs.CCC.2015.567}, annote = {Keywords: polynomial threshold function, pseudorandom generator, Gaussian distribution} }
Feedback for Dagstuhl Publishing