Refine your search:

From Computational Complexity
#### Favorite Theorems: Compressing the Local Lemma

Not only did Moser give a near optimal construction, but he did so in my favorite STOC talk of the decade.
A Constructive Proof of the Lovász Local Lemma by Robin...

From Computational Complexity
#### Four Centuries of Logarithms

I just returned from visiting my former student Rahul Santhanam in Edinburgh. The National Museum of Scotland has an exhibit on logarithms, first published in...

From Computational Complexity
#### Computer Dating

My brother went through his old stuff cleaning out his apartment in New York and stumbled upon the 1981 computer dating questionnaire I wrote in high school. Forgive...

From Computational Complexity
#### Favorite Theorem: PCP Simplified

The famous Probabilistically Checkable Proof Theorem due to Arora, Lund, Motwani, Sudan and Szegedy states that every problem in NP has a proof that can be checked...

From Computational Complexity
#### CCC 2014

I'm returning from the 2014 IEEE Conference on Computational Complexity in Vancouver, unfortunately missing the last day. Several very nice talks including a wonderful...

From Computational Complexity
#### Wassily Hoeffding 1914-1991

In honor of the 100th anniversary of the birth of Wassily Hoeffding today, let's recall his incredibly useful inequality.
Prob(|X-pn|>εn) < 2e-2ε2n
where...

From Computational Complexity
#### STOC 2014

At the just completed STOC conference I received the 2014 SIGACT Distinguished Service Prize. Part of this citation reads"His blog, and many others that followed...

From Computational Complexity
#### Forgotten but not Lost in a Mapless World

Massimo Vignelli passed away on Tuesday, a visionary designer known for many things in particularly the
1970s NYC Subway Map. I used to pour over this map assteering...

From Computational Complexity
#### Theory Jobs 2014

In the fall we list theory jobs, in the spring we see who got them. Similar to last year, I created a fully editable Google Spreadsheet to crowd source who is going...

From Computational Complexity
#### Losing the Middle

In the 70's growing up, to listen to music I had a turntable for vinyl records. The quality of music went up almost continuously with the amount you were willing...

From Computational Complexity
#### 1984 + 30

Back in 7th grade we had some discussion in history class long since forgotten but was ended by the statement "Remember, 1984 is only eight years away". While the...

From Computational Complexity
#### (IEEE) Conference on Computational Complexity

The 29th IEEE Conference on Computational Complexity will be held in Vancouver June 11-13. Student travel award deadline is TOMORROW Monday May 5th, early registration...

From Computational Complexity
#### Favorite Theorems: Equilibrium

The past decade has seen an explosion of work tying together theoretical computer science and micro-economics. Much has come in the area of market design, where...

From Computational Complexity
#### Libraries Without Books

Georgia Tech in its library renovation will move the vast majority of its books into a combined Emory/Tech Library Service Center off-campus. Very few people use...

From Computational Complexity
#### Announcements

Time for a short rundown of announcements.
STOC will be held May 31-June 3 in New York City. Early registration and hotel deadline is April 30. Student travel...

From Computational Complexity
#### Should you reveal a P = NP algorithm?

A reader asks
What would you do if you could prove that P=NP with a time-complexity of n2 or better... moreover, would you publish it?
There are all theseheartbleed...

From Computational Complexity
#### Favorite Theorems: Extended Formulations

The first couple of favorite theorems took place at the beginning of the last decade, but recent years have brought exciting results as well, such as the limitations...

From Computational Complexity
#### I am Bill Gasarch

I have a confession to make. Remember back in 2007 when I retired from the blog for about a year. I didn't actually retire at all but instead took the blog innew...

From Computational Complexity
#### Should We Have a TCS Ethics Board?

We sometimes hear of the (rare) scientist who fakes data or results of experiments. In theoretical computer science one cannot fake a theorem, particularly an important...

From Computational Complexity
#### Spring Breaking at Dagstuhl

It's spring break at Georgia Tech and time to head to Germany for the Dagstuhl Seminar Computational Complexity of Discrete Problems. Lots of discussion on...