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
Peter Shor on Quantum Error Correction
[Guest post by Annie Wei who scribed Peter Shor's lecture in our physics and computation seminar. See here for all the posts of this seminar. --Boaz] On October 19, we were lucky enough to have Professor Peter Shor give a guest lecture about quantum error correcting codes. In this blog post, I (Annie Wei) will … Continue reading Peter Shor on Quantum Error Correction
Highlights beyond EC: Call for nominations
[Guest post by Moshe Babaioff --Boaz] "Highlights Beyond EC" Session at EC 2019: Call for Nominations Committee: Mohammad Akbarpour, Moshe Babaioff, Shengwu Li and Ariel Procaccia Following a new tradition started last year, the 2019 ACM Conference on Economics and Computation (EC’19) will host a special session highlighting some of the best work in economics … Continue reading Highlights beyond EC: Call for nominations
HALG 2019 Call for nominations
[Guest post by Piotr Sankowski --Boaz] Call for Nominations - 4th Highlights of Algorithms conference (HALG 2019) Copenhagen, June 14-16, 2019 http://www.halgdiku.dk/ The HALG 2019 conference seeks high-quality nominations for invited talks that will highlight recent advances in algorithmic research. Similarly to previous years, there are two categories of invited talks: A. survey (60 minutes): a … Continue reading HALG 2019 Call for nominations
Where’s that paper?
[Guest post by Eylon Yogev about a Chrome extension he wrote, of which I am a happy user --Boaz] Hi fellow researchers, I'm writing to share a little tool that I have developed with the ambitious goal of boosting research productivity. The tool is a Chrome extension named "Where's that paper?". Before I tell you … Continue reading Where’s that paper?
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
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
Windows On Theory 