A cute not too hard problem: If k <= n/2 give a fully combinatorial proof that (n choose k) >= 2^k.
There's more than one way to do this.
There's more than one way to do this.
February 16, 2026 at 9:20 PM
A cute not too hard problem: If k <= n/2 give a fully combinatorial proof that (n choose k) >= 2^k.
There's more than one way to do this.
There's more than one way to do this.
Bill asks open problems as extra credit on class.
blog.computationalco...
Why not go all the way? Just hide an open problem in the regular problems and see what happens.
blog.computationalco...
Why not go all the way? Just hide an open problem in the regular problems and see what happens.
Assigning Open Problems in Class
I sometimes assign open problems as extra credit problems. Some thoughts: 1) Do you tell the students the problems are open? YES- it would b...
blog.computationalcomplexity.org
February 16, 2026 at 2:07 PM
Bill asks open problems as extra credit on class.
blog.computationalco...
Why not go all the way? Just hide an open problem in the regular problems and see what happens.
blog.computationalco...
Why not go all the way? Just hide an open problem in the regular problems and see what happens.
Joe Halpern passed away Friday at the age of 72. He was a leader in mathematically reasoning about knowledge.
www.linkedin.com/pos...
www.linkedin.com/pos...
February 16, 2026 at 7:34 AM
Joe Halpern passed away Friday at the age of 72. He was a leader in mathematically reasoning about knowledge.
www.linkedin.com/pos...
www.linkedin.com/pos...
Reposted by Lance Fortnow
The list of accepted papers at #STOC2026 is out:
acm-stoc.org/stoc2026/acc...
Congratulations to all authors!
acm-stoc.org/stoc2026/acc...
Congratulations to all authors!
STOC 2026 - 58th ACM Symposium on Theory of Computing
acm-stoc.org
February 13, 2026 at 1:27 AM
The list of accepted papers at #STOC2026 is out:
acm-stoc.org/stoc2026/acc...
Congratulations to all authors!
acm-stoc.org/stoc2026/acc...
Congratulations to all authors!
A young aspiring mathematicians asks about the future of math with all the AI advances. My advice: Embrace research but be ready to pivot as needed. We many be seeing a new age in mathematics, how could you not be part of it.
The Future of Mathematics and Mathematicians
A reader worried about the future. I am writing this email as a young aspiring researcher/scientist. We live in a period of uncertainty and ...
blog.computationalcomplexity.org
February 12, 2026 at 4:26 PM
A young aspiring mathematicians asks about the future of math with all the AI advances. My advice: Embrace research but be ready to pivot as needed. We many be seeing a new age in mathematics, how could you not be part of it.
Bill on the future historians access to our times. I'm more interested in how they will judge us, assuming there is a future with historians.
I used to think historians in the future will have too much to work with. I could be wrong
(I thought I had already posted this but the blogger system we use says I didn't. Apologies if I did. Most likely is that I posted somethin...
blog.computationalcomplexity.org
February 9, 2026 at 3:03 PM
Bill on the future historians access to our times. I'm more interested in how they will judge us, assuming there is a future with historians.
The new SIGACT Luca Trevisan Award for Expository Work promotes and recognizes high-impact work expositing ideas and results from the theory of computation. Nomination deadline is April 10th.
sigact.org/prizes/tr...
sigact.org/prizes/tr...
February 5, 2026 at 1:54 PM
The new SIGACT Luca Trevisan Award for Expository Work promotes and recognizes high-impact work expositing ideas and results from the theory of computation. Nomination deadline is April 10th.
sigact.org/prizes/tr...
sigact.org/prizes/tr...
Google put out an article on accelerating research with Gemini. I'm one of the 34 authors for my adventures in vibe-coding a research paper.
Accelerating Scientific Research with Gemini: Case Studies and...
Recent advances in large language models (LLMs) have opened new avenues for accelerating scientific research. While models are increasingly capable of assisting with routine tasks, their ability...
arxiv.org
February 4, 2026 at 8:47 PM
Google put out an article on accelerating research with Gemini. I'm one of the 34 authors for my adventures in vibe-coding a research paper.
One of the humanities fellows at Oxford called a "computer science library" an oxymoron. Yet, the university has one and a visit helped bring new life to an old paper.
Blogger
Weblog publishing tool from Google, for sharing text, photos and video.
draft.blogger.com
February 4, 2026 at 3:18 PM
One of the humanities fellows at Oxford called a "computer science library" an oxymoron. Yet, the university has one and a visit helped bring new life to an old paper.
Thomas Watson has a new computational complexity textbook about to be published by Cambridge University Press. There's a free version online for personal use.
complexityincs.com
complexityincs.com
February 3, 2026 at 4:09 PM
Thomas Watson has a new computational complexity textbook about to be published by Cambridge University Press. There's a free version online for personal use.
complexityincs.com
complexityincs.com
Bill talks about how technology leads to fears of less learning throughout history.
Before the ChatGPT-HW debate there were other ``If students use X to do their HW'' debates
Lance and I had a blog-debate about What to do about students using ChatGPT to do their Homework . Some commenters pointed out that we've b...
blog.computationalcomplexity.org
February 2, 2026 at 3:10 PM
Bill talks about how technology leads to fears of less learning throughout history.
Large-language models have gotten very good at academic literature search, but it often requires two prompts where the second prompt is "You made up those references. Try again."
January 30, 2026 at 10:10 PM
Large-language models have gotten very good at academic literature search, but it often requires two prompts where the second prompt is "You made up those references. Try again."
January 28, 2026 at 6:20 PM
I'm perfectly happy having AI models trained on all my research papers and everything else I've publicly written, and I hope others feel the same. Best to have the models know as much about computational complexity as possible if we want to best further the field.
January 26, 2026 at 7:17 PM
I'm perfectly happy having AI models trained on all my research papers and everything else I've publicly written, and I hope others feel the same. Best to have the models know as much about computational complexity as possible if we want to best further the field.
England weather has been as advertised, cold, dark and damp. I haven't seen dry ground since I got here two weeks ago.
Still we're 50 degrees warmer than Chicago today.
Still we're 50 degrees warmer than Chicago today.
January 23, 2026 at 5:25 PM
England weather has been as advertised, cold, dark and damp. I haven't seen dry ground since I got here two weeks ago.
Still we're 50 degrees warmer than Chicago today.
Still we're 50 degrees warmer than Chicago today.
The 2026 Michael and Sheila Held Prize goes to Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer and Muli Safra for their work on the 2-to-2 Games Theorem.
Michael and Sheila Held Prize – NAS
The Michael and Sheila Held Prize is presented annually to honor outstanding, innovative, creative, and influential research in the areas of combinatorial and discrete optimization, or related parts of computer science, such as the design and analysis of algorithms and complexity theory. This $100,000 prize is intended to recognize recent…
www.nasonline.org
January 23, 2026 at 3:00 PM
The 2026 Michael and Sheila Held Prize goes to Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer and Muli Safra for their work on the 2-to-2 Games Theorem.
Reposted by Lance Fortnow
Congrats to Irit Dveer Dinur of the Institute for Advanced Study & Weizmann Insitute, #NASmember Subhash Khot of New York University, Guy Kindler of @hebrewuniversity.bsky.social, Dor Minzer of @mit.edu, and Muli Safra of Tel Aviv University, winners of the 2026 Michael and Sheila Held Prize! (1/2)
January 22, 2026 at 3:56 PM
Congrats to Irit Dveer Dinur of the Institute for Advanced Study & Weizmann Insitute, #NASmember Subhash Khot of New York University, Guy Kindler of @hebrewuniversity.bsky.social, Dor Minzer of @mit.edu, and Muli Safra of Tel Aviv University, winners of the 2026 Michael and Sheila Held Prize! (1/2)
In academia we have two main communities, our department and our academic field. At Oxford, community seems to lie mainly in the colleges.
Community
I once had a provost who felt that academic departments hindered the university as they tended to silo the faculty. He would argue we should...
blog.computationalcomplexity.org
January 22, 2026 at 4:52 PM
In academia we have two main communities, our department and our academic field. At Oxford, community seems to lie mainly in the colleges.
New ACM Fellows include Swarat Chaudhuri, Javier Esparza, Paolo Ferragina, Ken-Ichi Kawarabayashi, Aggelos Kiayias, Alistair Moffat, Noam Nisan, Ariel Procaccia, Oded Regev, Natarajan Shankar, Stephanie Weirich, Adam Wierman and Ke Yi.
awards.acm.org/fello...
awards.acm.org/fello...
January 21, 2026 at 4:32 PM
New ACM Fellows include Swarat Chaudhuri, Javier Esparza, Paolo Ferragina, Ken-Ichi Kawarabayashi, Aggelos Kiayias, Alistair Moffat, Noam Nisan, Ariel Procaccia, Oded Regev, Natarajan Shankar, Stephanie Weirich, Adam Wierman and Ke Yi.
awards.acm.org/fello...
awards.acm.org/fello...
Bill asks how can we handle students using AI for homework and I give my thoughts.
Short Answer: Not much.
Short Answer: Not much.
What to do about students using ChatGPT to do their homework?
Students are using ChatGPT to do their HW. Here are things I've heard and some of my thoughts on the issue (Lance also added some comments)....
blog.computationalcomplexity.org
January 20, 2026 at 6:45 AM
Bill asks how can we handle students using AI for homework and I give my thoughts.
Short Answer: Not much.
Short Answer: Not much.
Reposted by Lance Fortnow
This is scientists’s version of tearing down parts of the White House.
The National Science Foundation sign on our Eisenhower Av building is now gone.
The NSF mural in the foyer is removed and torn off in sheets.
We were supposed to celebrate the 75th anniversary of the agency in May 2025. That never happened.
The NSF mural in the foyer is removed and torn off in sheets.
We were supposed to celebrate the 75th anniversary of the agency in May 2025. That never happened.
January 18, 2026 at 3:16 AM
This is scientists’s version of tearing down parts of the White House.
A three-decade-old open problem of mine just got solved! Matt Kovacs-Deak, Daochen Wang and Rain Zimin Yang showed that if a Boolean function f is exactly computed by a low-degree rational function, the quotient of two polynomials, then f has low decision-tree complexity.
1/2
1/2
January 14, 2026 at 3:06 PM
A three-decade-old open problem of mine just got solved! Matt Kovacs-Deak, Daochen Wang and Rain Zimin Yang showed that if a Boolean function f is exactly computed by a low-degree rational function, the quotient of two polynomials, then f has low decision-tree complexity.
1/2
1/2
RIP Scott Adams www.nytimes.com/2026...
Whatever you think of the man, his Dilbert creations captured the tech world. Just call me Dan.
1/2
Whatever you think of the man, his Dilbert creations captured the tech world. Just call me Dan.
1/2
January 13, 2026 at 4:46 PM
RIP Scott Adams www.nytimes.com/2026...
Whatever you think of the man, his Dilbert creations captured the tech world. Just call me Dan.
1/2
Whatever you think of the man, his Dilbert creations captured the tech world. Just call me Dan.
1/2
In the LLM era, I'm finding people are not very tolerent of typos and grammatical issues.
January 12, 2026 at 11:18 PM
In the LLM era, I'm finding people are not very tolerent of typos and grammatical issues.