We study community detection in the \emph{symmetric $k$-stochastic block model}, where $n$ nodes are evenly partitioned into $k$ clusters with intra- and inter-cluster connection probabilities $p$ and $q$, respectively. Our main result is a polynomial-time algorithm that achieves the optimal misclassification rate $\exp(-(1 \pm o(1)) C/k)$, where $C = (\sqrt{pn} - \sqrt{qn})^2$, whenever $C \geq K k^2 \log k$ for some universal constant $K$, matching the Kesten–Stigum ({KS}) threshold up to a $\log k$ factor. Notably, this rate holds even when an adversary corrupts an $\eta \leq \exp(-(1 \pm o(1)) C/k)$ fraction of the nodes. To the best of our knowledge, this optimal error rate was previously only attainable either via computationally inefficient procedures (Zhang and Zhou, 2015) or via polynomial-time algorithms that require strictly stronger assumptions such as $C \geq K k^3$ (Gao et al., 2017). In the node-robust setting, the best known algorithm requires the substantially stronger condition $C \geq K k^{102}$ (Liu and Moitra, 2022). Our results close this gap by providing the first polynomial-time algorithm that achieves the optimal error rate near the {KS} threshold in both settings. Our work has two key technical contributions: (1) we robustify majority voting via the Sum-of-Squares framework, (2) we develop a novel graph bisectioning algorithm via robust majority voting, which allows us to significantly improve the misclassification rate to $1/\mathrm{poly}(k)$ for the initial estimation near the {KS} threshold.

Let X be a d-partite d-dimensional simplicial complex with parts T1,…, Tdand let μ be a distribution on the facets of X. Informally, we say (X, μ) is a path complex if for any ii, G ∈ Tj, K ∈ Tk, we have ${{\mathbb{P}}_\mu }[F,K\mid G] = {{\mathbb{P}}_\mu }[F\mid G]\cdot{{\mathbb{P}}_\mu }[K\mid G]$. We develop a new machinery with ${\mathcal{C}}$-Lorentzian polynomials to show that if all links of X of co-dimension 2 have spectral expansion at most 1/2, then X is a 1/2-local spectral expander. We then prove that one can derive fast-mixing results and log-concavity statements for top-link spectral expanders.We use our machinery to prove fast mixing results for sampling maximal flags of flats of distributive lattices (a.k.a. linear extensions of posets) subject to external fields, and to sample maximal flags of flats of "typical" modular lattices. We also use it to re-prove the Heron-Rota-Welsh conjecture and to prove a conjecture of Chan and Pak which gives a generalization of Stanley’s log-concavity theorem. Lastly, we use it to prove near optimal trickle-down theorems for "sparse complexes" such as constructions by Lubotzky-Samuels-Vishne, Kaufman-Oppenheim, and O’Donnell-Pratt.

Given a matroid M = (E,I), and a total ordering over the elements E, a broken circuit is a circuit where the smallest element is removed and an NBC independent set is an independent set in I with no broken circuit. The set of NBC independent sets of any matroid M define a simplicial complex called the broken circuit complex which has been the subject of intense study in combinatorics. Recently, Adiprasito, Huh and Katz showed that the face of numbers of any broken circuit complex form a log-concave sequence, proving a long-standing conjecture of Rota. We study counting and optimization problems on NBC bases of a generic matroid. We find several fundamental differences with the independent set complex: for example, we show that it is NP-hard to find the max-weight NBC base of a matroid or that the convex hull of NBC bases of a matroid has edges of arbitrary large length. We also give evidence that the natural down-up walk on the space of NBC bases of a matroid may not mix rapidly by showing that for some family of matroids it is NP-hard to count the number of NBC bases after certain conditionings.

Wiki systems form a subclass of the more general Open Collaborative Authoring Systems, where content is created and maintained by a user community. The ability of anyone to edit the content is, at the same time, their strength and their weakness. Anyone can write documents that improve the value of the wiki-system, but at the same time, anyone can also introduce errors into these documents, by accident or on purpose. A security model for wiki-style authoring systems has previously been proposed. This model is based on both static and dynamic document access controls that enforce a simple integrity based security policy. In this paper, we present a new policy for the existing wiki security model, which provides a higher degree of parameterization and adaptability. The new policy is analyzed and compared to the original policy. Our evaluation shows that this new policy provides stronger security when the number of malicious and colluding users is low, but it has a clearly defined level of tolerance in terms of the amount of work required by an attacker to achieve a given probability of violating the policy. Efforts beyond that level, can allow such users to take control of the system, but this is true for all soft security systems. We show that the system parameters can be tuned so that the amount of work required by malicious and colluding users to reach this level is well beyond most attackers' capabilities.