This sounds pretty cool: bipartite perfect matching is solvable in polylog time in parallel with poly many processors. This was known if you allow randomness but has been a longstanding open problem deterministically.

I have been watching some show set in a university and their version of tenure is wild! One character was hired as a full prof but without tenure (!), and then asked to be placed on the tenure track. The tenure track was sped up just for her from 5 years to 1 year.

Online Matrix Factorization, Online Private Query Release, and Online Discrepancy Minimization Aleksandar Nikolov, Haohua Tang, Jonathan Ullman http://arxiv.org/abs/2605.08358

Interesting how many people are losing their shit over an innocuous sounding use of AI to make custom feeds.

Changing to daylight savings time feels like I’m going through mini jet lag.

A great read about @henryyuen.bsky.social's research. Also great pictures of him looking thoughtfully into the distance.

I didn't think anyone needed to hear this, but if you are applying for a PhD program, and used an LLM to help write your SoP, check if the papers you cite by the person you say you want to work with actually exist! I remember the titles of my own papers.

To recap: Doug Ford destroyed parkland at Ontario Place for a private waterpark; closed Ontario Science Centre under false pretenses; and now is moving the OSC into Harbourfront. Partial destruction of one public place; permanent destruction of another; longterm takeover of a third.

Happy #STOC2026 deadline to all who celebrate!

Me to my undergrad students: “Don’t submit 30 secs before the deadline. If you do, don’t complain you missed it.” Also me: pushing submit on a paper at 4:59pm, for a 5pm deadline.

I admit I didn't pay much attention to baseball till this year, although I have been to games. This was wild, and heartbreaking for Toronto. The World Series is not always this dramatic, is it? 18 inning games, wedged balls, being short of a win by a few inches in the last inning..

The Toronto Blue Jays are going to the World Series

Congratulation to Canada’s Toronto Blue Jays!! 🇨🇦🇨🇦🇨🇦🇨🇦

The great thing about parenting a toddler is that the rest of your day is easy after whatever you've been through by 9 am

Exciting news from SRI! We’re welcoming Michael Inzlicht & Avery Slater as new research leads for 2025–26! Alongside six continuing leaders, they’ll advance bold projects on AI safety, trust, fairness, creativity & more. Learn more: srinstitute.utoronto.ca/news/eight-n... #AI #UofT

This is a good feed to have in the mixer. It shows all papers being shared by your follows

The owner of a giant dog that they had unleashed in a children’s playground just did the “but he’s friendly” to my wife and 4yo this morning. The “Please leash your dog at all times” signs are everywhere. This ad is not mean enough IMO.

To test a “quantum computing is impossible” argument, substitute “random bit” for “qubit”, and coins for cats, and see if it sounds silly. E.g.: “N random coins are simultaneously heads/tails and do 2^N work for you to test if a number is prime? Extremely dubious” See, it’s silly!

Great cringe comedy over at the other site.

Imagine you are in charge of a playground of 3 year olds, but they are each three meters tall and are throwing rocks at you. It wouldn’t be very hard for them to get around you.

Here is an uplifting song in memory of the greatest that ever got chalk on his coat www.youtube.com/watch?v=frAE...

Blasting Black Sabbath and remembering seeing them in Sofia in 2005.

Spent the week at an AIM workshop on metric embedding in Caltech, and got to meet many of my mathematical heroes. Also had this view as inspiration.

It’s been 10 years (and 3 days) since I moved to Canada. Lots of things changed in my life in these 10 years, but meeting @theannasu.bsky.social and becoming a dad are the definite highlights!

New profile photo taken by my 4yr old, I think he did a good job!

Was reading a paper on my iPad while eating my lunch and the waitress asked if I was doing my homework. Been a while since I passed for a student!

It's a depressing time in Toronto - a city that once had the continent's most ambitious city-building initiative. This transformation had 3 KEY PILLARS: 1. RapidTO 2. GO Expansion 3. Ontario Line Two pillars have been watered down beyond recognition - DEVASTATING for the region. Here's why: 1/🧵

Spread the word: there is a new prize in Theoretical Computer Science in honor of Luca Trevisan-- cs.unibocconi.eu/call-nominat... (Intent-to-nominate letters due by July 31.)

It's time for the Theory Jobs spreadsheet for 2025! The theory CS community crowdsources who accepted which jobs every year. Links in next post 1/2

The King St streetcar situation right now is a disaster, and it will be a disaster for the whole summer. I am experiencing real whiplash after riding the Tokyo public transit last week.

Our Japan vacation with a preschooler has just been a train ride after train ride and he’s loving it!

Христос Воскресе! Growing up in Bulgaria, Easter meant eating lots of boiled eggs and козунак (sweet eggy Easter bread). Sticking to that in Canada too.

Me completing my annual review

First time voting in Canada. To support bilingualism I posed in front of the French side of the sign.

I’m trying the “scientific recipe” in this paper next week. Will report back with the results. All for science obviously

I think this "subscriptionification" of goods and services is the biggest danger tbh. It's already a thing with some goods like printers and I expect will only be more so in time. This in conjunction with planned obsolescence of software support makes me very pessimistic.

This is great, highly recommend going through the slides!

Hey, Berkeley, these numbers don't make sense.

Big if true

happy architectural turkey day part II: robarts library at u. toronto, mathers & haldenby, 1973. 🦃🦃🦃

Recorded an extended version of my MFCS'24 invited talk. The talk presents my personal experiences in entering learning theory with a TCS background. The target audience is mostly TCS researchers. Hope some of you might enjoy it. youtu.be/ZYe2mITwww4

On the TCS job market: Tamalika Mukherjee! Tamalika's research: (1) designing computationally efficient privacy-preserving algorithms for data analysis, (2) understanding their societal implications through the lens of equity and policy. Keywords: sublinear, DP 1/2 #TCSSky #AcademicJobMarket

Teaching NP completeness and gadget reductions reminds how one time I was reading a hardness of approximation paper when a friend came over. My friend saw the section title “The Dictatorship Gadget” and was very concerned

Check out this exciting new work by my colleague Subhash Khot, in work with Amey Bhangale, Yang Liu, and Dor MInzer giving improved bounds for the density Hales-Jewett problem, building off their work on approximability of satisfiable CSPs! eccc.weizmann.ac.il/report/2024/...

The world watches incredulously as our Premier puts people who bike’s lives at risk for no good reason except to start a culture war. www.theguardian.com/world/2024/n... #topoli #onpoli #bikeTO

If you are on the job market, and work on the kinds of topics that might be published in FORC ("Foundations of Responsible Computing"), fill out this form and get on the job list. This covers mathematical research on privacy, fairness, and related topics.

I was today years old when I got it

We asked Russell Impagliazzo to write up his memories of Steven Rudich for our blog. He came back with a very honest and personal seven-page remembrance. fortnow.com/weblog/m... Blog post: blog.computationalco...

Differential Privacy (DP) inherently requires 🎲 to ensure the sensitive data stays private, in a rigorous, mathematical sense. So DP algos are randomized, by defn. But how much is needed to ensure privacy? One random bit? One gazillion? We didn't know! Until now. (Paper below)