From Schneier on Security
Artificial intelligence (AI) has been billed as the next frontier of humanity: the newly available expanse whose exploration
…
B. Schneier| February 29, 2024
Last week the Georgia Tech School of Industrial and Systems Engineering honored the 80th birthday of George Nemhauser and the 70th of Arkadi Nemirovski at an...Lance Fortnow From Computational Complexity | May 18, 2017 at 08:42 AM
Today we celebrate our mothers of course, but also the 100th anniversary of the birth of Bill Tutte, best known for his role in decrypting the Lorenz cipher used...Lance Fortnow From Computational Complexity | May 14, 2017 at 09:18 AM
Today a guest post from Periklis Papakonstantinou, coincidentally not unrelated to Bill's post earlier this week. I'll be back with a special post on Sunday.
I'm...Lance Fortnow From Computational Complexity | May 11, 2017 at 09:07 AM
Ahh summer. No Classes. Baseball. Opera Festivals. Time to focus on research and starting a new book. But, of course, many computer scientists travel the worldSTOC...Lance Fortnow From Computational Complexity | May 4, 2017 at 08:12 AM
While Bill marched at the main March for Science in DC, I marched at the satellite march in Atlanta, my daughter Molly in Chicago, Scott Aaronson in Austin,in...Lance Fortnow From Computational Complexity | April 27, 2017 at 09:57 AM
Today Georgia Tech had the launch event for our new Machine Learning Center. A panel discussion talked about different challenges in machine learning across the...Lance Fortnow From Computational Complexity | April 17, 2017 at 05:02 PM
"The only useful thing computer science has given us is Alice and Bob" - A physicist at a 1999 quantum computing workshop
Alice and Bob, great holders of secrets...Lance Fortnow From Computational Complexity | April 13, 2017 at 08:07 AM
In Atlanta last week a fire destroyed a major highway bridge right on my, and so many others, commutes. I've been playing with different strategies, like coming...Lance Fortnow From Computational Complexity | April 6, 2017 at 08:44 AM
In one of the hallway discussions of last week's Dagstuhl I learned about an upcoming STOC paper Deciding Parity Games in Quasipolynomial Time by Cristian Calude...Lance Fortnow From Computational Complexity | March 28, 2017 at 07:32 AM
This week I'm at the Dagstuhl workshop on Computational Complexity of Discrete Problems. As you long time readers know Dagstuhl is a German center that hosts...Lance Fortnow From Computational Complexity | March 23, 2017 at 05:16 AM
If NP is in ZPP is the entire polynomial-time hierarchy in ZPP? I saw this result used in an old TCS Stackexchange post but I couldn't find a proof (comment ifharder...Lance Fortnow From Computational Complexity | March 16, 2017 at 02:54 PM
Lisa Randall wrote a New York Times book review of Carlo Rovelli's Reality Is Not What It Seems with some interesting responses. I want to focus on a single sentence...Lance Fortnow From Computational Complexity | March 9, 2017 at 04:47 PM
I did some counting and the 35 academic faculty members in the Georgia Tech School of Computer Science come from 14 different countries. My co-authors come from...Lance Fortnow From Computational Complexity | March 2, 2017 at 08:02 AM
Kenneth Arrow, the Nobel Prize winning economist known for his work on social choice and general equilibrium, passed away Tuesday at the age of 95.
I can't cover...Lance Fortnow From Computational Complexity | February 23, 2017 at 07:07 AM
Tuomas Sandholm (center) and Ph.D. student Noam Brown (via CMU)
Congratulations to Liberatus the new poker champ. Liberatus, an AI program, beat several top-ranked...Lance Fortnow From Computational Complexity | February 16, 2017 at 07:51 AM
Arash Rafiey, Jeff Kinne and Tomás Feder settle the Feder-Vardi dichotomy conjecture in their paper Dichotomy for Digraph Homomorphism Problems. Jeff Kinne is my...Lance Fortnow From Computational Complexity | February 9, 2017 at 07:11 AM
A solidarity rally held at Georgia Tech today
There are ten Iranian members of my department, the School of Computer Science at Georgia Tech, all of whom face...Lance Fortnow From Computational Complexity | February 2, 2017 at 02:15 PM
As I checked in at the Holiday Inn in New Brunswick Wednesday night, they asked me if I had stayed there before. I said it has been a while and they lookedWorkshop...Lance Fortnow From Computational Complexity | January 26, 2017 at 08:47 PM
There's a wonderful new series of math videos PBS Infinite Series hosted by Cornell Math Phd student Kelsey Houston-Edwards. Check out this latest video on Markov...Lance Fortnow From Computational Complexity | January 19, 2017 at 08:25 AM
"So it is quasipolynomial time again"
Short Version: Babai fixed his proof.
In November 2015 László Babai announced a talk "Graph Isomorphism in Quasipolynomial...Lance Fortnow From Computational Complexity | January 10, 2017 at 02:27 PM