Refine your search:

From Computational Complexity
#### FOCS 2010 CALL FOR PAPES is out!

(Univ of MD at College Park had Monday, Tuesday, Wed, Thursday all off.
I've spend most of that time shoveling snow, so I am tired. Hence I am glad
to have a SHORT...

From Computational Complexity
#### What is an Elementary Proof?

What is an Elementary Proof?
Different things in different contexts.
An Elementary Proof is one that does not use Complex Analysis.
Basic Calculus is fine.
This...

From Computational Complexity
#### The more things change the more things change

There have been some articles on how much things have changed
because of technology.
One from the Washington Post Magazine, titled
Going, Going, ..., Gone
lists...

From Computational Complexity
#### Time Space Tradeoffs for SAT- good resuls but...

This is a real conversation between BILL and STUDENT (a Software Engineering Masters Student
who knows some theory). As such there are likely BETTER arguments BILL...

From Computational Complexity
#### Naming and Ranking

Martin Kruskal
invented Soliton Waves which were a very important concept in
Physics.
Rebecca Kruskal (Martin's Granddaughter): Daddy, how come they are not...

From Computational Complexity
#### Travel Support for Grad Students who GOTO STOC 2010

If you are a grad student and want to goto STOC 2010
there is travel support money that you can apply for.
See
here
for details.
What is the best way to get...

From Computational Complexity
#### Referees'''' reports

A commenter a LOOOOONG time ago left the following:
Tell me, Gasarch, how in the world do you get your
papers published when you consistently skip the
apostrophe...

From Computational Complexity
#### Guest post on ICS 2010 (x of y for some x and y)

(Another Guest post about ICS 2010. From Aaron Sterling.
Is he on his way to break the MOST GUEST POSTS IN A YEAR record?
I doubt it- I think I hold it from before...

From Computational Complexity
#### The First Pseudorandom Generator--Probably

(The following was told to be by Ilan Newman at Dagstuhl 2009. His source was the book The Broken Dice and other mathematical tales of chance.)
What was the...

From Computational Complexity
#### When is a theorem really proven?

One of the comments on
this blog pointed out correctly that for a theorem
to be accepted by the community is not a Eureka Moment.
It is a social process. The author...

From Computational Complexity
#### Job Postings

Two sites to look for jobs at:
Lance Fortnow
set up this blog that collects theory annoucments including jobs:
here
Boaz Barak Obama, in an effort to create...

From Computational Complexity
#### Two Theorems this blog missed

I warned Lance to wait until early Jan to post
2009 Complexity Year in Review.
It was my fear that by posting it on Dec 28, 2009 he may miss out if
someone proves...

From Computational Complexity
#### Should CCC2012 be at the North Pole?

The last few posts on ICS in China have lead to off-topic (though maybe they were not off topic)
comments on whether we should have conferences in countries who...

From Computational Complexity
#### Do Innovative papers have a hard time getting into STOC and FOCS? I ask this objectively with no ax or teeth to grind.

(This is my last post until next week Tuesday.)
Many people believe the following:
FOCS and STOC only take technically hard results on
problems that we already...

From Computational Complexity
#### ICS I: snapshots and the longer view (guest post)

(Guest Post by Rahul Santhanam)
Title: ICS I : Snapshots & The Longer View
1. Local Arrangements: Kudos to the organizing committee for going far
beyond...

From Computational Complexity
#### Guest Post on ICS 2010 (2 of 3)

Innovations in Computer Science 2010 (post #2)
Guest Post by Aaron Sterling
This is the sequel to my previous post on ICS 2010, the new theoretical computer...

From Computational Complexity
#### Guest Post on ICS 2010 (1 of 3)

Innovations in Computer Science 2010 (post #1)
Guest post by Aaron Sterling
This is the first of three posts about ICS 2010, the much-discussed "concept...

From Computational Complexity
#### COLT and CCC

The COLT (Computational Learning Theory)
call for papers
is out. (Actually its been out since October but I was only recently
emailed it.)
For other information...

From Computational Complexity
#### DO NOT do this when choosing books for your class

When I took my first graduate course in complexity theory the professor
had FOUR books on the REQUIRED FOR THE COURSE list.
I bought all four. He said that
We...

From Computational Complexity
#### Axioms: What should we believe?

Some misc thoughts on set theory inspired by yesterdays comments
and other things.
Geometry:
Use Euclidean Geometry when appropriate, for example if you are
So...