Blogroll | Communications of the ACM

From Computational Complexity

Happy 90th Juris!

Juris Hartmanis turns 90 today. Hartmanis with Richard Stearns received the 1993 Turing Award for their seminar work On the Computational Complexity of Algorithms... Lance Fortnow
From Computational Complexity | July 5, 2018 at 09:15 AM

From Computational Complexity

STOC 50 Part II

On Wednesday, STOC had a great complexity session and the best complexity paper of the conference, Cody Murray and Ryan Williams extending Ryan’s celebrated result... Lance Fortnow
From Computational Complexity | June 28, 2018 at 06:31 PM

From Computational Complexity

STOC 50 Part I

This week I'm in Los Angeles attending the 50th Symposium on the Theory of Computing. Most attendees weren't even born before the first STOC. Many of them weren't... Lance Fortnow
From Computational Complexity | June 26, 2018 at 06:31 PM

From Computational Complexity

Hoteling

Thanks to Grigory Yaroslavtsev for taking over the Theory Jobs Spreadsheet. Details on Grigory's blog. Check out who is going where next year. My office... Lance Fortnow
From Computational Complexity | June 14, 2018 at 03:44 PM

From Computational Complexity

BQP not in the Polynomial-Time Hierarchy in Relativized Worlds

The quantum complexity world is a rocking with the paper released yesterday by Ran Raz and Avishay Tal, Oracle Separation of BQP and PH, resolving a question open... Lance Fortnow
From Computational Complexity | June 1, 2018 at 02:09 PM

From Computational Complexity

Seventh Grade Math Contest

I stumbled upon an old blog post on the Lesswrong weblog that quotes several famous mathematicians on the connections, or lack thereof, between mathematics competitions... Lance Fortnow
From Computational Complexity | May 31, 2018 at 11:09 AM

From Computational Complexity

Kolmogorov Complexity and Causation

I got an interesting email question. Suppose I give you a set of points S of the form (x,y). He suggested ideally they would be pairs of a real numbers. Supposing... Lance Fortnow
From Computational Complexity | May 24, 2018 at 11:15 AM

From Computational Complexity

The Complexity of the Firm

In 1937, a year after Turing had his seminal paper, Ronald Coase published a paper The Nature of the Firm to give a framework to why we have companies and how large... Lance Fortnow
From Computational Complexity | May 17, 2018 at 08:37 AM

From Computational Complexity

Richard Feynman (1918-1988)

When I took cryptography from Manuel Blum, he handed out copies of the chapter "Safecracker Meets Safecracker" from Richard Feynman's book Surely You're Joking... Lance Fortnow
From Computational Complexity | May 11, 2018 at 05:29 AM

From Computational Complexity

Broader Impacts Redefined

The ACM Future of Computing Academy suggests that "peer reviewers should require that papers and proposals rigorously consider all reasonable broader impacts, both... Lance Fortnow
From Computational Complexity | May 3, 2018 at 07:12 AM

From Computational Complexity

Memory is Hot

A good number of the faculty candidates interviewing at Georgia Tech have a common theme: Memory. Memory connected to databases, to programming languages, to... Lance Fortnow
From Computational Complexity | April 19, 2018 at 07:42 AM

From Computational Complexity

Lance and Bill Gather for Gardner

Every two years in Atlanta, recreational mathematicians gather to honor Martin Gardner, whose Scientific American column Mathematical Games through the 60's and... Lance Fortnow
From Computational Complexity | April 13, 2018 at 08:01 AM

From Computational Complexity

Almost Famous Quantum Polynomial Time

I have been playing with a new complexity class AFQP, defined in a yet-to-be-published manuscript by Alagna and Fleming. A language L is in AFQP if there is a polynomial... Lance Fortnow
From Computational Complexity | March 29, 2018 at 12:42 PM

From Computational Complexity

A Reduced Turing Award

A Turing machine has an extremely simple instruction set: Move left, move right, read and write. If you want to do real programming, you need something a bit... Lance Fortnow
From Computational Complexity | March 29, 2018 at 08:06 AM

From Computational Complexity

Stephen Hawking (1942-2018)

Stephen Hawking passed away earlier this morning in Cambridge, England. As a brilliant theoretical physicist and best-selling author all while dealing withA... Lance Fortnow
From Computational Complexity | March 14, 2018 at 09:08 AM

From Computational Complexity

Data-Driven Programming

Five years ago I posted about Flash Fill, a then new Microsoft Excel feature that would reformat data based on examples. I just checked the latest version of Excel... Lance Fortnow
From Computational Complexity | March 9, 2018 at 08:37 AM

From Computational Complexity

Me and My Bolt

On Tuesday I got a knock on my car's window. Rolling it down someone asked if I liked my car as he was thinking of buying one himself. Was I driving the... Lance Fortnow
From Computational Complexity | March 1, 2018 at 07:33 AM

From Computational Complexity

NP is Hard

You don't get much press by stating conventional beliefs--there is no "round earth society". Nevertheless there are serious researchers out there trying to sayI... Lance Fortnow
From Computational Complexity | February 22, 2018 at 07:43 AM

From Computational Complexity

Corporate Education

First of all read the #metoo testimonial going around the TCS blogosphere. Our field is not immune. Last Sunday Frank Bruni wrote an op-ed column Corporations,... Lance Fortnow
From Computational Complexity | February 15, 2018 at 08:09 AM

From Computational Complexity

For the Love of Algorithms

Wired magazine labelled 2017 as The Year We Fell Out of Love with Algorithms. The article goes on to talk about how algorithms give us filter bubbles, affect elections... Lance Fortnow
From Computational Complexity | February 8, 2018 at 07:42 AM