Skip to content

Sensitivity conjecture proved!

July 2, 2019
by

In a recent breakthrough, Hao Huang gave a 6 page paper proving the longstanding sensitivity conjecture. (Hat tip, Scott Aaronson and Gil Kalai. See this stackexchange post and this paper of Avishai for some links to the literature on this.)

The proof is beautiful and simple. I will write a few words here, but it is probably easier for you to just read the paper. The sensitivity conjecture was known to follow from the following statement: let G_n be the Boolean Cube which is the degree n graph on N=2^n vertices identified with \{0,1\}^n such that for every x,y\in \{0,1\}^n, x \sim y if their Hamming distance is one. Then, the maximum degree of every subgraph H of G_n of size >N/2 is at least \sqrt{n}.

Hao proves the above statement by showing that there is a signing of the N\times N adjacency matrix of G_n that turns it into a matrix with N/2 eigenvalues equaling +\sqrt{n} and N/2 eigenvalues equaling -\sqrt{n}. That is, he shows (using a simple but clever inductive argument, see the 5 line proof of his Lemma 2.2) that there is an N\times N matrix A with entries in \{ 0, \pm 1 \} whose nonzero entries correspond to the edges of the Boolean cube, and such that all the N eigenvalues of A are \pm \sqrt{n} and they sum up to zero. (Note that this makes sense since A should have the same Frobenius norm as the adjacency matrix of G_n. The Frobenius norm squared is both the sum of squares of entries, which is N\cdot n for G_n which is a degree n graph, and also equal to the sum of squares of the eigenvalues, which is N\cdot n if all eigenvalues are \pm \sqrt{n}.)

Once you have such a signing, the result follows from Cauchy’s Interlace Theorem that says that for every N\times N matrix A and any M\times M matrix B that is a principle sub-matrix of A,

\lambda_{1+N-M}(A) \leq \lambda_1(B) \leq \lambda_1(A)

where \lambda_1(A) \geq \lambda_2(A) \cdots \geq \lambda_N(A) are the eigenvalues of A and \lambda_1(B) is the maximum eigenvalue of B. A corollary of this (which is the only fact we need) is that if A has its top eigenvalue \lambda_1(A) with multiplicity K (i.e., \lambda_1(A)=\lambda_K(A)), then every principle sub-matrix B of order larger than N-K will satisfy \lambda_1(B) = \lambda_1(A). (In fact, we only need \lambda_1(B) \geq \lambda_1(A).)

Indeed, suppose that H is a subgraph of the Boolean cube of size M>N/2. Then the principle submatrix B of A corresponding to the vertices of H satisfies \lambda_1(B) \geq \lambda_{1+N-M}(A) = \sqrt{n} (since M>N/2 and the first N/2 eigenvalues of A are +\sqrt{n}). But it’s easy to show that for every matrix B the maximum eigenvalue of B is upper bounded by the maximum \ell_1 norm of its rows, which in our case is the maximum degree of the graph H.

4 Comments
from → Uncategorized

TCS Women at STOC (guest post by Virginia Williams)

June 20, 2019
by
[Guest post by Virgi Vassilevska Williams on the TCS women program at STOC. In particular the TCS Women Spotlight workshop has a great program and is open to all. –Boaz]
Dear all,
The TCS Women 2019 program is finalized: https://sigact.org/tcswomen/tcs-women-2019/. Here are some details:
On June 23rd, we have our TCS Women Spotlight workshop from 2 pm to 5 pm. This will feature an inspirational talk by Ronitt Rubinfeld (MIT & Tel Aviv University)–“Comedy of Errors”, and rising stars talks by Naama Ben-David (CMU), Debarati Das (Charles University), Andrea Lincoln (MIT) and Oxana Poburinnaya (Boston University). The workshop is open to all and we would love to see you all there.
 
On June 24th, we have the TCS Women lunch and panel of distinguished researchers from academia and industries. This year’s panelists include Shuchi Chawla (University of Wisconsin), Julia Chuzhoy (TTIC), Edith Cohen (Google), Faith Ellen (University of Toronto), Rachel Lin (University of Washington) and Nutan Limaye (Indian Institute of Technology, Mumbai). The event is open to all women participants of FCRC.
 
In addition to these, there will be a TCS Women poster session held jointly with the STOC poster session on June 24th. Fourteen women researchers will be presenting posters on their research. More information is available on our website. All are welcome. 
 
We are providing travel scholarships to more than forty women students this year to attend STOC and FCRC. We secured funding from the NSF, Akamai, Amazon, Google and Microsoft. Thank you!
 
Looking forward to seeing you soon!
 
Best wishes,
The TCS Women organizers
Comments Off on TCS Women at STOC (guest post by Virginia Williams)
from → Uncategorized

Intro-TCS rebooted

June 10, 2019
by

This Spring and Summer I am doing some major editing to my text on introduction to theoretical computer science. I am adding figures (176 so far and counting..), examples, exercises, simplifying explanations, reducing footnotes, and mainly trying to make it more “user friendly” and less “idiosyncratic”. I am now adding in all chapters figures such as the following that outline the main results and how they are connected to one another.

Overview of the results in "Code and Data" chapter presenting universal circuit and the counting lower bound
Overview of the results in “Code and Data” chapter presenting universal circuit and the counting lower bound
Overview of the results in the "loops and infinity" chapter defining Turing Machines. A running theme in the book is the emphasis on distinguishing specification (the mathematical function being computed) from implementation (the algorithm, machine, or program doing the computation).
Overview of the results in the “loops and infinity” chapter defining Turing Machines. A running theme in the book is the emphasis on distinguishing specification (the mathematical function being computed) from implementation (the algorithm, machine, or program doing the computation).
Overview of the results in the chapter on universality and uncomputability. We use Sipser's metaphor on reductions as transforming a "pig that can whistle" (e.g., an algorithm for the deciding if a function halts on the zero input) into a "horse that can fly" (e.g., an algorithm for the general halting problem).
Overview of the results in the chapter on universality and uncomputability. We use Sipser’s metaphor on reductions as transforming a “pig that can whistle” (e.g., an algorithm for the deciding if a function halts on the zero input) into a “horse that can fly” (e.g., an algorithm for the general halting problem).




Specifically, in the previous version of the book I used programming languages as the main computational models. While I still think this is the right way if we were to “start from scratch”, these idiosyncratic models made it harder for students to use other resources such as textbooks and lecture notes. They also make it more difficult for instructors to use individual chapters in their courses without committing to using the full book.

Hence in the new revision the standard models of Turing Machines and Boolean Circuits are front and center. We do talk about the programming-language equivalents as well, since I think they are important for the connection to practice and some concepts such as the duality of code and data are better explained in these terms. I also use the programming-language variants to demonstrate concepts to students in code including compilers from circuits to straightline programs, various “syntactic sugar” transformations, and the Cook-Levin Theorem and NP reductions.

An equivalent description of a finite computation using straight-line programs and Boolean circuits. The supplementary code contains a Python implementation of the transformation between these two representations.



One thing did not change – we still start with Boolean Circuits rather than automata as the initial computational model. Boolean circuits are closer to actual implementations of computing, are a finite (and hence simpler) model, but one that is non-trivial enough to allow showing some important theorems early in the course including existence of a circuit for computing every finite function, the existence of a circuit to evaluate other circuits, and the counting lower bound as well as the counting lower bound.

Circuits are also crucial for later material in the course since they make the proof of the Cook-Levin Theorem much simpler and cleaner, allow talking about results such as BPP \subseteq P_{/poly} and Sipser-Gacs, and are crucial to be even able to state results in advanced topics such as derandomization, cryptography, and quantum computing.

Reduction of SAT to independent set from Chapter 13 in the book. On the right is the Python code implementing the reduction, on the left is the resulting independent set.
An instance of independent set obtained by chaining together the proof of the Cook-Levin Theorem together with the reduction of 3SAT to independent set. Figure taken from Chapter 14.



We do cover automata as well, including the equivalence of regular expressions and deterministic finite automata. We also cover context-free grammars (though not pushdown automata) and the λ calculus, including its equivalence with Turing Machines and the Y combinator (see also this notebook)

I have also done some work on the technical side of producing the book. The book is written in markdown. Markdown has many advantages but it wasn’t designed for 600-page technical books full of equations and cross-references so I did need to use some extensions to it. I am using pandoc (and my own filter) to produce both the HTML and LaTeX/PDF versions of the book.

There is still more work to do. I plan to add a chapter on space complexity and on proofs and computation (including both interactive and zero knowledge proofs, as well as the “propositions as types” correspondence between proofs and programs). I need to add more examples and exercises. There are also still several chapters where the text is “rough around the edges”.

As usual, the latest version of the book is available on https://introtcs.org . If you see any typo, problem, etc.., please post an issue on the GitHub repository (you can also make a pull request for small typo fixes if you prefer)

Comments Off on Intro-TCS rebooted
from → Uncategorized

ITCS 20 call for papers (guest post by Thomas Vidick)

June 4, 2019
by

We invite you to submit your papers to the 11th Innovations in
Theoretical Computer Science (ITCS). The conference will be held at
the University of Washington in Seattle, Washington from January 12-14,
2020.

ITCS seeks to promote research that carries a strong conceptual message
(e.g., introducing a new concept, model or understanding, opening a new
line of inquiry within traditional or interdisciplinary areas,
introducing new mathematical techniques and methodologies, or new
applications of known techniques). ITCS welcomes both conceptual and
technical contributions whose contents will advance and inspire the
greater theory community.

Submission deadline: September 9, 2019 (05:59pm PDT)
Notification to authors: October 31, 2019
Conference dates: January 12-14, 2020

See the website at http://itcs-conf.org/itcs20/itcs20-cfp.html for
detailed information regarding submissions.

Program committee

Nikhil Bansal, CWI + TU Eindhoven
Nir Bitansky, Tel-Aviv University
Clement Canonne, Stanford
Timothy Chan, University of Ilinois at Urbana-Champaign
Edith Cohen, Google and Tel-Aviv University
Shaddin Dughmi, University of Southern California
Sumegha Garg, Princeton
Ankit Garg, Microsoft research
Ran Gelles, Bar-Ilan University
Elena Grigorescu, Purdue
Tom Gur, University of Warwick
Sandy Irani, UC Irvine
Dakshita Khurana, University of Illinois at Urbana-Champaign
Antonina Kolokolova, Memorial University of Newfoundland.
Pravesh Kothari, Carnegie Mellon University
Rasmus Kyng, Harvard
Katrina Ligett, Hebrew University
Nutan Limaye, IIT Bombay
Pasin Manurangsi, UC Berkeley
Tamara Mchedlidze, Karlsruhe Institute of Technology
Dana Moshkovitz, UT Austin
Jelani Nelson, UC Berkeley
Merav Parter, Weizmann Institute
Krzysztof Pietrzak, IST Austria
Elaine Shi, Cornell
Piyush Srivastava, Tata Institute of Fundamental Research, Mumbai
Li-Yang Tan, Stanford
Madhur Tulsiani, TTIC
Gregory Valiant, Stanford
Thomas Vidick, California Institute of Technology (chair)
Virginia Vassilevska Williams, MIT
Ronald de Wolf, CWI and University of Amsterdam
David Woodruff, Carnegie Mellon University

2 Comments
from → Uncategorized

TCS Women

April 9, 2019
by

[Guest post from Virginia Vassilevska Williams –Boaz]

Barna Saha, Sofya Raskhodnikova and I are organizing the second annual TCS Women event at STOC’19. We had an event at STOC’18 and it went really well. We envision an exciting program for the TCS Women event at STOC 2019. The details about the program are forthcoming.  The new TCS Women website is here: https://sigact.org/tcswomen/. There you can learn more about our initiative.

In addition to the event, we have secured generous funding (similar to last year) from the NSF and industrial partners such as Akamai, Amazon, Google and Microsoft for travel grants for women and underrepresented minority students and postdocs to attend STOC. These grants are separate from the STOC travel awards and you can apply to both.

The application deadline for the TCS Women travel scholarship is April 25th, 2019. The information on how to apply is available here https://sigact.org/tcswomen/tcs-women-travel-scholarship/. We hope to support as many women and underrepresented minority students and postdocs as possible all over the globe to come to STOC and FCRC. The participants will also have the opportunity to present their work at the STOC poster session.
If you are aware of eligible students (not only PhD) who are interested in attending STOC, please encourage them to apply.

Best wishes,

Virginia on behalf of the TCS Women organizers

Comments Off on TCS Women
from → Uncategorized

Donate to AddisCoder!

April 9, 2019
by

In 2011, as a graduate student Jelani Nelson founded the AddisCoder course on algorithms and coding for high schoolers in Addis Ababa Ethiopia. Since then the course has been offered twice more, and this summer it will occur again for the fourth time. Over 330 students have completed the course, and some of its alumni are now students in top institutions in the U.S., Ethiopia, and all over the world. I was a lecturer in this course in 2016 and will be again this summer (together with Jelani, Timnit Gebru, and Daniel Kang).

The students in AddisCoder come from all over Ethiopia, and many have never considered computer science as a potential field of study or even touched a computer. Once when meeting an alum, I asked whether he enjoyed the course. He told me that he didn’t just enjoy it, it was a lifechanging experience for him, and I believe the same holds for many other graduates.

The reason for this post is that AddisCoder is now a tax-exempt non profit organization, which you can donate to through our website. It is a fairly lean operation, but funds are needed for travel of teaching staff (with TA’s that come from all over the world). Please consider supporting AddisCoder yourself (any amount helps!), and forward this information to any friends or colleagues. If you work for a company that might be interested in supporting AddisCoder, you can contact Jelani at the email minilek+addiscoder@gmail.com .

Comments Off on Donate to AddisCoder!
from → Uncategorized

PCP Fest videos

April 6, 2019
by

In December I participated in the wonderful “PCP Fest” workshop in Tel Aviv. The videos from these workshops are now online on their youtube channel.

The channel contains not just videos of talks but also two wide ranging interviews of Alon Rosen with Avi Wigderson and Christos Papadimitriou, as well as a discussion between them. I think many people, especially students, might find these interviews inspiring. They cover Avi’s and Christos’ personal and intellectual journeys, that are similar in some ways and quite different in others.

1 Comment
from → Uncategorized
« Older Entries