Boaz Barak in a comment last week mentioned one of my favorite survey papers, Russell Impagliazzo's A Personal View of Average-Case Complexity presented at the...
Are you an American IEEE member? Now you can help guide American foreign policy. IEEE-USA has announced an Engineering and Diplomacy Fellowship where IEEE...
Tomorrow is the last day for early registration for this year's Complexity Conference in Amherst. I promise a good time will be had by all. -- Posted by Lance...
Let's end this week how we started it, with a survey paper. Luca Trevisan has recently posted on ECCC a new survey Some Applications of Coding Theory in...
With the June issue, Jacobo Torn takes over the editorial duties of the BEATCS Complexity Column . Following with tradition, he wrote his first column, Space...
Professional Societies perform valuable roles in academics. They give awards, sponsor conference and publish reasonably-priced journals as well as bulletins,...
My first weblog contest. Guess the paid attendance (including students and postdocs) at next week's STOC conference . Closest to the correct answer receives an...
May Edition I have always loved results that find connections between previously-thought different areas of complexity. This month we highlight one of the...
STOC got underway Sunday with a full slate of talks and a lengthy business meeting last night. I do not have time for a long post now so I will just bring you...
Journals dominate the non-research talk at STOC. We had a long discussion at the business meeting about the special issue of STOC. A little background: For the...
A commenter asks a good question for a bad reason: Would a proof of the Riemann Hypothesis have any impact on complexity theory? Rather surprisingly the answer...
Wisconsin Professor Dieter van Melkebeek has a paper at the ICALP conference but cannot go to Finland to present it. Why not? Delayed processing of his green...
Shimon Even was born in Israel on June 15th, 1935. He died on May 1st, 2004. In addition to his pioneering research contributions (most notably to Graph...
This week I am in Amherst at the University of Massachusetts for the 19th IEEE Conference on Computational Complexity . Lots of fun papers and complexity...
I received the following from Nikolay Vereshchagin. The combinatorial question I have discussed last summer at the rump session at Computational complexity ...
The list of accepted papers for the upcoming FOCS conference in Rome is out. [ Thanks Suresh ] A few complexity papers to note: Ran Raz finds easy languages...
Rakesh Vohra pointed me to some interesting takes on journals in economics. Economics runs on a different model than computer science; conferences are less...
The Elsevier owned Journal of Computer and System Sciences will pay an honorarium of $100 to a cognizant editor for each paper handled. According to...
Another fourth of July out of the states, this time at the Banff International Research Station (BIRS), a Canadian mathematical conference center similar in ...
Yesterday Avi Wigderson gave a talk entitled Gems of Additive/Combinatorial Number Theory where he presented three interesting results about the sizes of sets...
A Guest Post by Bill Gasarch and Brian Postow In the 1970's there was some hope that deep techniques from Computability theory might crack P vs NP. Some nice ...
Some final notes from the Banff workshop. First a few lemmas used in Wigderson's talk . Lemma 1: Let G=(V,E) with n vertices and m edges and m4n. Let cr(G) be...
When we have a conference or a workshop in a tourist location, like Banff, many of the participants bring their non-computer scientist spouses and sometimes...
What the world needs are the time and space hierarchies clearly spelled out in one place. A function t is time-constructible if there is a Turing machine M ...
In nearly every scientific discipline conferences play a minor role. Most conferences have a few plenary speakers mixed with massive parallel sessions where...
Michael Nielsen is in the midst of a long series of posts on Principles of Effective Research . Much of what he says seems obvious but the obvious often needs...
In this post I will describe some recent results in extracting randomness in terms of Kolmogorov complexity since I (and some others) find Kolmogorov...
Maryland Professor Carl Smith passed away last night losing his year and a half battle with brain cancer. He was an expert in inductive inference and an active...
June Edition Branching programs give us a nice way to model time and space bounds for Boolean functions in a simple non-uniform model. A branching program is a...
The US House Appropriations committee has passed the NSF budget at a 2% ($111 Million) cut. There are still many more phases in the budget process to go but...
Having problems with message search?
Fill out this form to ensure your group is one of the first to be migrated to the new message search system.
