- be there for the junior researchers, and be generous with your funding/opportunities. Again, You (we? I feel old) have more stability, more of a cushion. Go out of your way to ease the path of the next generation and shield them. 4/ (end of personal, biased advice for senior TCS researchers)

The WAVE (Women in Algorithms, Venture into Exploration) 2026 workshop will take place on Friday, 11 September 2026, at the University of Copenhagen, Denmark. Website: wave-workshop.github.io Registration free but mandatory. Register now!! Please spread the word. Write to us if you have queries.

Thore Husfeldt and I wrote a guest post on @lance.fortnow.com and Bill Gasarch’s blog trying to explain the recent result that bipartite perfect matching allows *deterministic* efficient parallel algorithms (“BPM belong to NC”). blog.computationalcomplexity.org/2026/07/bipa...

Bipartite Perfect Matching in Deterministic NC

Nutan Limaye and Thore Husfeldt guest post on the new deterministic parallel algorithm for bipartite perfect matching by Abhranil Chatterje...

blog.computationalcomplexity.org

Heading to ICALP 2026. From Copenhagen to London by bus!!! 🚌

Here is yet another episode of Life of a researcher. open.spotify.com/episode/4M3T... This episode is really special. The picture says it all, I suppose. But read the comments to know more! Pro tip for listening: we are much more fun and snappy at 1.5x or 2x speed. So speed up the audio!!

Now it's official!! I already finished reading the introduction. Working out the proof is what I'm looking forward to next! Highest on my to-do. eccc.weizmann.ac.il/report/2026/... Paper number 100. Love it!! :D

Nutan Limaye@nutanlimaye.bsky.social · 2mo ago

Since today Bipartite Perfect Matching is in NC. The proof uses connections between coding theory and Hall's theorem. Presented at WACT 2026. Yay!!!

The preprint is out! Bipartite Perfect Matching is in NC, by Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, Thomas Thierauf eccc.weizmann.ac.il/report/2026/... #MathSky

Nutan Limaye@nutanlimaye.bsky.social · 2mo ago

Since today Bipartite Perfect Matching is in NC. The proof uses connections between coding theory and Hall's theorem. Presented at WACT 2026. Yay!!!

If you know it you know it. www.kva.se/en/event/cel...

We are ending with a lovely talk by Tuukka Korhonen who is telling us about lower bounds on tropical circuits, circuits that work over the (max, +) semiring.

Pietro Posta is telling us how to count interesting representation theoretical quantities using quantum algorithms. Specifically, he provides #BQP algorithms for counting these quantities.

The first talk in the final session of the final day of the workshop Julian Dörfler is telling us about local combinatorial interpretations. This is like a close cousin of what Igor Pak told us about the first day.

Pravesh Kothari is taking us on a tour through the two worlds of algorithms for tensor decomposition.

In the talk just before the lunch break Théo Fabris is telling us about strong separation between monotone and non-monotone circuits. There is a polynomial that has cubic size depth-3 circuit but requires exp(n) size monotone circuit.

Next, Magnus Hansen talked about the non-closure of roABPs under factoring. This is in contrast to previous results presented in the session.

Shanthanu Rai talked about the complexity of a fundamental problem, namely GCD. This is a problem I can explain to my nephew who is in 5th grade. It is fascinating that we have a new upper bound for it since 2024 and it has been made field independent in the work he presented. The talk was online.

The day started with a talk by Mrinal Kumar who presented one of my favorite recent results. The result is about the complexity of the factors of easy polynomials. It states that the factors are as easy as the polynomial. It subsumes all previous results of this kind.

Rohit Gurjar describes the result about Bipartite Perfect Matching is in NC to Avi Wigderson.

Prahladh Harsha is telling us about how to obtain near linear time algorithms for the list deciding problem. The main bottleneck is to design a near linear time algorithm for the interpolation step that shows up in previous polynomial time algorithms.

Roshan Raj presented a randomized polynomial time algorithm for a natural problem called Black-box Principal Minor Assignment. A definition called rank one extensions seem very interesting. I wonder whether it has any geometric interpretation.

Computing the order of an element is an important step in integer factorization. Ben Lee Volk have an improvement to this algorithmic question.

In the afternoon session we started with a talk by Josh Alman who is telling us about Faster Walsh-Hadamard Transform from Matrix Non-Rigidity.

Since today Bipartite Perfect Matching is in NC. The proof uses connections between coding theory and Hall's theorem. Presented at WACT 2026. Yay!!!

The talk before lunch is by Anakin Dey. He is telling us about how to deborder a result of Andrews and Forbes about IPS lower bounds. The main ingredient, surprisingly, is the isolation lemma.

The next talk in the session is by Prerona Chatterjee who is telling us about a variant of the IPS that is motivated by a previous result of Li, Tzameret, and Wang regarding the non-commutative IPS.

First talk in the session after the coffee break was by Tuomas Hakoniemi who presented our recent result (with Iddo Tzameret) on IPS proof systems which gives a CNF hard instance.

The first session today (Jun 4) is about proof complexity. The first talk is by Susanna de Rezende and Kilian Risse about Algebraic Proof Systems. Susanna introduced NZ and PC proof systems and Kilian is telling us about some recent results about PC.

An auditorium full of complexity theorists!

The talk before the poster session was by Tim Seppelt. He told us about the exciting new work on separation results for symmetric algebraic complexity classes.

The afternoon session on day 2 started with an introduction to symmetric circuits and lower bound techniques for these by Anuj Dawar. The symmetric model is one of the rare models that distinguishes the non-identical twins Det and Perm.

The two talks before lunch continue the derandomization-PIT-reconstruction theme. Zeyu Guo talked about how techniques from function fields and PIT can be used for constructing explicit lossless rank extractors. Whereas Devansh is talking about their recent work on depth-3 reconstruction problem.