Refine your search:

From Computational Complexity
#### And the Winners Are...

I always like that the announcement of accepted papers for the Computational Complexity Conference happens around the time of the Academy Awards. These acceptances...

From Computational Complexity
#### Richard Hamming Centenary

Richard Hamming was born a hundred years ago today in Chicago. He worked on the Manhattan Project during World War II, moved to Bell Labs after the war and started...

From Computational Complexity
#### Computers Turn Good and Evil

Entertainment Weekly proclaimed 2015 the year that artificial intelligence will rule the (movie) world with talk of the Terminator reboot, the new Avengers movie...

From Computational Complexity
#### Reusing Data from Privacy

Vitaly Feldman gave a talk at Georgia Tech earlier this week on his recent paper Preserving Statistical Validity in Adaptive Data Analysis with Cynthia Dwork, Moritz...

From Computational Complexity
#### There Should be an Algorithm

My high school daughter Molly was reading her Kindle and said "You know how you can choose a word and the Kindle will give you a definition. There should be anword...

From Computational Complexity
#### The Impact Factor Disease

The Institute of Science Information (ISI) was founded in 1960 to help index the every growing collection of scientific journals. The founder of ISI, Eugene Garfield...

From Computational Complexity
#### The History of the History of the History of Computer Science

In 2007, the science historian Martin Campbell-Kelly wrote an article The History of the History of Software, where he writes about how he initially wrote histories...

From Computational Complexity
#### 2014 Complexity Year in Review

Theorem of the year goes to 2-Server PIR with Sub-polynomial Communication by Zeev Dvir and Sivakanth Gopi. In Private Information Retrieval you want to accessshowed...

From Computational Complexity
#### Undergraduate Research

I just received the Cornell Math Matters, dedicated to the memory of Eugene Dynkin who passed away on November 14 at the age of 90. In my freshman year at Cornell...

From Computational Complexity
#### The NIPS Experiment

The NIPS (machine learning) conference ran an interesting experiment this year. They had two separate and disjoint program committees with the submissions split...

From Computational Complexity
#### The Ethics of Saving Languages

The linguist John McWhorter wrote an NYT opinion piece entitled Why Save a Language? where he argues why we should care about saving dying languages, basically...

From Computational Complexity
#### Favorite Theorems Recap

We've now completed five decades of favorite theorems.
1965-1974
1975-1984
1985-1994 (PDF)
1995-2004
And to recap the ten we chose this year from 2005-2014
...

From Computational Complexity
#### A November to Remember

The Imitation Game starring Benedict Cumberbatch as Alan Turing opens in the US on November 28. If you read this blog you should see that movie. If one challenged...

From Computational Complexity
#### From Homework Solution to Research Paper

Inspired by the Dantzig Story I occasionally put an open problem on a class assignment. Never worked, though I did have a student get a research paper from solving...

From Computational Complexity
#### George Dantzig >= 100

We celebrate the 100th anniversary of the birth of George Dantzig today. In his obituary post we talked about his work on optimization, particularly the simplex...

From Computational Complexity
#### Favorite Theorems: Circuit Lower Bounds

My long time blog readers should have no surprise on my final favorite theorem of 2005-2014.
Nonuniform ACC Circuit Lower Bounds by Ryan Williams (PDF)
We sawlist...

From Computational Complexity
#### Metrics in Academics

Congratulations to the San Francisco Giants, winning the World Series last night. In honor of their victory let's talk metrics. Baseball has truly embraced metrics...

From Computational Complexity
#### Sipser Symposium

On Sunday we had the Symposium on Theoretical Computer Science on the Occasion of Michael Sipser's 60th birthday to celebrate what Mike has brought to research...

From Computational Complexity
#### MSR SVC Letters

The Committee for the Advancement of Theoretical Computer Science put together an open letter to several research leaders at Microsoft.
We feel that there should...

From Computational Complexity
#### The Curious Case of NP and NEXP

NP (nondeterministic polynomial time) and NEXP (nondeterministic exponential time) are provably different classes by the nondeterministic time hierarchy. No surprise...