acm-header
Sign In

Communications of the ACM

Blogroll


bg-corner

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...

The First Pseudorandom Generator--Probably
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...

From Computational Complexity

Voting on Mathematical Truths: The Axiom of Det.

One of the founders of Conservapedia (a conservative alternative to Wikipedia) said the following on The Colbert Report: There is an absolute truth. People don't...

From Computational Complexity

How to tell how good a TV show is

(This is my last blog of the year. Lance will interupt his blog sabbatical to do an END OF THE YEAR blog later.) The TV show MONK recently finished its 8thHow...

What is an Explicit Construction?
From Computational Complexity

What is an Explicit Construction?

The Prob method (usually credited to Erdos) was once considered quite novel: You show something exists but you don't show how to construct it! An early exampleThe...

From Computational Complexity

A hard problem inspired by an easy problem

The following problem was problem 1 (the easy one) on the Maryland Math Competition 2009 (I will later report on how the students did on it). Show that for every...

Guest Post- Women in Theory Workshop
From Computational Complexity

Guest Post- Women in Theory Workshop

(Tal Rabin requested to post this so I am doing so. This post is essentially her email, so call it a guest post.)   There will be a Women In Theory workshop for...
Sign In for Full Access
» Forgot Password? » Create an ACM Web Account