Computational Complexity

Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch

Tuesday, December 30, 2003

End of Year Thoughts

›
We had another solid year for theoretical computer science and computational complexity with many exciting results such as the polynomial ...
Sunday, December 28, 2003

John von Neumann

›
Today is the 100th anniversary of the birth of John von Neumann , one of the greatest mathematicians of the 20th century. Let me discuss t...
Friday, December 26, 2003

That's My State

›
Nothing like this Chicago Tribune story to ruin your holidays. Apparently the Illinois Board of Higher Education has launched a study of fa...
Monday, December 22, 2003

Scientific Superstars

›
On Saturday I visited the Einstein Exhibit at Chicago's Field Museum . Some manuscripts and letters and a nice exhibit explaining why ...
Thursday, December 18, 2003

Does NP=UP?

›
Time for another of my favorite open problems. Does NP=UP imply the polynomial-time hierarchy collapses? UP is the class of languages...
4 comments:
Monday, December 15, 2003

Does PowerPoint Make You Dumb?

›
Yesterday the New York Times Magazine had its annual "The Year in Ideas" issue. Ideas Futures Markets in Everything and Prov...
Friday, December 12, 2003

Ordering Authors

›
Every scientific field has their own rules for the order of authors in a paper. In theoretical computer science, tradition dictates that we...
Wednesday, December 10, 2003

Seven Naughty Words

›
Want an easy rule to greatly improve your writing? Just avoid the following words, particularly in the abstract and introduction of your pa...
Monday, December 08, 2003

Two Uses of Randomness

›
Over the last 15 years, two very active research areas seem at odds. Derandomization results have shown us that we can often remove random...
Thursday, December 04, 2003

A Regular Problem Solved

›
Paz Carmi, Yinnon Haviv and Enav Weinreb from Ben-Gurion University have solved the regular language problem I posted last month. The ...
Wednesday, December 03, 2003

The Elsevier Dilemma

›
The Cornell University Library has announced it will drop a substantial number of their Elsevier subscriptions, part of a general proble...
Tuesday, December 02, 2003

The NSF and SIGACT News

›
First an update on NSF program solicitations: The Formal and Mathematical Foundations cluster has posted its solicitation which includes ...
Monday, December 01, 2003

Show Us Your Papers

›
I hope you all got your Complexity submissions in on time last week. Now let the rest of the world see your work. Make them into technical...
Wednesday, November 26, 2003

Critical Mass

›
In the left column of this weblog's homepage, I've added a new "weblogs" section to list the academic weblogs that I have...
Monday, November 24, 2003

Theory and XML

›
XML (eXtensible Markup Language) has become quite a popular data format in recent years. XML roughly corresponds to a tree. For example, ...
Friday, November 21, 2003

Rational Functions and Decision-Tree Complexity

›
I thought I should mention some of my favorite and most frustrating open questions over the years. Here's one of them: Let f:{0,1} n →{...
4 comments:
Wednesday, November 19, 2003

Midwest Theory Day

›
Over the years a number of localized theory workshops have developed which bring together researchers from around the area to mingle and l...
Monday, November 17, 2003

Editors Needed

›
Back in my science-fiction reading days, I particularly remember one editorial written in one of those anthology magazines about 1980: In ...
Friday, November 14, 2003

A Regular Problem

›
Here's a problem from Janos Simon. For a set A, let L(A)={x | for some m≥0, x m is in A} Simon asked, as a homework problem, to s...
Wednesday, November 12, 2003

Opportunities at Chicago (Blatant Plug)

›
[I will do this just once. Feel free to use the comments link to mention your own institution.] We are seeking theory graduate students ...
‹
›
Home
View web version
Powered by Blogger.