Nathaniel Harms

44 papers A* 11A 5Journal 27Unranked 1
YearRankTypeTitle / Venue / Authors
2026 A* conf
Feature Selection and Junta Testing are Statistically Equivalent.
SODA
Lorenzo Beretta, Nathaniel Harms, Caleb Koch
2025 A* conf
Constant-Cost Communication Is Not Reducible to k-Hamming Distance.
STOC
Yuting Fang, Mika Göös, Nathaniel Harms, Pooya Hatami
2025 A conf
Equality Is Far Weaker Than Constant-Cost Communication.
APPROX/RANDOM
Mika Göös, Nathaniel Harms, Artur Riazanov
2025 J jnl
Equality is Far Weaker Than Constant-Cost Communication.
Electron. Colloquium Comput. Complex.
Mika Göös, Nathaniel Harms, Artur Riazanov
2025 J jnl
Equality is Far Weaker than Constant-Cost Communication.
CoRR
Mika Göös, Nathaniel Harms, Artur Riazanov
2025 J jnl
Pseudodeterministic Communication Complexity.
CoRR
Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan
2025 J jnl
Pseudodeterministic Communication Complexity.
Electron. Colloquium Comput. Complex.
Mika Göös, Nathaniel Harms, Artur Riazanov, Anastasia Sofronova, Dmitry Sokolov, Weiqiang Yuan
2025 J jnl
Randomized Communication and Implicit Graph Representations.
TheoretiCS
Nathaniel Harms, Sebastian Wild, Viktor Zamaraev
2025 J jnl
Sign-Rank of
CoRR
Mika Göös, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov
2025 J jnl
Sign-Rank of $k$-Hamming Distance is Constant.
Electron. Colloquium Comput. Complex.
Mika Göös, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov
2025 A* conf
Sign-Rank of k-Hamming Distance is Constant.
FOCS
Mika Göös, Nathaniel Harms, Valentin Imbach, Dmitry Sokolov
2025 J jnl
Testing Juntas Optimally with Samples.
CoRR
Lorenzo Beretta, Nathaniel Harms, Caleb Koch
2025 A* conf
Testing Support Size More Efficiently Than Learning Histograms.
STOC
Renato Ferreira Pinto Jr., Nathaniel Harms
2024 — conf
Better Boosting of Communication Oracles, or Not.
FSTTCS
Nathaniel Harms, Artur Riazanov
2024 J jnl
Better Boosting of Communication Oracles, or Not.
CoRR
Nathaniel Harms, Artur Riazanov
2024 J jnl
Constant-Cost Communication is not Reducible to k-Hamming Distance.
CoRR
Yuting Fang, Mika Göös, Nathaniel Harms, Pooya Hatami
2024 A conf
Distribution Testing with a Confused Collector.
ITCS
Renato Ferreira Pinto Jr., Nathaniel Harms
2024 J jnl
Graphs with minimum fractional domatic number.
Discret. Appl. Math.
Maximilien Gadouleau, Nathaniel Harms, George B. Mertzios, Viktor Zamaraev
2024 A* conf
No Complete Problem for Constant-Cost Randomized Communication.
STOC
Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami
2024 J jnl
No Complete Problem for Constant-Cost Randomized Communication.
CoRR
Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami
2024 J jnl
No Complete Problem for Constant-Cost Randomized Communication.
Electron. Colloquium Comput. Complex.
Yuting Fang, Lianna Hambardzumyan, Nathaniel Harms, Pooya Hatami
2024 J jnl
Optimal Adjacency Labels for Subgraphs of Cartesian Products.
SIAM J. Discret. Math.
Louis Esperet, Nathaniel Harms, Viktor Zamaraev
2024 A* conf
Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank.
SODA
Nathaniel Harms, Viktor Zamaraev
2024 J jnl
Testing Support Size More Efficiently Than Learning Histograms.
CoRR
Renato Ferreira Pinto Jr., Nathaniel Harms
2024 A conf
Testing and Learning Convex Sets in the Ternary Hypercube.
ITCS
Hadley Black, Eric Blais, Nathaniel Harms
2023 J jnl
Distribution Testing Under the Parity Trace.
CoRR
Renato Ferreira Pinto Jr., Nathaniel Harms
2023 J jnl
Distribution Testing with a Confused Collector.
CoRR
Renato Ferreira Pinto Jr., Nathaniel Harms
2023 J jnl
Graphs with minimum fractional domatic number.
CoRR
Maximilien Gadouleau, Nathaniel Harms, George B. Mertzios, Viktor Zamaraev
2023 A* conf
Optimal Adjacency Labels for Subgraphs of Cartesian Products.
ICALP
Louis Esperet, Nathaniel Harms, Viktor Zamaraev
2023 J jnl
Randomized Communication and Implicit Representations for Matrices and Graphs of Small Sign-Rank.
CoRR
Nathaniel Harms, Viktor Zamaraev
2023 J jnl
Testing Convexity of Discrete Sets in High Dimensions.
CoRR
Hadley Black, Eric Blais, Nathaniel Harms
2022 A* conf
Downsampling for Testing and Learning in Product Distributions.
ICALP
Nathaniel Harms, Yuichi Yoshida
2022 J jnl
Optimal Adjacency Labels for Subgraphs of Cartesian Products.
CoRR
Louis Esperet, Nathaniel Harms, Viktor Zamaraev
2022 A* conf
Randomized communication and implicit graph representations.
STOC
Nathaniel Harms, Sebastian Wild, Viktor Zamaraev
2022 A conf
Sketching Distances in Monotone Graph Classes.
APPROX/RANDOM
Louis Esperet, Nathaniel Harms, Andrey Kupavskii
2022 J jnl
Sketching Distances in Monotone Graph Classes.
CoRR
Louis Esperet, Nathaniel Harms, Andrey Kupavskii
2021 J jnl
Randomized Communication and the Implicit Graph Conjecture.
CoRR
Nathaniel Harms, Sebastian Wild, Viktor Zamaraev
2021 A* conf
VC dimension and distribution-free sample-based testing.
STOC
Eric Blais, Renato Ferreira Pinto Jr., Nathaniel Harms
2020 J jnl
Downsampling for Testing and Learning in Product Distributions.
CoRR
Nathaniel Harms, Yuichi Yoshida
2020 A conf
Universal Communication, Universal Graphs, and Graph Labeling.
ITCS
Nathaniel Harms
2020 J jnl
VC Dimension and Distribution-Free Sample-Based Testing.
CoRR
Eric Blais, Renato Ferreira Pinto Jr., Nathaniel Harms
2019 A* conf
Testing Halfspaces over Rotation-Invariant Distributions.
SODA
Nathaniel Harms
2019 J jnl
Universal Communication, Universal Graphs, and Graph Labeling.
CoRR
Nathaniel Harms
2018 J jnl
Testing Halfspaces over Rotation-Invariant Distributions.
CoRR
Nathaniel Harms