acm-header
Sign In

Communications of the ACM

Blogroll


Refine your search:
dateMore Than a Year Ago
authorLance Fortnow
bg-corner

From Computational Complexity

While I Was Away

After the Oxford Workshop I enjoyed a two-week family vacation in Spain, where there was no rain in the plain, just very hot up to 106℉. The old Spanish citiesMeanwhile...

From Computational Complexity

Complexity in Oxford

Oxford, England is in the middle of a heat wave and it handles high temperatures about as well as Atlanta handles snow. But that can't stop the complexity and a...

From Computational Complexity

CRA Snowbird 2018

Marios Papaefthymiou (UC Irvine), Michael Franklin (U. Chicago), Larry Birnbaum (Northwestern) and me. This week I attended the 2018 Computing Research Association...

From Computational Complexity

The Mystical Bond Between Man and Machine

You just can't watch a movie these days without being inundated with trailers. First came Axl, a movie about a boys love for a military robotic dog.   "It's...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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...

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...
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account