Sign In

Communications of the ACM

Blogroll



From Computational Complexity

2019 Fall Jobs Post

Starting PhD students over time would always assume that the computer science academic job market would be a strong or as weak when they graduate as it is whenCRA...

From Computational Complexity

Quantum Supremacy

By now you've probably heard the rumors of Google achieving quantum supremacy. I don't have inside information outside of Scott's blog post but it looks like the...

From Computational Complexity

Transitioning

You may have noticed, or not, that I haven't posted or tweeted much in the last month. I've had a busy time moving back to Chicago and starting my new positionsignificant...

From Computational Complexity

The Advisor/Advisee Relationship

I've always felt a strong advisor/advisee relationship is the single most important factor in a successful PhD career. At its best, the advisor works closely with...

From Computational Complexity

Degree and Sensitivity

Hao Huang's proof of the sensitivity conjecture that I posted on last week relied on a 1992 result of Gotsman and Linial. Let's talk about that result. Consider...

From Computational Complexity

Local Kid Makes History

The blogosphere is blowing up over Hao Huang's just posted proof of the sensitivity conjecture, what was one of the more frustrating open questions in complexity...

From Computational Complexity

FCRC 2019

Georgia Tech FCRC Participants I'm heading home from the 2019 ACM Federated Computing Research Conference in Phoenix, a collection of computer science meetings...

From Computational Complexity

The Urban/Rural Collegiality Divide

Just a reminder that Grigory Yaroslavtsev has taken over the Theory Jobs Spreadsheet. Check out who is moving where and let everyone know where you will continue...

From Computational Complexity

Compressing in Moscow

This week finds me in Moscow for a pair of workshops, the Russian Workshop on Complexity and Model Theory and a workshop on Randomness, Information and Complexity...

From Computational Complexity

What Happened to the Surprising Theorems?

Twenty-five years ago Peter Shor presented a polynomial-time factoring algorithms for quantum computers. For Peter, it was a simple translation of a quantum algorithm...

From Computational Complexity

NSF Panels

The government shut down in January led to delays at the National Science Foundation and only recently announcing decisions on grants submitted last fall. For those...

From Computational Complexity

Logic Then and Now

This week I attended the Association of Symbolic Logic North American Annual Meeting in New York City, giving a talk on P v NP. First I must share the announcement...

From Computational Complexity

Getting Through the Clutter

My daughter showed up at her doctor's office the other day and found it closed. She complained that she had received all these alerts, texts, emails, voicemails...

From Computational Complexity

Multiple Provers

Just over thirty years ago on May 5, 1989, I defended my PhD Thesis Complexity-Theoretic Aspects of Interactive Proof Systems. It's starts off with a parable for...

From Computational Complexity

The Next Chapter

I've accepted a position as Dean of the College of Science at the Illinois Institute of Technology in Chicago starting in August. It's an exciting opportunity...

From Computational Complexity

Geo-Centric Complexity

An interesting discussion during Dagstuhl last month about the US-centric view of theory. Bad enough that all talks and papers in an international venue are inManhattan...

From Computational Complexity

Physics of Everday Life

Based on Scott's review, I read through Stephen Pinker's Enlightenment Now. I can't top Scott's exposition of the book, but it is pretty incredible how far humanity...

From Computational Complexity

Cuckoo Cycles

Guest Blog by John Tromp (Thanks for the opportunity, Lance) In the past few months, cycle finding has become one of the most widely run graph theory problems....

From Computational Complexity

Scooped

At Dagstuhl I got a few ideas for future posts but then... We had some discussions about STOC allowing program committee members to submit papers that I planned...

From Computational Complexity

Back at Dagstuhl

Participants and Their Research Interests This week I'm in Germany for the Dagstuhl workshop on Computational Complexity of Discrete Problems well timedtypecast...
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account