Refine your search:

From Computational Complexity
#### Things a Complexity Theorist Should Do At Least Once

A few weeks ago, Suresh wrote a post Things a TCSer should have done at least once with the caveat
This list is necessarily algorithms-biased. I doubt you'll need...

From Computational Complexity
#### Poset Games are PSPACE-complete

Consider the following game on a poset, each player takes turns picking an element x of a finite poset and removes all y ≥ x. First one to empty the poset wins....

From Computational Complexity
#### Theory Conferences Galore

Early registration for the FOCS conference in New Jersey is September 27th. There is some travel support available for students and postdocs, deadline is this Friday...

From Computational Complexity
#### Max Flow

A couple of weeks ago Suresh tweeted the following result of James Orlin
Max flows in O(nm) time or better. jorlin.scripts.mit.edu/Max_flows_in_O…
— Suresh Venkat...

From Computational Complexity
#### The Time of Research

Among the many conference/journal discussions, one systems person said the reason they don't publish in journals is that their work is very dependent on current...

From Computational Complexity
#### The Net or the Jet

I spent the first half of my life in the jet age but not in the Internet age. I could fly anywhere in the world but the fastest way to get a research paper to another...

From Computational Complexity
#### Knuth Prize

Leonid Levin will receive the Knuth Prize, and give the corresponding lecture, at FOCS this year. The Knuth Prize is jointly given by ACM SIGACT and the IEEE TC...

From Computational Complexity
#### Ten Years of the Complexity Blog

On August 22, 2002 I wrote the following immortal words to start this blog
This is my complexity web log. I'll be giving random thoughts about computational complexity...

From Computational Complexity
#### Is the Turing Test Still Interesting?

Besides the Turing machine, Alan Turing also developed what we now call the Turing Test in Turing's seminal 1950 AI paper "Computational Machinery and Intelligenc...

From Computational Complexity
#### Another Algorithmic Market Failure

In 2009, Matt Cushman, Managing Director at Knight Equity Markets, gave a seminar at Northwestern on "High Frequency Trading". Here is the abstract:
High frequency...

From Computational Complexity
#### MOOCs

I haven't posted in about a month. A combination of traveling, vacation, moving to Atlanta and getting started as chair. I appreciate why Michael Mitzenmacher stopped...

From Computational Complexity
#### Why is it called the Turing Award?

The ACM Turing Award represents the highest honor in the computing research community, the closest we have to a Nobel prize in computer science. In this centenary...

From Computational Complexity
#### Instance Compression

Some announcements: FOCS Accepts, ITCS Call and ToC Special Issue for Rajeev Motwani
I'd like to highlight one of the new FOCS papers, New Limits to Classical by...

From Computational Complexity
#### Transitions

On July 1 I officially move jobs from Northwestern to Georgia Tech, a change not just in location but in role as I become a department chair.
I'm proud by what...

From Computational Complexity
#### Alan Turing (1912-1954)

Today we celebrate the 100th anniversary of the birth of Alan Turing, remembering his incredible life and mourning his tragic death. Alan Turing simply askedwebcast...

From Computational Complexity
#### Name My Book

As many of you know I have been working on a non-technical popular science book on the P versus NP for a general audience. The book is mostly finished but the biggest...

From Computational Complexity
#### Fortnoy's Complaint

During my daughter's 8th grade graduation last week, the teacher reading the names said "Molly Fortnoy...I mean Fortnow". I felt for Molly. When my name was first...

From Computational Complexity
#### Mihai P?tra?cu (1982-2012)

Mihai P?tra?cu passed away Tuesday after a bout with brain cancer. Even though he hadn't reached his 30th birthday, he had already produced a number of major achievements...

From Computational Complexity
#### Which Books to Keep?

Moving is an excuse to go through your possessions and weed out what you don't need anymore. Over my professional life I've collected two large bookcases full of...

From Computational Complexity
#### Theory Jobs 2012

The theoretical computer science job market has mostly settled so time for the annual spring jobs posts. I set up a Google Spreadsheet that everyone can edit so...