(This post is based on part of a lecture delivered by Boriana Gjura and Prayaag Venkat. See also posts by Ben Edelman and Fred Zhang for more context on Quantum Hamiltonian Complexity.) Introduction In this post we present the Area Law conjecture and prove it rigorously, emphasizing the emergence of approximate ground state projectors as … Continue reading A 1D Area Law for Gapped Local Hamiltonians
Algorithmic and Information Theoretic Decoding Thresholds for Low density Parity-Check Code
by Jeremy Dohmann, Vanessa Wong, Venkat Arun Abstract We will discuss error-correcting codes: specifically, low-density parity-check (LDPC) codes. We first describe their construction and information-theoretical decoding thresholds, $latex p_{c}$. Belief propagation (BP) (see Tom's notes) can be used to decode these. We analyze BP to find the maximum error-rate upto which BP succeeds. After this … Continue reading Algorithmic and Information Theoretic Decoding Thresholds for Low density Parity-Check Code
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
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
Windows On Theory 