Ising Perceptron under Gaussian Disorder, and k-NAE-SAT

Blog Post By: Patrick Guo, Vinh-Kha Le, Shyam Narayanan, and David Stoner Methods in statistical physics are known to be extremely useful for understanding certain problems in theoretical computer science. Physical observations can motivate the underlying theoretical models, which in turn explain some of the physical phenomena. This post is based on Professor Nike Sun's … Continue reading Ising Perceptron under Gaussian Disorder, and k-NAE-SAT

Approximating Partition Functions

[Guest post by Alex Kelser, Alex Lin, Amil Merchant, and Suproteem Sarkar, scribing for a lecture by Andrej Risteski.] Andrej Risteski: Approximating Partition Functions via Variational Methods and Taylor Series For a probability distribution defined up to a constant of proportionality, we have already seen the partition function. To refresh your memory, given a probability … Continue reading Approximating Partition Functions

Belief Propagation and the Stochastic Block Model

[Guest post by Thomas Orton who presented a lecture on this in our  physics and computation seminar --Boaz] Introduction This blog post is a continuation of the CS229R lecture series. Last week, we saw how certain computational problems like 3SAT exhibit a thresholding behavior, similar to a phase transition in a physical system. In this post, … Continue reading Belief Propagation and the Stochastic Block Model

Statistical Physics: an introduction in two parts

Statistical physics has deep connections to many computational problems, including statistical inference, counting and sampling, and optimization. Perhaps especially compelling are the field's insights and intuitions regarding "average-case complexity" and information-computation gaps. These are topics for which the traditional theoretical CS approaches seem ill-suited, while on the other hand statistical physics has supplied a rich … Continue reading Statistical Physics: an introduction in two parts

Black holes, paradoxes, and computational complexity

(Thanks so much to Scott Aaronson for giving me many pointers, insights, explanations, and corrections that greatly improved this post. As I'm a beginner to physics, the standard caveat holds doubly here: Scott is by no means responsible to any of my remaining technical mistakes and philosophical misconceptions.) One of the interesting features of physics … Continue reading Black holes, paradoxes, and computational complexity

Physics Envy

There is something cool about physics. Black holes, anti-matter, "God's particle": it all sounds so exciting. While our TCS "mental experiments" typically involve restricting the inputs of constant-depth circuits, physicists talk about jumping into black holes while holding a dictionary. Physicists also have a knack for names: notions such as "uncertainty principle" or "monogamy of … Continue reading Physics Envy

Statistical physics dictionary

I've always been curious about the statistical physics approach to problems from computer science. The physics-inspired algorithm survey propagation is the current champion for random 3SAT instances, statistical-physics phase transitions have been suggested as explaining computational difficulty, and statistical physics has even been invoked to explain why deep learning algorithms seem to often converge to … Continue reading Statistical physics dictionary

The different forms of quantum computing skepticism

(see also pdf version)   Quantum computing is one of the most exciting developments of computer science in the last decades. But this concept is not without its critics, often known as "quantum computing skeptics" or "skeptics" for short. The debate on quantum computing can sometimes confuse the physical and mathematical aspects of this question, … Continue reading The different forms of quantum computing skepticism

On “external” definitions for computation

I recently stumbled upon a fascinating talk by the physicist Nima Arkani-Hamed on the  The Morality of Fundamental Physics. ("Moral" here is in the sense of "morally correct", as opposed to understanding the impact of science on society. Perhaps "beauty" would have been a better term.) In this talk, Arkani-Hamed describes the quest for finding scientific theories … Continue reading On “external” definitions for computation