In a distinguishing problem, the input is a sample drawn from one of two distributions and the algorithm is tasked with identifying the source distribution. The performance of a distinguishing algorithm is measured by its advantage, i.e., its incremental probability of success over a random guess. A classic example of a distinguishing problem is the Planted Clique problem, where the input is a graph sampled from either $G(n, 1 / 2)$ - the standard Erdős-Rényi model, or $G(n, 1 / 2, k)$ the Erdős-Rényi model with a clique planted on a random subset of k vertices. The Planted Clique Hypothesis asserts that efficient algorithms cannot achieve advantage better than some absolute constant, say 1/4, whenever $k=n^{1 / 2-\Omega(1)}$. In this work, we aim to precisely understand the optimal distinguishing advantage achievable by efficient algorithms on Planted Clique. We show the following results under the Planted Clique hypothesis:•Optimality of low-degree polynomials: No efficient algorithm can beat the advantage the optimal low-degree polynomial. Concretely, this means that the advantage of any efficient algorithm is at most $(1+o(1)) \cdot k^{2} /(\sqrt{\pi} n)$, which is optimal in light of a simple edge-counting algorithm achieving this bound.•Harder planted distributions: There is an efficiently sampleable distribution ${\mathcal{P}}^{*}$ supported on graphs containing k cliques such that no efficient algorithm can distinguish ${\mathcal{P}}^{*}$ from $G(n, 1 / 2)$ with advantage $n^{-d}$ for an arbitrarily large constant d. In other words, there exist alternate planted distributions that are much harder than $G(n, 1 / 2, k)$.Along the way, we prove a constructive hard-core lemma for a broad class of distributions with respect to low-degree polynomials. This result is applicable much more widely beyond Planted Clique and might be of independent interest.

The problem of sparsifying a graph or a hypergraph while approximately preserving its cut structure has been extensively studied and has many applications. In a seminal work, Benczúr and Karger (1996) showed that given any n-vertex undirected weighted graph G and a parameter ε ∈ (0,1), there is a near-linear time algorithm that outputs a weighted subgraph G' of G of size Õ(n/ε²) such that the weight of every cut in G is preserved to within a (1 ± ε)-factor in G'. The graph G' is referred to as a (1 ± ε)-approximate cut sparsifier of G. Subsequent recent work has obtained a similar result for the more general problem of hypergraph cut sparsifiers. However, all known sparsification algorithms require Ω(n + m) time where n denotes the number of vertices and m denotes the number of hyperedges in the hypergraph. Since m can be exponentially large in n, a natural question is if it is possible to create a hypergraph cut sparsifier in time polynomial in n, independent of the number of edges. We resolve this question in the affirmative, giving the first sublinear time algorithm for this problem, given appropriate query access to the hypergraph. Specifically, we design an algorithm that constructs a (1 ± ε)-approximate cut sparsifier of a hypergraph H(V,E) in polynomial time in n, independent of the number of hyperedges, when given access to the hypergraph using the following two queries: 1) given any cut (S, ̄S), return the size |δ_E(S)| (cut value queries); and 2) given any cut (S, ̄S), return a uniformly at random edge crossing the cut (cut edge sample queries). Our algorithm outputs a sparsifier with Õ(n/ε²) edges, which is essentially optimal. We then extend our results to show that cut value and cut edge sample queries can also be used to construct hypergraph spectral sparsifiers in poly(n) time, independent of the number of hyperedges. We complement the algorithmic results above by showing that any algorithm that has access to only one of the above two types of queries can not give a hypergraph cut sparsifier in time that is polynomial in n. Finally, we show that our algorithmic results also hold if we replace the cut edge sample queries with a pair neighbor sample query that for any pair of vertices, returns a random edge incident on them. In contrast, we show that having access only to cut value queries and queries that return a random edge incident on a given single vertex, is not sufficient.

Cuts in graphs are a fundamental object of study, and play a central role in the study of graph algorithms. The problem of sparsifying a graph while approximately preserving its cut structure has been extensively studied and has many applications. In a seminal work, Benczúr and Karger (1996) showed that given any n-vertex undirected weighted graph G and a parameter ε ∈ (0,1), there is a near-linear time algorithm that outputs a weighted subgraph G' of G of size Õ(n/ε2) such that the weight of every cut in G is preserved to within a ( 1±ε)-factor in G'. The graph G' is referred to as a ( 1±ε)-approximate cut sparsifier of G. A natural question is if such cut-preserving sparsifiers also exist for hypergraphs. Kogan and Krauthgamer (2015) initiated a study of this question and showed that given any weighted hypergraph H where the cardinality of each hyperedge is bounded by r, there is a polynomial-time algorithm to find a ( 1±ε)-approximate cut sparsifier of H of size Õ([nr/(ε2)]). Since r can be as large as n, in general, this gives a hypergraph cut sparsifier of size Õ(n2/ε2), which is a factor n larger than the Benczúr-Karger bound for graphs. It has been an open question whether or not Benczúr-Karger bound is achievable on hypergraphs. In this work, we resolve this question in the affirmative by giving a new polynomial-time algorithm for creating hypergraph sparsifiers of size Õ(n/ε2).