Category Archives: Announcement

Announcing Monotonicity Festival at IIT Bombay

IIT Bombay is organizing an online Monotonicity Festival which is dedicated to understanding the impressive progress over the last couple of decades in Testing Boolean Monotonicity over various partially ordered domains (most notably, the Boolean Hypercube and the Hypergrid). Five of the lectures in this ongoing festival (with six planned lectures in total) have already taken place. Tomorrow is the last lecture where (PTReview’s own) Seshadhri will shed some light on the Directed Talagrand Inequality central to the analysis of the Monotonicity tester presented in the seminal work of Khot-Minzer-Safra.

The talk will begin at 10:30 AM India time tomorrow (April 30, 2024). Here is the zoom link: https://us06web.zoom.us/j/85365027303?pwd=hreOInC1dMwdFYnTOVa0nblSs9kDz6.1

Also, here is the link for all the YouTube playlist where we will upload all the talks: https://www.youtube.com/playlist?list=PLuoJqx7PPeVKzhTgFbMQH1zvF40yClpES

Thanks to Hadley Black, Deeparnab Chakrabarty and C. Seshadhri for kindly agreeing to give the talk.

WoLA’24: Dates, Registration, and call for contributed talks and posters

The 8th edition of WoLA, the Workshop on Local Algorithms, will be taking place on August 5-7, 2024 at the Simons Institute, as part of the Simons Institute’ summer program on Sublinear Algorithms.

Now, what is WoLA, some of you may ask?
“Local algorithms, that is, algorithms that compute and make decisions on parts of the output considering only a portion of the input, have been studied in a number of areas in theoretical computer science and mathematics. Some of these areas include sublinear-time algorithms, distributed algorithms, inference in large networks and graphical models. These communities have similar goals but a variety of approaches, techniques, and methods. This workshop is aimed at fostering dialogue and cross-pollination of ideas between the various communities.”

Save the date — the workshop has consistently been a great event for the local algorithms community to meet and discuss, and everyone is welcome to attend! (Registration is free)

The schedule is still being finalized, but here are some salient points:

  • on the first day, a celebration of Dana Ron‘s work and far-reaching influence, at the occasion of her 60th birthday
  • an open problem session for people to propose and discuss open questions and directions in local algorithms
  • Senior-junior lunches, and lightning talks (“graduating bits”) for graduating or soon-to-be-graduating students and postdocs
  • contributed short talks and a poster session

Importantly, there will also be another event (independent of WoLA, but very much related) on August 8 at the Simons Institute: a one-day birthday celebration for Ronitt Rubinfeld, “RR@60”, organized by Arnab Bhattacharyya, Funda Ergun, Krzysztof Onak, and Ravi Kumar. So plan on attending both!

To register your interest in attending WoLA (optional: for planning purposes), please fill the Simons Institute form on the right side here (or, alternatively, the form below). If you’d like to present your work, as a short contributed talk and/or a poster, or would like to take part in the “graduating bits” session, please express your interest by filling this form by ⏰ May 3, 5pm ET. Notifications will be sent by May 15.

If you have any questions about WoLA, or need an invitation letter to attend (for visa reasons), please indicate it in the form.

Update (25/04): updated the post to include the link to the Simons Institute registration form.

Clément Canonne, on behalf of the WoLA PC (Talya Eden, Manuela Fischer, Michael Kapralov, Robi Krauthgamer, Reut Levi, Rotem Oshman, Michal Parnas, Ron Rothblum, and Jara Uitto)

Sublinear Algorithms Program at the Simons Institute in 2024

Exciting news!* Next year, the Simons Institute will host a summer program on Sublinear Algorithms. from May 20 to August 9, 2024. Organised by Artur Czumaj, Piotr Indyk, Jelani Nelson, Noga Ron-Zewi, Ronitt Rubinfeld, Asaf Shapira and myself, the summer program will feature 4 workshops:

This is, of course, in addition to the bulk of the program itself: research discussions, reading groups, talks, social activities… If you happen to be in the area, you’re more than welcome to come and take part in some of these!

While each workshop will have its own set of attendees (more details soon), there are also some slots for (1) long-term visitors and (2) Simons Research Fellows (within five years of the award of their PhD at the start of academic year 2024-25, may already hold faculty positions) you can apply to! The deadline to apply is December 1, 2023:

Hope to see many of you next summer! Oh, and to conclude… have you seen our logo?

Sublinear Algorithms Wide Format Logo

* Full disclosure: I am biased, being an organizer, but do find that very exciting.

A Pedagogical reference to kick off the New Year

Dear Readers,

Our own Clément Canonne has written a beautiful survey which is now available in FnT book format from now publishers. This appears to be a very promising read — especially for the Distribution Testers among you. Today’s post is a mere advertisement for this beautiful survey/book which is clearly the result of a dedicated pursuit.

Let me now dig into this survey a teeny tiny bit. One among the many cool features of this survey is that it uses one central example (testing goodness-of-fit) to give a unified treatment to the diverse tools and techniques used in distribution testing. Another plus for me is the historical notes section that accompanies every chapter. In particular, I really liked jumping into the informative history section at the end of Chapter 2 which has an almost story like feel to it. If the above points do not catch your fancy, then please try opening the survey. You will be hardpressed to find a book that is typeset in such an aesthetically pleasing way with colored fonts to emphasize various parameters in several intricate proofs. Happy Reading!

New Property Testing book, by Arnab Bhattacharyya and Yuichi Yoshida

More great news: a new textbook on property testing, 📘 Property Testing: Problems and Techniques, by two experts in the field, Arnab Bhattacharyya and Yuichi Yoshida, is now available!

Property Testing: Problems and Techniques (Springer, 2022)

As the overview below outlines (from the book’s website), the book covers a wide range of topics, and should give anyone interested a great overview of scope, techniques, and results in testing.

This book introduces important results and techniques in property testing, where the goal is to design algorithms that decide whether their input satisfies a predetermined property in sublinear time, or even in constant time – that is, time is independent of the input size.

This book consists of three parts. The first part provides an introduction to the foundations of property testing. The second part studies the testing of specific properties on strings, graphs, functions, and constraint satisfaction problems. Vectors and matrices over real numbers are also covered. The third part is more advanced and explains general conditions, including full characterizations, under which properties are constant-query testable.

The first and second parts of the book are intended for first-year graduate students in computer science. They should also be accessible to undergraduate students with the adequate background. The third part can be used by researchers or ambitious graduate students who want to gain a deeper theoretical understanding of property testing.

2022: Voilà, WOLA!

Good news, everyone! WOLA, the Workshop on Local Algorithms, is coming back this year, with WOLA 2022 taking place in person* in Warsaw on June 25–27. Exciting speakers, events and outings are being planned!

Keep track of updates by visiting the website, and register at https://ideas-ncbr.pl/en/wola/registration/ (even if you intend to attend remotely).

* Virtual participation is also possible.

Workshop on Algorithms for Large Data: We found WALD(O), and so can you!

Ainesh Bakshi, Rajesh Jayaram, and Samson Zhou are organizing a 3-day Workshop on Algorithms for Large Data (nicely abbreviated as WALD(O), the O standing for Online), featuring many talks which should be of interest to the readers of this blog, as well as an open problems and a poster sessions, and a junior/senior lunch. As the organizers describe it:

This workshop aims to foster collaborations between researchers across multiple disciplines through a set of central questions and techniques for algorithm design for large data. We will focus on topics such as sublinear algorithms, randomized numerical linear algebra, streaming and sketching, and learning and testing.

The workshop will take place on August 23 — August 25 (ET). Attendance is free, but registration is required by August 20th. More details at https://waldo2021.github.io/

Announcing WOLA’21 (Workshop on Local Algorithms)

The fifth WOLA (Workshop on Local Algorithms) will be virtual, and take place June 14-15. Registration is free, but required: please fill this form by June 10th to attend.

Local algorithms — that is, algorithms that compute and make decisions on parts of the output considering only a portion of the input — have been studied in a number of areas in theoretical computer science and mathematics. Some of the related areas include sublinear-time algorithms, distributed algorithms, streaming algorithms, (massively) parallel algorithms, inference in large networks, and graphical models. These communities have similar goals but a variety of approaches, techniques, and methods. This workshop is aimed at fostering dialogue and cross-pollination of ideas between the various communities.

This year, the workshop will include:

  • A poster session: Please submit your poster proposal (title and abstract) at by May 26th. Everyone is invited to contribute. This session will take place on gather.town.
  • Invited long talks: the tentative schedule is available, and features talks by James Aspnes, Jelani Nelson, Elaine Shi, Christian Sohler, Uri Stemmer, and Mary Wootters.
  • Junior-Senior social meetings
  • An AMA (Ask Me Anything) session, moderated by Merav Parter
  • A Slack channel
  • An Open Problems session

The Program Committee of WOLA 2021 is comprised of:

  • Venkatesan Guruswami (CMU)
  • Elchanan Mossel (MIT)
  • Merav Parter (Weizmann Institute of Science)
  • Sofya Raskhodnikova (chair) (Boston University)
  • Gregory Valiant (Stanford)

and the organizing committee:

  • Sebastian Brandt (ETH)
  • Yannic Maus (Technion)
  • Slobodan Mitrović (MIT)

For more detail, see the website; to stay up to date with the latest announcements concerning WOLA, join our mailing list!

Policy on reporting papers

While we at PTReview always look through the posted papers, we do not check for correctness. We make a serious attempt to make sure the paper is reasonable. In a few instances, we have decided not to post a (topically relevant) paper, because it looks absolutely wrong. Our position is: the benefit of doubt goes to the author, and a borderline paper should be posted. We are only curating relevant tech reports, not passing judgment on results.

In some borderline cases, readers familiar with the subject complained to us that the paper should be not be considered a scientific contribution (because of, say, unspecified algorithms, blatantly incorrect or unverifiable central claims). These are cases where we were also unsure of the paper. We have usually removed/not posted such papers.

If the paper author(s) feels that his/her paper should nonetheless be posted, then they should email us at little.oh.of.n@gmail.com. As long as the paper is not complete nonsense and appears to cite relevant history, we will defer to the authors’ wishes.

FOCS 2017: Workshop on Distribution Testing

As it may have transpired by now, FOCS 2017 (a.k.a. the 58th Annual Symposium on Foundations of Computer Science) is around the corner.

I am not going to go into the details of the talks on or related to property testing at the conference itself,\({}^{(\ast)}\) but instead focus on (one of) the workshops.

This FOCS will include 3 workshops,\({}^{(\dagger)}\) on Saturday 14th (gird your loins — they last the full day!):

  • Linear Sketching as a Tool for Everything
  • Frontiers in Distribution Testing
  • Hardness Escalation in Communication Complexity and Query Complexity

The second,  Frontiers in Distribution Testing, is specifically about recent advances, new questions, and novel directions in property testing of distributions. Co-organized by Gautam Kamath and me, its official objective is to “catch the community up in recent developments, and highlight some of the most interesting frontiers in distribution testing.”

It’ll feature a stellar lineup of speakers\({}^{(\ddagger)}\) (namely, Ilias Diakonikolas, Jiantao Jiao, Alon Orlitsky, Constantinos Daskalakis, Ryan O’Donnell, Ronitt Rubinfeld, and Tom Gur), as well as an open problem session — and, very possibly, pictures of eggs. The program is available, with all relevant details, on the workshop webpage.

If you are around next Saturday, consider attending — and submit your favorite open problems!

\({}^{(\ast)}\) Hint: look at Sessions 7A and 10B.
\({}^{(\dagger)}\) Thanks to the FOCS workshop chairs James Lee and Aleksander Mądry.
\({}^{(\ddagger)}\) A lineup of stellar speakers.