Refine your search:

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

From Computational Complexity
#### 2014 Fall Jobs Post

Tis the season for the fall jobs post. Please list any jobs, academic or industrial, in theoretical computer science broadly construed in the comments to this post...

From Computational Complexity
#### Favorite Theorems: Multilinear Circuits

In the past decade we have seen a strong program in algebraic circuit complexity. If you just define circuits using multiplication and addition gates, sometimes...

From Computational Complexity
#### MikeFest

I rarely highlight individual events on the blog, but one's advisor only turns sixty once. We will honor Michael Sipser at MIT on Sunday, October 26 with a one...

From Computational Complexity
#### Typecasting in Dagstuhl

After this pre-recorded typecast, we learned of the tragic death of Alexey Chervonenkis, the C of VC dimension, a huge loss to the learning community. We’ll have...

From Computational Complexity
#### Goodbye MSR-SVC

This week I'm back at Dagstuhl for the Workshop on Algebra in Complexity Theory. Bill is here as well and we hope to have a typecast for you later this week.
The...

From Computational Complexity
#### Richard Lipton Wins Knuth Prize

Georgia Tech professor and fellow blogger Richard Lipton will receive the 2014 Knuth Prize at the upcoming FOCS conference in Philadelphia. The Knuth Prize is given...

From Computational Complexity
#### Beyond the Commodity

Back in 2005 I lamented the fact that students viewed computers as a commodity, a tool they use, like an automobile, but have no reason to understand how or why...

From Computational Complexity
#### Favorite Theorems: Quantum Interactive Proofs

Practical quantum computing still has many hurdles to jump through, but the quantum computing model does generate great complexity questions and often surprising...

From Computational Complexity
#### Sixteen Years in the Making

Every paper has a story but Sunny Daniel's Arxiv paper from yesterday deserves a blog post.
We begin in 1982 when Ravi Kannan proved that Σ2 (the problems computable...

From Computational Complexity
#### A Deadly Side of Complexity

Better algorithms can lead to better medicine and save lives. Just today Tim Gowers discusses Emmanuel Candès' ICM Plenary Lecture, which among other things describes...

From Computational Complexity
#### Turing's Oracle

My daughter had a summer project to read and summarize some popular science articles. Having heard me talk about Alan Turing more than a few times, she picked a...

From Computational Complexity
#### Complexity versus Algorithms: The FOCS Challenge

In recent years, I've heard complaints from my complexity colleagues that FOCS and STOC are mostly algorithms and from the algorithm buddies that STOC and FOCSFOCS...

From Computational Complexity
#### Favorite Theorems: Limited Independence

When can limited randomness act as well as true random bits?
Polylogarithmic independence fools AC0 circuits by Mark Braverman (JACM 2010)
To explain this result...

From Computational Complexity
#### Subhash Khot wins Nevanlinna

At the opening ceremonies of the International Congress of Mathematicians in 2014, Subhash Khot was awarded the Rolf Nevanlinna Prize, given every four years to...

From Computational Complexity
#### The Burden of Large Enrollments

This week I'm at the CRA Snowbird conference, the biennial meeting of CS chairs and other leaders in the field. In 2012 many of the discussion focused on MOOCS....

From Computational Complexity
#### Elfdrive

New York Times, dateline June 11, 2019
With a near record-setting investment announced last week, the self-driving car service Elfdrive is the hottest, mostpiece...