https://wiki.simons.berkeley.edu/ 2026-08-08T01:46:10+00:00 https://wiki.simons.berkeley.edu/ https://wiki.simons.berkeley.edu/lib/exe/fetch.php?media=wiki:dokuwiki.svg text/html 2025-12-22T23:45:17+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.simons.berkeley.edu/doku.php?id=hd20:algorithms-for-ising-perceptron&rev=1766447117&do=diff Algorithmic Lower Bounds on the Storage Capacity of the Binary Perceptron Contact: Lenka Zdeborova Consider the *binary perceptron* with $n$ variables and $\alpha n$ halfspaces, defined as follows: $m = \alpha n$ random unit vectors $w_1,\ldots,w_{m}$ are drawn independently, then we consider the set of *solutions* $x \in \{ \pm 1\}^n$$$\langle x, w_i \rangle \geq \kappa ~~~~ \mbox{for all}~~~~ 1 \le i\leq m, $$$\kappa \in \mathbb{R}$$\alpha_c = \alpha_c(\kappa)$$\alpha > \alpha_c(\kappa)$$\al… text/html 2025-12-22T23:45:17+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.simons.berkeley.edu/doku.php?id=hd20:boot-camp&rev=1766447117&do=diff PGCHD boot camp: reading resources Crash course on PCP (Irit Dinur and Dana Moshkovitz) PCP course page (Dinur, Moshkovitz) Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming (Goemans, Williamson) A parallel repetition theorem (Raz) Some optimal inapproximability results (Håstad) Optimal inapproximability results for MAX‐CUT and other 2‐variable CSPs? (Khot, Kindler, Mossel, O'Donnell) Noise stability of functions with low influenc… text/html 2025-12-22T23:45:17+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.simons.berkeley.edu/doku.php?id=hd20:diameter-of-gaussian-polytopes&rev=1766447117&do=diff Diameter of Random (Gaussian) Polytopes Contact: Daniel Dadush Meeting times: Thursdays 9:30am Pacific at <https://us02web.zoom.us/j/87850810181> Given a polytope $P$ in $n$ variables and $m$ constraints, which we can write as $$P = \{x\in\mathbb{R}^n : Ax \leq b\}$$ we are interested in the *diameter* of $P$, i.e., the maximum length of the shortest path between any two $v,w\in P$$P$$m-n$$n$$m$$\operatorname{diam}(P) = O(m\cdot 2^n)$$\operatorname{diam}(P) = m^{O(\log n)}$$P=\{x\in\mathbb{… text/html 2025-12-22T23:45:17+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.simons.berkeley.edu/doku.php?id=hd20:glauber-dynamics-for-sk&rev=1766447117&do=diff Rapid Mixing of Glauber Dynamics for the Sherrington-Kirkpatrick Model Contact: Andrea Montanari Consider the Sherrington-Kirkpatrick spin glass model at inverse temperature $\beta > 0$ -- that is, the Gibbs distribution over $\{\pm 1\}^n$ given by $\mu(x) \propto \exp \{ \tfrac \beta 2 \langle x, A x \rangle \}$ where $A \sim \text{GOE}(n)$; i.e. $A$ is symmetric and for $i \leq j$$A_{ij} \sim \mathcal{N}(0,1/n)$$\{ \pm 1\}^n$$x$$i \in [n]$$b \in \{ \pm 1\}$$i$$\mu$$x_{-i}$$x'$$x'_{-i} = x_{-… text/html 2025-12-22T23:45:17+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.simons.berkeley.edu/doku.php?id=hd20:learning-and-testing-in-hd&rev=1766447117&do=diff Learning and Testing in High Dimensions Reading Group Logistics Every Friday from 12-2 pm Pacific (Berkeley) Time Zoom link will be shared on discord and the hd-visitors mailing lists. Schedule (tentative, regularly updated throughout the semester) text/html 2025-12-22T23:45:17+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.simons.berkeley.edu/doku.php?id=hd20:predicting-and-explaining-statistical-computational-gaps&rev=1766447117&do=diff Predicting and explaining statistical-computational gaps: Reading group A major thrust of information theory is to establish guarantees for learning procedures that are algorithm-independent, addressing questions about sufficient data like, “How much data is necessary and sufficient for any algorithm to be able to extract useful information?” Algorithm-agnostic impossibility results of this type are informative for learning as they provide conditions under which no method can hope to perform we… text/html 2025-12-22T23:45:17+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.simons.berkeley.edu/doku.php?id=hd20:sdp-universality&rev=1766447117&do=diff Universality for Semidefinite Optimization Contact: Sidhanth Mohanty Famously, Parisi predicted and Talagrand proved the following result concerning ground states of the Sherrington-Kirkpatrick spin glass -- also known to computer scientists as the Max-$2$$$ \max_{x \in \{ \pm 1\}^n} \frac{\langle G, xx^\top \rangle}{n^{3/2}} = 1.5235\ldots \pm o(1) \text{ whp for $$$ The matrix $$ does not even have to be Gaussian --- (Carmona-Hu) show that the same holds for a large //universality class//: t… text/html 2025-12-22T23:45:17+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.simons.berkeley.edu/doku.php?id=hd20:start&rev=1766447117&do=diff Probability, Geometry, and Computation in High Dimensions, Fall 2020 Reading groups Learning and testing in HD Stochastic localization Predicting and explaining statistical-computational gaps Polymath projects SDP universality Verifying communities Glauber dynamics for SK Algorithms for Ising perceptron The Courtade-Kumar conjecture Diameter of Gaussian polytopes All HD seminars and workshops 08/19-08/28 boot camp workshop: event page and reading resources 09/03 seminar Andrea Mont… text/html 2025-12-22T23:45:17+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.simons.berkeley.edu/doku.php?id=hd20:stochastic-localization&rev=1766447117&do=diff Abstract: Stochastic localization is a way of decomposing a probability measure on a high-dimensional space into a mixture of simpler measures in a “Markovian” way. These simpler measures are “localized” in the sense that they are concentrated on smaller (random) subsets of the original space. The decomposition turns out to be useful in understanding the original measure. This technique has found applications in high-dimensional geometry and probability, notably in problems related to the Kan… text/html 2025-12-22T23:45:17+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.simons.berkeley.edu/doku.php?id=hd20:the-courtade-kumar-conjecture&rev=1766447117&do=diff Data Processing for Correlated Samples from the Hypercube Contact: Thomas Courtade Fix $\alpha \in (0,1)$. Let $X = (X_1, \dots, X_n)$ and $Y = (Y_1, \dots, Y_n)$ each be uniformly distributed on $\{0,1\}^n$, with $\Pr\{X_i \neq Y_i\} = \alpha$ for all $1 \leq i \leq n$. Problem: For any $f: \{0,1\}^n\rightarrow \{0,1\}$, we have $I(f(X); Y) \leq 1-h_2(\alpha)$, where $I$ is the mutual information and $h_2(\alpha)$ is the binary entropy function. Both are computed with respect to the base-2 l… text/html 2025-12-22T23:45:17+00:00 Anonymous (anonymous@undisclosed.example.com) https://wiki.simons.berkeley.edu/doku.php?id=hd20:verifying-communities&rev=1766447117&do=diff Verifying communities Contact: Prasad Raghavendra Studying algorithms which verify solutions to computational problems -- as opposed to finding solutions -- has been enormously fruitful in the worst-case complexity theory, where it leads to the theory of NP-completeness. Can it pay off for average-case problems as well? What follows is just one concrete problem in this direction.$k$$d$$[n]$$k$$\{i,j\}$$G$$\tfrac d n (1 + \varepsilon(\mathbf{1}(i,j \text{ in same community}) - \tfrac 1k))$$\va…