Published in: LIPIcs, Volume 323, 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)
Nathaniel Harms and Artur Riazanov. Better Boosting of Communication Oracles, or Not. In 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 323, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{harms_et_al:LIPIcs.FSTTCS.2024.25, author = {Harms, Nathaniel and Riazanov, Artur}, title = {{Better Boosting of Communication Oracles, or Not}}, booktitle = {44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2024)}, pages = {25:1--25:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-355-3}, ISSN = {1868-8969}, year = {2024}, volume = {323}, editor = {Barman, Siddharth and Lasota, S{\l}awomir}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2024.25}, URN = {urn:nbn:de:0030-drops-222143}, doi = {10.4230/LIPIcs.FSTTCS.2024.25}, annote = {Keywords: oracles, error reduction, communication complexity} }
Published in: LIPIcs, Volume 317, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)
Hadley Black. Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 317, pp. 37:1-37:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{black:LIPIcs.APPROX/RANDOM.2024.37, author = {Black, Hadley}, title = {{Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2024)}, pages = {37:1--37:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-348-5}, ISSN = {1868-8969}, year = {2024}, volume = {317}, editor = {Kumar, Amit and Ron-Zewi, Noga}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2024.37}, URN = {urn:nbn:de:0030-drops-210308}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2024.37}, annote = {Keywords: Property testing, learning, Boolean functions, monotonicity, k-monotonicity} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Hadley Black, Eric Blais, and Nathaniel Harms. Testing and Learning Convex Sets in the Ternary Hypercube. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 15:1-15:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{black_et_al:LIPIcs.ITCS.2024.15, author = {Black, Hadley and Blais, Eric and Harms, Nathaniel}, title = {{Testing and Learning Convex Sets in the Ternary Hypercube}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {15:1--15:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.15}, URN = {urn:nbn:de:0030-drops-195435}, doi = {10.4230/LIPIcs.ITCS.2024.15}, annote = {Keywords: Property testing, learning theory, convex sets, testing convexity, fluctuation} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Renato Ferreira Pinto Jr. and Nathaniel Harms. Distribution Testing with a Confused Collector. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 47:1-47:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{ferreirapintojr._et_al:LIPIcs.ITCS.2024.47, author = {Ferreira Pinto Jr., Renato and Harms, Nathaniel}, title = {{Distribution Testing with a Confused Collector}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {47:1--47:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.47}, URN = {urn:nbn:de:0030-drops-195755}, doi = {10.4230/LIPIcs.ITCS.2024.47}, annote = {Keywords: Distribution testing, property testing, uniformity testing, identity testing, earth-mover distance, sublinear algorithms} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Louis Esperet, Nathaniel Harms, and Viktor Zamaraev. Optimal Adjacency Labels for Subgraphs of Cartesian Products. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 57:1-57:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{esperet_et_al:LIPIcs.ICALP.2023.57, author = {Esperet, Louis and Harms, Nathaniel and Zamaraev, Viktor}, title = {{Optimal Adjacency Labels for Subgraphs of Cartesian Products}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {57:1--57:11}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.57}, URN = {urn:nbn:de:0030-drops-181093}, doi = {10.4230/LIPIcs.ICALP.2023.57}, annote = {Keywords: Adjacency labeling schemes, Cartesian product, Hypercubes} }
Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)
Louis Esperet, Nathaniel Harms, and Andrey Kupavskii. Sketching Distances in Monotone Graph Classes. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 18:1-18:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{esperet_et_al:LIPIcs.APPROX/RANDOM.2022.18, author = {Esperet, Louis and Harms, Nathaniel and Kupavskii, Andrey}, title = {{Sketching Distances in Monotone Graph Classes}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)}, pages = {18:1--18:23}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-249-5}, ISSN = {1868-8969}, year = {2022}, volume = {245}, editor = {Chakrabarti, Amit and Swamy, Chaitanya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.18}, URN = {urn:nbn:de:0030-drops-171406}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2022.18}, annote = {Keywords: adjacency labelling, informative labelling, distance sketching, adjacency sketching, communication complexity} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Nathaniel Harms and Yuichi Yoshida. Downsampling for Testing and Learning in Product Distributions. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 71:1-71:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{harms_et_al:LIPIcs.ICALP.2022.71, author = {Harms, Nathaniel and Yoshida, Yuichi}, title = {{Downsampling for Testing and Learning in Product Distributions}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {71:1--71:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.71}, URN = {urn:nbn:de:0030-drops-164123}, doi = {10.4230/LIPIcs.ICALP.2022.71}, annote = {Keywords: property testing, learning, monotonicity, halfspaces, intersections of halfspaces, polynomial threshold functions} }
Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)
Nathaniel Harms. Universal Communication, Universal Graphs, and Graph Labeling. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 33:1-33:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{harms:LIPIcs.ITCS.2020.33, author = {Harms, Nathaniel}, title = {{Universal Communication, Universal Graphs, and Graph Labeling}}, booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)}, pages = {33:1--33:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-134-4}, ISSN = {1868-8969}, year = {2020}, volume = {151}, editor = {Vidick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.33}, URN = {urn:nbn:de:0030-drops-117182}, doi = {10.4230/LIPIcs.ITCS.2020.33}, annote = {Keywords: Universal graphs, graph labeling, distance labeling, planar graphs, lattices, hamming distance} }
Feedback for Dagstuhl Publishing