Published in: LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024)
Hugo Aaronson, Tom Gur, Ninad Rajgopal, and Ron D. Rothblum. Distribution-Free Proofs of Proximity. In 39th Computational Complexity Conference (CCC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 300, pp. 24:1-24:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{aaronson_et_al:LIPIcs.CCC.2024.24, author = {Aaronson, Hugo and Gur, Tom and Rajgopal, Ninad and Rothblum, Ron D.}, title = {{Distribution-Free Proofs of Proximity}}, booktitle = {39th Computational Complexity Conference (CCC 2024)}, pages = {24:1--24:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-331-7}, ISSN = {1868-8969}, year = {2024}, volume = {300}, editor = {Santhanam, Rahul}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.24}, URN = {urn:nbn:de:0030-drops-204204}, doi = {10.4230/LIPIcs.CCC.2024.24}, annote = {Keywords: Property Testing, Interactive Proofs, Distribution-Free Property Testing} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Édouard Bonnet, Julien Duron, John Sylvester, Viktor Zamaraev, and Maksim Zhukovskii. Tight Bounds on Adjacency Labels for Monotone Graph Classes. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 31:1-31:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bonnet_et_al:LIPIcs.ICALP.2024.31, author = {Bonnet, \'{E}douard and Duron, Julien and Sylvester, John and Zamaraev, Viktor and Zhukovskii, Maksim}, title = {{Tight Bounds on Adjacency Labels for Monotone Graph Classes}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {31:1--31:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.31}, URN = {urn:nbn:de:0030-drops-201741}, doi = {10.4230/LIPIcs.ICALP.2024.31}, annote = {Keywords: Adjacency labeling, degeneracy, monotone classes, small classes, factorial classes, implicit graph conjecture} }
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} }