Nathaniel Harms

According to our database, Nathaniel Harms authored at least 26 papers between 2019 and 2026.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2026

No Constant-Cost Protocol for Point-Line Incidence.

Mika Göös, Nathaniel Harms, Florian K. Richter, Anastasia Sofronova

CoRR, April, 2026

No Constant-Cost Protocol for Point-Line Incidence.

Mika Göös, Nathaniel Harms, Florian Richter, Anastasia Sofronova

Electron. Colloquium Comput. Complex., 2026

Pseudodeterministic Communication Complexity.

Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan

Proceedings of the 58th Annual ACM Symposium on Theory of Computing, 2026

Feature Selection and Junta Testing are Statistically Equivalent.

Lorenzo Beretta, Nathaniel Harms, Caleb Koch

Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, 2026

2025

Sign-Rank of <i>k</i>-Hamming Distance is Constant.

Mika Göös, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov

CoRR, June, 2025

Testing Juntas Optimally with Samples.

Lorenzo Beretta, Nathaniel Harms, Caleb Koch

CoRR, May, 2025

Testing Support Size More Efficiently Than Learning Histograms.

Renato Ferreira Pinto Jr., Nathaniel Harms

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Constant-Cost Communication Is Not Reducible to k-Hamming Distance.

Yuting Fang, Mika Göös, Nathaniel Harms, Pooya Hatami

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Sign-Rank of k-Hamming Distance is Constant.

Mika Göös, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov

Proceedings of the 66th IEEE Annual Symposium on Foundations of Computer Science, 2025

Equality Is Far Weaker Than Constant-Cost Communication.

Mika Göös, Nathaniel Harms, Artur Riazanov

Proceedings of the Approximation, 2025

2024

Graphs with minimum fractional domatic number.

Maximilien Gadouleau, Nathaniel Harms, George B. Mertzios, Viktor Zamaraev

Discret. Appl. Math., January, 2024

No Complete Problem for Constant-Cost Randomized Communication.

Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami

Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2024

Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank.

Nathaniel Harms, Viktor Zamaraev

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Distribution Testing with a Confused Collector.

Renato Ferreira Pinto Jr., Nathaniel Harms

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Testing and Learning Convex Sets in the Ternary Hypercube.

Hadley Black, Eric Blais, Nathaniel Harms

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

Better Boosting of Communication Oracles, or Not.

Nathaniel Harms, Artur Riazanov

Proceedings of the 44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2024

2023

Testing Convexity of Discrete Sets in High Dimensions.

Hadley Black, Eric Blais, Nathaniel Harms

CoRR, 2023

Distribution Testing Under the Parity Trace.

Renato Ferreira Pinto Jr., Nathaniel Harms

CoRR, 2023

Optimal Adjacency Labels for Subgraphs of Cartesian Products.

Louis Esperet, Nathaniel Harms, Viktor Zamaraev

Proceedings of the 50th International Colloquium on Automata, Languages, and Programming, 2023

2022

Randomized communication and implicit graph representations.

Nathaniel Harms, Sebastian Wild, Viktor Zamaraev

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

Downsampling for Testing and Learning in Product Distributions.

Nathaniel Harms, Yuichi Yoshida

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

Sketching Distances in Monotone Graph Classes.

Louis Esperet, Nathaniel Harms, Andrey Kupavskii

Proceedings of the Approximation, 2022

2021

Randomized Communication and the Implicit Graph Conjecture.

Nathaniel Harms, Sebastian Wild, Viktor Zamaraev

CoRR, 2021

VC dimension and distribution-free sample-based testing.

Eric Blais, Renato Ferreira Pinto Jr., Nathaniel Harms

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

2020

Universal Communication, Universal Graphs, and Graph Labeling.

Nathaniel Harms

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Testing Halfspaces over Rotation-Invariant Distributions.

Nathaniel Harms

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019