Author: Omer Reingold

A Social Blogger

~ Omer Reingold ~ 2 Comments

Since the close of MSR-SVC, I seem to have lost my taste for blogging. I think I finally know why: For me blogging is a social activity. I loved discussing the posts with my down-the-hall colleagues and friends. So, to regain this wonderful feeling, we (Stanford Theory) are opening a new theory group blog – Theory Dish. I hope this experience would be as great as starting “Windows on Theory” has been (for us and the readers).

As for “Windows on Theory,” we seem to have left the wonderful Boaz to hold the fort on his own, which he has done valiantly so far. Surely, recruiting Boaz has been one of my greatest contributions to the world of theory blogging and I simply love his posts. Nevertheless, I am not leaving Windows on Theory and we have great plans for it, including guest posts and more. Stay tuned!

TOCA-Revolution Begins: Nov 4

~ Omer Reingold ~ 3 Comments

The success of TOC is due to the intrinsic intellectual merit of our field but also due to many fruitful connections: connections between subfields of TOC (see Avi Wigderson’s depth through breadth), connection with Mathematics, connections with other fields in Science and Humanities via the computational lens, and connections with industry. All of these powerful connections contribute to the impact and vitality of TOC.

In this spirit, the theory group at Stanford and our theory colleagues all around the Silicon Valley are establishing a forum for continuous collaboration (through meetings and electronic means) between theoreticians in industry and academia in the SF Bay Area. We name it TOCA-SV. TOCA stands for Theory of Computing Associated and also, quite appropriately, means touches in Spanish. Like others, calling for a revolution: I hope that TOCA groups will surface all over.

Our first meeting will take place at Stanford on November 4th. Please join us if you are around and please don’t forget to register.

Students who want to present in this event (in a lightning-talk session) are asked to email us at tocasvalley@gmail.com. Please specify your name, affiliation, adviser (if you have one), year and email address. We will try to accommodate as many as possible (but future opportunities are planed).

Finally, to stay in touch for future information, please join our Google group.

Occupy TOC, power to the people, onwards and upwards or whatever seems appropriate here 🙂

Stanford, Here I Come

~ Omer Reingold ~ 9 Comments

Most of the stories in the research-life story project (including mine) are already processed and often told with some well-packaged perspective the teller wants to share. Today I am sharing a moment as it unfolds: Come next fall, I’ll be joining the Stanford CS Department. I’m very excited.

Since the closing of MSR-SV, I’ve been lending a hand in efforts to create a new distributed-system group at Samsung Research America. But in a few months I’ll be returning to academia. Returning may be too strong of a word. The place where I was “academically born” and where I served as a CS Professor was The Weizmann Institute of Science. Weizmann feels to me (and I hope it will always feel) like home. But Weizmann and Stanford are very different. So the question that burns in me towards next year (and towards the decades I hope to spend at Stanford) is what can I do at Stanford that I couldn’t at my past wonderful work places?

Of course, the main thing I plan to do is (hopefully good) research. With the excellent Stanford students and faculty (theory and otherwise), I am sure it will be a lot of fun. But my feeling is that this should not be it. Buzzing in my mind are many ideas (which I expect would require many years and some/most would never happen): New intro courses to CS (targeting different populations- Humanities, Math, Sciences, Information Science), new popular science books, new programs for K-12 education, a stronger connection with local theorists in industry, and perhaps most importantly to me is contributing to making academia a more humane place for students, junior faculty and in fact for all of us. The research-life story project was motivated by similar desires, and I hope to join efforts around the world that take this approach much further. I have the feeling that Stanford would be a particularly suitable place to promote these agendas (and others).

So what would you be passionate about in my shoes?

Outreach on Fairness, Privacy and Data Analysis

~ Omer Reingold ~ 2 Comments
  1. A lovely interview with Cynthia Dwork in the New York Times on bias in computations. In particular, discussing our work (joint with Moritz Hardt, Toni Pitassi and Rich Zemel) on Fairness through Awareness.
  1. Our Science article, The reusable holdout: Preserving validity in adaptive data analysis (joint with Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi and Aaron Roth), is out.

—-

update (8/16/2015): On Privacy and Anonymisation (with Cynthia Dwork and Salil Vadhan) in The Economist

Popularizing TOC

~ Omer Reingold ~ 12 Comments

It is hard to overestimate the impact of Popular Science books such as “A Brief History of Time” and “Chaos: Making a New Science” on Scientific Research. The indirect impact of popularizing Science and Scientific Education often surpass the direct contribution that most scientists can hope to achieve in their life time. For this reason, many of the greatest scientists (including in our field) choose to invest considerable time in this blessed endeavor. I personally believe that the Theory of Computing deserves more popularization than it gets (and I hope to someday contribute my share). Nevertheless, this post is meant as a tribute to our colleagues who already made wonderful such contributions. I will continuously edit this post with TOC popular books and educational resources (based on my own knowledge and suggestions in the comments).

Popular TOC books:

Scott Aaronson, Quantum Computing since Democritus

Martin Davis, Engines of Logic: Mathematicians and the Origin of the Computer

A. K. Dewdney, The New Turing Omnibus: Sixty-Six Excursions in Computer Science

David Harel, Computers Ltd.: What They Really Can’t Do

David Harel with Yishai Feldman, Algorithmics: The Spirit of Computing

Douglas Hofstadter: Gödel, Escher, Bach: An Eternal Golden Braid

Lance Fortnow, The Golden Ticket: P, NP, and the Search for the Impossible

Cristopher Moore and Stephan Mertens, The Nature of Computation

Dennis Shasha and Cathy Lazere, Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists

Leslie Valiant, Probably Approximately Correct: Nature’s Algorithms for Learning and Prospering in a Complex World

Leslie Valiant, Circuits of the Mind

Noson S. Yanofsky, The Outer Limits of Reason: What Science, Mathematics, and Logic Cannot Tell Us

Hector Zenil, Randomness Through Computation: Some Answers, More Questions

Fiction

Apostolos Doxiadis and Christos Papadimitriou, Logicomix: An epic search for truth

Christos H. Papadimitriou, Turing (A Novel about Computation)

Other Resources:

CS Unplugged (including a book)

 

Do It Yourself Theoryfestival Design – Guest Post By Sanjeev Arora

~ Omer Reingold ~ 8 Comments

Sanjeev suggesting an interesting exercise, in our series on the design of a Theory Festival as part of STOC 2017:

—————

Throughout our conference design process  we often observe big shifts in people’s opinions as they engage with the issues and the mathematical constraints. So if you have strong opinions about the theory festival, I highly recommend spending half an hour trying to come up with your own design.

Before and during your design, answer the following questions to yourself about the event you are planning:

  • How is the event appealing to theorists who currently don’t come?
  • How is the event creating more interaction opportunities?
  • Part of the target audience wants more signal from the PC (= more power), and part of the target audience wants to give less power to the PC because they disagree with its past decisions and general preferences. Which direction does your plan go in?

Keep in mind also the general equilibrium view:

(i) People worry about the effect of any change in the conferences on hiring/promotion/grant applications. The general equilibrium view says that if you double or halve the total number of STOC papers (“the money supply”) its only effect will be to double/halve the number of publications required to get the job or the grant. So what should determine the total number of accepts in your design?
(ii) The net attention of attendees is unchanged.  X-minute talks in 4 parallel sessions use up the same amount as X/2-minute talks in 2 parallel sessions. Which do you prefer —as author and as attendee—and why?

Of course you could argue that you can change the equilibrium by causing more jobs/grants to be created, or by increasing the number of attendees. In that case, please state your assumptions.

Have a go at it, and if you come up with interesting designs, please sketch them in your comments!

———————————————————————————

Data:

Currently: 90 accepts; 20 min talks in 2 parallel sessions (about 16-17 hrs)
Essentially no plenary. 1 separate day of workshops.

Our designs assume at least 12 plenary hrs, 2 hrs of tutorial, 1 day of workshops (all distributed over 5 days).  Plus, two hours for lunch and an evening poster session.

Remember to allow for  changeover time between speakers.

More fun at the theory festival: plenary sessions – guest post by Sanjeev Arora

~ Omer Reingold

Towards the business meeting, another personal post in our series (this one by Sanjeev Arora):

————–

An important part of the plan for theory festival —which everybody involved agrees upon—is the need for a substantial plenary component. The festival organizing committee would select the plenary program based upon inputs from various sources.

Plenary sessions will include about 20-25 short talks from a broad spectrum of “Theory” subcommunities, including (but not limited to) SODA, CCC, COLT, CRYPTO, KDD, EC, PODS, PODC, etc., as well as STOC and FOCS. We envisage some kind of nomination process whereby these communities/PCs could propose recent papers presented at their recent conferences which would be of interest to a broader theory audience. Sometimes they could nominate an older paper that is now generating a lot of work, or a survey talk.

Plenary sessions would also include 1-hr lectures introducing an area in science, social science, or mathematics of interest to a broad theory audience. I could’ve generate some sample topics myself, but in interest of fun I decided to ask for suggestions from a small group of people. (I’ve reworded/shortened their answers.)

Silvio Micali: Connectomics (figuring out the graph of interconnections of the brain’s neurons from imaging data).

Scott Aaronson: (a) Recent work connecting complexity, quantum information and quantum gravity (Harlow, Hayden, Preskill etc.); it is creating waves (b) Theorist-friendly introduction to deep nets and deep learning.

Ankur Moitra: Linear Inverse Problems: recovering an object from linear measurements (includes robust PCA, matrix completion, phase retrieval, tensor completion, etc. May have interesting connections to SDPs and other convex methods studied in our community.

Suresh Venkatsubramanian: (a) Computational Topology. Motivated by data analysis, it has completely taken over what used to be called computational geometry. STOC/FOCS people might be able to provide approximation algorithms for topological quantities. (b) Optimization: a basic primitive in many applied settings, especially machine learning. Esoteric optimization ideas like momentum and regularizers are now ubiquitous in applications, but haven’t affected STOC/FOCS world much (except for recent work on flows).

In your comments, please send other suggestions for talks that might be interesting.

Remember, the festival will also have a separate slot for technical tutorials on interesting topics within CS and theoretical CS. Also, some workshops may feature their own invited/plenary talks.

Can We Get Serious?

~ Omer Reingold ~ 19 Comments

This post represents my personal opinion (and only my opinion) with respect to turning STOC 2017 into a “Theory Festival.”

FOCS and STOC is where the entire theory community is supposed to come together for the benefit of the fruitful exchange of ideas between sub-areas of theory (which as Boaz mentioned, has been one of the sources of the community’s success). But this beautiful vision is threatened by two growing trends to worry about:

  1. More and more researchers in specific sub-communities abandon FOCS and STOC for the benefit of specialized venues that provide more effective exposure to their work.
  2. Even the FOCS-STOC experience gets fragmented as people tend to attend talks in areas closer to their own research (it is hard to know what to attend out of so many talks outside of one’s area).

The second issue could be addressed with a strong plenary program that would focus the attention of the entire community. This does not seem to be controversial and so I believe that STOC 2017 will have such a program, which is great. The second issue is much more problematic. We can no longer expect all of the strongest work in theory to be submitted to FOCS/STOC and I would think that having strong specialized venues should be encouraged. It is therefore difficult to expect researchers from area X that was “lost to FOCS/STOC” to attend the event just for the FOCS/STOC papers. In my mind, the only way to get them back is to offer a strong program in area X in addition to the plenary program that would allow them to stay connected with other areas of theory. This will require some effort and does not come for free as it will reduce the centrality of FOCS/STOC talks within the more general event. So this is the place to ask: are we really serious about a pan-theory event or are we content with keeping FOCS/STOC a place where a fraction of the theory community meets? Are we serious enough to give up a little bit of our entitled attention?

Currently, a large group of good intentioned individuals, led by the SIGACT executive committee, is considering designs for STOC 2017. This group is trying to be as attentive as possible to the voices coming out of the entire community. The problem is that in such a committee work it is very tempting to go for a conservative small change that will not upset anyone (but may gain too little). As the set of reasonable constraints and goals is impossible to completely satisfy, it is tempting to concentrate on not losing anything STOC already is rather than on gaining something new for the sake of what STOC can become. Being a romantic, I wish there was a hope to be just a little bit bolder!

To be less vague, let me conclude with the design of a pan-theory event that I would have chosen. This would be an event that would be more attractive for me to attend and much more attractive for researcher from the areas of theory that are underserved by STOC:

A STOC PC will select its program as usual (but with full flexibility regarding the number of accepted papers). An organizing committee will design the program of the theory festival. This committee will have representatives from the STOC PC but also from many other subareas of theory. The program will have three parts:

  1. A plenary session designed by the organizing committee and aimed to present only what the entire community should hear about.
  2. An afternoon session in many parallel tracks containing a collection of 3-5 days workshops (featuring STOC papers as well as other papers). These workshops will be curated by the organizing committee. For natural areas (various Algorithms areas, Complexity, ML, Econ, Cryptography, Quantum Computing, etc) representatives of the organizing committee will be setting up a workshop program (as they would do for an Oberwolfach/Simons/Banf … workshop). The committee can also accept other workshop proposals.
  3. An evening session that will include poster sessions (having guaranteed spots for all STOC papers).

The main challenge I see is to allocate a venue with many rooms for the parallel sessions. STOC papers will get a little bit less “formal attention” but will probably get on average more “substantial attention.” In particular, papers that deserve the attention of the entire community will be presented in the plenary session, while other papers will get the attention of their respective subcommunity (as they currently do). In addition, the poster session will give a more relaxed and interactive forum for cross-area interactions.