Hadley Black

Postdoctoral Researcher

University of California, San Diego

EnCORE Institute

 

email: hablack[at]ucsd[dot]edu

My CV

 

Preprints

Optimal Graph Reconstruction by Counting Connected Components in Induced Subgraphs
Hadley Black, Arya Mazumdar, Barna Saha, Yinzhan Xu
Preprint, 2025.
[short summary]




We study the graph reconstruction problem where one wishes to learn the edge-set of a graph using access to an oracle which returns partial information about a subset (or subsets) of vertices. This line of work began in the late 90's with the edge-detection query model, where the oracle returns whether or not a queried set of vertices contains an edge. There are various ways to strengthen this model. In particular, there have been many works studying additive queries (returns the number of edges in a chosen induced subgraph), cross-additive queries (returns the number of edges between two chosen disjoint sets of vertices), and very recently maximal independent set queries (returns some maximal independent set in a chosen induced subgraph).

In this work we introduce a new query model, where the oracle returns the number of connected components in a chosen induced subgraph. We prove matching upper and lower bounds for the query complexity of graph reconstruction in this model. Moreover, we show that this model is notably different from previously studied models in terms of the amount of adaptivity needed for efficient algorithms (i.e. round complexity).

Learning Partitions with Optimal Query and Round Complexities
Hadley Black, Arya Mazumdar, Barna Saha
Preprint, 2024.
[5-min slides]     [short summary]




We study the "clustering by crowdsourcing" problem where one wishes to reconstruct a hidden k-partition over n elements with access to a pair-query oracle that answers the question "do these two elements belong to the same set?". The goal is to learn the partition exactly while minimizing the number of queries. It is well known that Θ(nk) is necessary and sufficient for adaptive algorithms and Θ(n²) is necessary and sufficient for non-adaptive algorithms. In terms of adaptivity, previous known algorithms using O(nk) queries used k-1 rounds. Minimizing adaptivity is desirable since this allows many queries to be asked in parallel.

What is the fewest rounds of adaptivity that suffice to obtain the optimal O(nk) query complexity? In general, if an algorithm is allowed r rounds of adaptivity, what is the best possible query complexity?

We obtain an algorithm making O(nk) queries, using only O(loglog n) rounds which is a double-exponential improvement over previous works for reasonably large k. Additionally, for every constant r > 0 we characterize the query complexity of algorithms using r rounds, interpolating between the Θ(n²) non-adaptive and Θ(nk) adaptive settings.

We also study the subset query model where the algorithm can query a subset of at most s elements and the oracle returns the number of sets in the partition intersecting the query. We show that the non-adaptive query complexity of this problem is ~Θ(n² / s²), answering a question left open from our previous NeurIPS '24 paper. For adaptive algorithms we show that the query complexity is ~Θ(nk / s²) and we obtain an interpolation between these two cases in terms of rounds of adaptivity, similar to our result for the pair query model.

Publications

Clustering with Non-adaptive Subset Queries
Hadley Black, Euiwoong Lee, Arya Mazumdar, Barna Saha
Neural Information Processing Systems (NeurIPS) 2024.
[arXiv]     [5-min slides]     [short summary]




Over the last decade there has been a lot of interest by the learning theory community in "clustering by crowdsourcing" where the goal is to learn a hidden k-partition over n elements with the ability to ask whether two elements belong to the same set or not (pair queries). Our aim in this work is to design non-adaptive algorithms for this task, which are able to ask all of their queries in parallel. However, there is an Ω(n²) pair query lower bound for non-adaptive algorithms, even when k = 3.

To go beyond this quadratic barrier, we study a generalized query model where the algorithm can ask for the number of sets in the partition intersecting a queried subset. Chakrabarty-Liao (FSTTCS 24) obtained an O(n) query adaptive algorithm and this query complexity is optimal. We obtain a non-adaptive algorithm which comes very close to the optimal query complexity, up to factors of (log k + loglog n). We also study the setting where the algorithm is only allowed to query subsets of size at most s, and show upper and lower bounds of ~O(n² k / s²) and Ω(n² / s²). Finally, we also obtain results for the special case of recovering roughly-balanced partitions and algorithms using two rounds of adaptivity.

Nearly Optimal Bounds for Sample-Based Testing and Learning of k-Monotone Functions
Hadley Black
International Conference on Randomization and Computation (RANDOM) 2024.
[arXiv]     [20-min slides]     [short summary]



Testing monotonicity of Boolean functions is a classic property testing problem dating back to the origins of the field. Most of the literature has focused on the setting where the tester is allowed to request the value of the function at any point (query-access). If you allow access only to uniform random examples then there is an algorithm using roughly exp(√d)) samples which comes from coverting a learning algorithm for monotone functions due to Bshouty-Tamon (J. ACM 1996) into a tester. In this work we obtain a nearly matching lower bound for sample-based testing, showing that this is essentially the best you can do. We also prove nearly optimal lower bounds for functions with larger ranges, and obtain an improved learner/tester for functions over hypergrids and continuous d-dimensional domains.

Testing and Learning Convex Sets in the Ternary Hypercube
Hadley Black, Eric Blais, and Nathaniel Harms
Innovations in Theoretical Computer Science (ITCS) 2024.
[arXiv]     [45-min slides]     [Nathan's art]     [short summary]



Testing convexity of sets in high-dimensions is an extremely natural property testing question for which our understanding is very limited. Thus, the goal of this work is to understand this question over the simplest high-dimensional domain where it can be studied: the ternary hypercube, {-1,0,1}ⁿ. We obtain the following results.

Structural: We prove that the maximum edge boundary of convex sets in the ternary cube is Θ(n^3/4) 3ⁿ.

Testing and learning with sample-access: We prove upper and lower bounds for the task of testing and learning convex sets under the uniform distribution from random examples.

Testing with query-access: We prove nearly matching upper and lower bounds for one-sided error testing of convex sets with non-adaptive queries.

A d^1/2+o(1) Monotonicity Tester for Boolean Functions on d-Dimensional Hypergrids
Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri
Foundations of Computer Science (FOCS) 2023.
Invited to SICOMP special issue.
[arXiv]     [ECCC]     [20-min slides]     [short summary]



This work studies the problem of testing monotonicity of Boolean-valued functions over the d-dimensional, n-width hypergrid. For the special case of n = 2 (the hypercube), a seminal work of Khot-Minzer-Safra (SICOMP 2018) showed that you can test with essentially d^1/2 queries and this is optimal among all non-adaptive testers (Chen-Waingarten-Xie STOC 2017). In our paper from STOC 2023 we obtained such a tester that makes n√d queries.

Can we remove the dependence on n from our STOC 2023 result and obtain a monotonicity tester for Boolean-valued functions over hypergrids that makes √d queries, matching the upper and lower bound for the n = 2 case?

Our main result is a monotonicity tester for such functions that makes d^1/2+o(1) queries, thus resolving the non-adaptive monotonicity testing question for all values of n, up to a d^o(1) factor. Central to our analysis is the inequality obtained in our STOC 2023 paper and our Domain Reduction Theorem from our SODA 2020 paper. We also introduce many new technical ingredients that allow us to replace n by d^o(1) in the query complexity.

Directed Isoperimetric Theorems for Boolean Functions on the Hypergrid and an O^∼(n√d) Monotonicity Tester
Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri
Symposium on Theory of Computing (STOC) 2023.
[arXiv]     [ECCC]     [20-min slides]     [short summary]



This work studies the problem of testing monotonicity of Boolean-valued functions over the d-dimensional, n-width hypergrid. For the special case of n = 2 (the hypercube), a seminal work of Khot-Minzer-Safra (SICOMP 2018) showed that you can test with essentially √d queries. To analyze their tester, they proved a directed analogue of Talagrand's isoperimetric inequality for Boolean functions from 1993. Previous works of ours from SODA 2018 and SODA 2020 showed that for general hypergrids (arbitrary n) there is a d^5/6 query tester. This result was obtained by proving a directed analogue of an inequality by Margulis for hypergrids. The Margulis inequality is weaker than the Talagrand inequality and so a natural next step in this line of inquiry was to try to generalize Khot-Minzer-Safra's directed Talagrand inequality to hypergrids.

Is there a generalization of the directed Talagrand inequality for hypergrids? Can we test monotonicity of Boolean-valued functions over the d-dimensional, n-width hypergrid with d^1/2 queries?

In this paper, we prove a generalization of the directed Talagrand inequality for hypergrids and use it to analyze a tester for Boolean functions on this domain which makes n√d queries. This is the first result to achieve the optimal dependence on d for any n > 2.

Isoperimetric Inequalities for Real-Valued Functions with Applications to Monotonicity Testing
Hadley Black, Iden Kalemaj, and Sofya Raskhodnikova
Random Structures and Algorithms (RSA) 2024.
Preliminary version in International Colloquium on Automata, Languages, and Programming (ICALP) 2023.
[arXiv]     [ECCC]     [Journal]     [Iden's slides]     [short summary]



Monotonicity testing of Boolean functions over the hypercube domain has been studied extensively since its introduction by Goldreich-Goldwasser-Lehman-Ron-Samorodnitsky in 1999. A seminal work of Khot-Minzer-Safra (SICOMP 2018) showed that you can test with essentially √d queries. To analyze their tester, they proved a directed analogue of Talagrand's isoperimetric inequality for Boolean functions from 1993. In contrast, the complexity of monotonicity testing of real-valued functions over the hypercube has been established as Θ(d) with matching upper and lower bounds (Chakrabarty-Seshadhri 2013, Blais-Brody-Matulef 2012), although the lower bound relies on a family of functions with a large range.

What is the complexity of testing monotonicity of functions over the hypercube with range size at most r? Do the known directed isoperimetric inequalities extend beyond the Boolean range?

Our main result is a generalization of Khot-Minzer-Safra's directed Talagrand inequality to real-valued functions whose range consists of any number of elements. To obtain this generalization we prove what we call the Boolean Decomposition Theorem which allows us to "lift" known inequalities for Boolean functions to real-valued functions. Using our generalized directed Talagrand inequality we obtain an optimal tester for functions with range size r. Prior to our work it wasn't known whether such testers exist even for r = 3.

Domain Reduction for Monotonicity Testing: A o(d) Tester for Boolean Functions in d-Dimensions
Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri
Symposium on Discrete Algorithms (SODA) 2020.
[arXiv]     [ECCC]     [short summary]



This work studies the problem of monotonicity testing of Boolean-valued functions over the d-dimensional, n-width hypergrid. A previous work of ours from SODA 2018 showed that there is a o(d) polylog(n) query tester. Other prior work (Dodis-Goldreich-Lehman-Raskhodnikova-Ron-Samorodnitsky 1999, Berman-Raskhodnikova-Yaroslavtsev 2014) showed that O(d) queries are possible with no dependence on n.

Can we remove the polylog(n) dependence from our SODA 2018 result, and more generally is there a black-box method for removing dependencies on n? If so, can testing results over hypergrids be extended to continuous space?

In this paper we showed that n can be replaced by poly(d) in a black-box fashion, thus implying a o(d) tester with no dependence on n by combining with our previous paper. The theorem that achieves this reduction is our main contribution, which we call the Domain Reduction Theorem. Going beyond the hypergrid, we also prove a version of this theorem over d-dimensional continuous spaces and attain a o(d) query tester for this domain.

A o(d) polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n]^d
Hadley Black, Deeparnab Chakrabarty, and C. Seshadhri
Symposium on Discrete Algorithms (SODA) 2018.
[arXiv]     [ECCC]     [short summary]



This work studies the problem of monotonicity testing of Boolean-valued functions over the d-dimensional, n-width hypergrid. Prior to this paper the best known testers had query complexity linear in d, and independent of n. For the special case of n = 2, it was known that o(d)-query testers are possible by exploiting a connection to isoperimetric inequalities for Boolean functions.

To what extent does this connection extend to hypergrids and can we achieve o(d) query testers?

In this paper we gave the first tester for the setting of arbitrary n > 2 with query complexity sublinear in d, although with a poly-logarithmic depedendence on n. The main technical contribution is a directed Margulis-style isoperimetric inequality for hypergrids, generalizing a result from the hypercube setting by Chakrabarty-Seshadhri (STOC 2013).