Abstract. We establish nearly optimal sample complexity bounds for testing the [Formula: see text]-clique property in the dense graph model. Specifically, we show that it is possible to distinguish graphs on [Formula: see text] vertices that have a [Formula: see text]-clique from graphs for which at least [Formula: see text] edges must be added to form a [Formula: see text]-clique by sampling and inspecting a random subgraph on only [Formula: see text] vertices. We also establish new sample complexity bounds for [Formula: see text]-testing [Formula: see text]-colorability. In this case, we show that a sampled subgraph on [Formula: see text] vertices suffices to distinguish [Formula: see text]-colorable graphs from those for which any [Formula: see text]-coloring of the vertices causes at least [Formula: see text] edges to be monochromatic. The new bounds for testing the [Formula: see text]-clique and [Formula: see text]-colorability properties are both obtained via new extensions of the graph container method. This method has been an effective tool for tackling various problems in graph theory and combinatorics. Our results demonstrate that it is also a powerful tool for the analysis of property testing algorithms.

The graph and hypergraph container methods are powerful tools with a wide range of applications across combinatorics. Recently, Blais and Seth (FOCS 2023) showed that the graph container method is particularly well-suited for the analysis of the natural canonical tester for two fundamental graph properties: having a large independent set and k-colorability. In this work, we show that the connection between the container method and property testing extends further along two different directions.

We establish nearly optimal sample complexity bounds for testing the $\rho$-clique property in the dense graph model. Specifically, we show that it is possible to distinguish graphs on n vertices that have a $\rho n$-clique from graphs for which at least $\epsilon n^{2}$ edges must be added to form a $\rho n$-clique by sampling and inspecting a random subgraph on only $\tilde{O}\left(\rho^{3} / \epsilon^{2}\right)$ vertices. We also establish new sample complexity bounds for $\epsilon$-testing k-colorability. In this case, we show that a sampled subgraph on $\tilde{O}(k / \epsilon)$ vertices suffices to distinguish k-colorable graphs from those for which any k-coloring of the vertices causes at least $\epsilon n^{2}$ edges to be monochromatic. The new bounds for testing the $\rho$-clique and k-colorability properties are both obtained via new extensions of the graph container method. This method has been an effective tool for tackling various problems in graph theory and combinatorics. Our results demonstrate that it is also a powerful tool for the analysis of property testing algorithms.

In a real brain, the act of perception is a bidirectional process, depending on both feedforward sensory pathways and feedback pathways that carry expectations. We are interested in how such a neural network might emerge from a biologically plausible learning rule. Other neural network learning methods either only apply to feedforward networks, or employ assumptions (such as weight copying) that render them unlikely in a real brain. Predictive estimators (PEs) offer a better solution to this bidirectional learning scenario. However, PEs also depend on weight copying. In this paper, we propose the symmetric PE (SPE), an architecture that can learn both feedforward and feedback connection weights individually using only locally available information. We demonstrate that the SPE can learn complicated mappings without the use of weight copying. The SPE networks also show promise in deeper architectures.