Refine your search:

From Computational Complexity
#### Cosmos from Generation to Generation

During high school, well before the world-wide web with its bloggers and YouTube, out came a series Cosmos that I watched religiously. Back then you had to watch...

From Computational Complexity
#### Favorite Theorems: Unique Games

Michel Goemans and David Williamson made a splash in the 90's using semidefinite programming to give a new approximation algorithm for the max-cut problem, a ratio...

From Computational Complexity
#### Why Become a Professor

Someone took me to task because in November I posted that the CRA News had 50 pages of job ads but didn't note that very few of those ads specifically were searching...

From Computational Complexity
#### Analog Adventures

I was 11 forty years ago when Dungeons and Dragons first appeared and by high school many of my friends spent far too many hours embarking on those fantasy adventures...

From Computational Complexity
#### IEEE and the Conference on Computational Complexity

Dieter van Melkebeek, current conference chair of the IEEE Conference on Computational Complexity has set up a forum to discuss the future affiliation of the conference...

From Computational Complexity
#### Favorite Theorems: Connecting in Log Space

We start the favorite theorems with a result that might surprise many is still less than ten years old.
Undirected Connectivity in Log-Space by Omer ReingoldPDF...

From Computational Complexity
#### Snow Days

An unexpected snowstorm hits the city in the middle of a workday. The roads get hopelessly clogged and I'm lucky to get home--many others just abandoned theirguarantees...

From Computational Complexity
#### What will we wrought?

When I went to college in the early 80's, students protested against college endowments invested in companies that had business in apartheid South Africa. My mother...

From Computational Complexity
#### Favorite Theorems: Introduction

I was invited to give a talk at the FST&TCS conference held in December 1994 in Madras (now Chennai). As I searched for a topic, I realized I was just finishing...

From Computational Complexity
#### Is Traveling Salesman NP-Complete?

[Nina Balcan asked me to mention that the COLT submission deadline is February 7]
Jean Francois Puget writes a controversial post No, The TSP Isn't NP Complete...

From Computational Complexity
#### 2013 Complexity Year in Review

The complexity result of the year goes to The Matching Polytope has Exponential Extension Complexity by Thomas Rothvoss. Last year's paper of the year showed that...

From Computational Complexity
#### To Write, or Not to Write, That Is the Question

Guest post by Vijay Vazirani
Our field has been blessed with some great books: classics such as Knuth's volumes and Garey & Johnson literally got the field going...

From Computational Complexity
#### Security Changes

A couple of policy changes recently, one that supposedly enhances privacy and another that could reduce it.
Google has been implementing perfect forward secrecy...

From Computational Complexity
#### Approximate Computing

Hadi Esmaeilzadeh is the newest professor in the School of Computer Science at Georgia Tech. Hadi works in computer architecture and did some great work on dark...

From Computational Complexity
#### Bitcoins Revisited

Two years ago I gave a lecture and posted about bitcoin. Of course what I didn't do was buy a bitcoin whose value back then was about $3 and today runs in the $1000...

From Computational Complexity
#### The New Patrons

A few centuries ago if you wanted to do science and not independently wealthy you needed help.
Most of the important astronomers and natural philosophers (as well...

From Computational Complexity
#### Local Reductions

With the STOC deadline passing on Monday, now is a good time to look at the arXiv to see what has been posted since then. Hamid Jahanjou, Eric Miles and Emanuele...

From Computational Complexity
#### A Theorist Goes to SOSP

Monday I attended the 24th Symposium on Operating Systems Principles, the lead conference for computer systems research. Why would a nice theorist go to SOSP? Trying...

From Computational Complexity
#### Andrzej Mostowski (1913-1975)

Andrzej Mostowski was born 100 years ago today. While Mostowski worked in many areas of logic, including early fundamental work on model theory, for our readers...

From Computational Complexity
#### Science and Humanities

David Hollinger, a historian, wrote a recent Chronicle Review article The Wedge Driving Academe's Two Families Apart: Can STEM and the human sciences get along?...