[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
Rabin postdocs ad is out
[Guest blog from Yaron Singer who is heading the selection committee for the Rabin fellowship this year. In addition to the Rabin fellowship and other postdoc opportunities, this year we also have a new postdoc opportunity in quantum computation and information via the Harvard Quantum Initiative. --Boaz.] Michael O. Rabin Postdoctoral Fellowship in Theoretical … Continue reading Rabin postdocs ad is out
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
Be a program director at NSF!
Guest post by Shuchi Chawla One of the best ways to serve the US-based TCS community is to take up a position at the NSF. Beginning as early as 2019, NSF/CCF is seeking at least one program director for the Algorithmic Foundations core program. This is a rotator position, which is generally two or three years in … Continue reading Be a program director at NSF!
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
FOCS early registration deadline
[Message from Adi Rosen --Boaz] This is a kind reminder that the deadline for the early rate registration fees for FOCS 2018 is this Sunday, September 9, 2018. =================================== FOCS 2018 - Second Call for Participation =================================== https://www.irif.fr/~focs2018/ The 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2018) will take place in Paris, France, … Continue reading FOCS early registration deadline
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
Johan Håstad wins Knuth prize
Congratulations to Johan Håstad for winning the 2018 Knuth prize! Johan of course has done groundbreaking works from constructing pseudorandom generators based on one way functions, through his famous switching lemma, to his PCP theorem that continues to this day to be the blueprint for much of the work in hardness of approximation. A most deserving … Continue reading Johan Håstad wins Knuth prize
Book Review: “Factor Man”
At the recommendation of Craig Gentry, I recently read the book "Factor Man" by Matt Ginsberg. This book is about a computer scientist that discovers an efficient algorithm for SAT, which starts off a international game of intrigue involving the FBI, NSA, Chinese spies, Swiss banks, and even some characters we know such as Steven … Continue reading Book Review: “Factor Man”
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
Windows On Theory 