In case you need a topic for your weblog: what about journal rankings for theoretical computer science journals? I was looking for something like that for my tenure portfolio. The only web-info I found on the topic was here whose reliability is hard to judge.

Here's how I rank theory journals.

1. Journal of the ACM.
2. SIAM Journal on Computing.
3. A large equivalence class of every other major theory journal.
4. Information Processing Letters which publishes short articles that don't merit publication in the above.

Special issues rank higher, especially those devoted to the best papers of a strong conference. On the other hand, I put no faith on the quality of theory papers that appear in non-theory and especially non-CS journals no matter how they are ranked in their respective field. More than a few rather weak CS papers have appeared in Science, the gold standard for many other scientific disciplines.

--
Posted by Lance to My Computational Complexity Web Log at 7/28/2004 03:03:03 PM

A professor's life has many responsibilities. Teaching and research of course but also paper writing, grant proposals, meeting with students, and administrative tasks including seemingly endless committee meetings. When I visit another university I leave most of these responsibilities behind so I can focus on research. I also expect the people who invited me to make time in their schedules so we can work together. That way even a short visit can be quite productive.

As the length of the visit increases it becomes harder to avoid these other responsibilities and the amount of research time per day decreases. In the extreme, two people who work at the same university for years end up spending very little time talking research together.

This explains why teleconferencing will never replace traveling no matter how technologically advanced. The social requirements of a short visit require people to spend time together in ways a teleconference cannot. What teleconferencing will do is "allow" me to attend those endless committee meetings wherever I am.

--
Posted by Lance to My Computational Complexity Web Log at 8/2/2004 08:53:01 AM

It is with great sadness that I write to inform you that Larry Stockmeyer passed away. He died at his home as he had wished when he fell terminally ill a few weeks ago.

Larry was one of the pioneers of computational complexity who made fundamental and lasting contributions to the field. His death creates a void in our community that cannot be filled.

1. If SAT does not have polynomial-size circuits then SAT then Σ₂^p∩Π₂^p which contains SAT does not have n^k-size circuits.
2. If SAT has polynomial-size circuits then Σ₄^p=Σ₂^p∩Π₂^p (Karp-Lipton) and thus Σ₂^p∩Π₂^p does not have n^k-size circuits.

Vinod Variyam recently observed that the class PP which is not known to contain S₂^p also cannot have n^k-size circuits. Here is his proof: If PP has n^k-size circuits then PP is in P/poly which implies the polynomial-time hierarchy and in particular Σ₂^p is in MA which is in PP which has n^k-size circuits contradicting Kannan.

Read Variyam's paper for details and references.

--
Posted by Lance to My Computational Complexity Web Log at 8/4/2004 05:45:06 AM

If you are completely altruistic you should announce your progress as this will best advance science quickly. But as in the end you need to worry about your own publication record, particularly for a young researcher, the answer isn't so clear. Of course it depends on many factors including your belief that you or others could extend the work as well as when the next conference deadline occurs.

Oddly enough before the internet (in the eighties) such decisions were easier. You could write up a technical report to establish your result and you would have months before your work spread throughout the community. This gives you plenty of time to try and extend the work. The quick spread of information not only improves collaborative work as it does, but forces us to make decisions that we could avoid in the past.

--
Posted by Lance to My Computational Complexity Web Log at 8/6/2004 11:26:28 AM

How can we evaluate risk? Decision scientists have developed a measure called micromorts (μmorts). A μmort is a one-millionth chance of death. Sounds gruesome but by counting micromorts we can analyze the right choices to keep the most people alive.

All of three lap children have died in airplane crashes where their parents survived since 1987. The average driver runs the risk of about .02 μmorts/miles. If the average car trip is say 500 miles that translates to about 10 μmorts for each child in the car. Three laptop children have died in airplane crashes where the parent has survived since 1987. This translates to the equivalent of 300,000 car trips or about 15,000/year. About 6 million children ride on laps on airplanes each year, so if more than 0.25% of them were to ride in a car instead because of the higher prices, we would about cost lives by requiring safety seats on planes. My numbers, drawn from various internet sources, don't tell the whole story but nevertheless we can and should do a full analysis before setting policy.

It would be nice to have a list of various activities and how many μmorts they use, say you feel like parachuting, you can get an idea of how dangerous it is compared to say riding a bicycle. But we don't get such lists and people have to use their own judgments and often make the wrong decisions. We can also give a cost amount to a μmort; how much is it worth to save lives?

By finding statistics online you can calculate the risks in your various activities. You need to use about 3 μmort/day on average to keep a 10% chance of accidental death in your life. Spend them wisely.

--
Posted by Lance to My Computational Complexity Web Log at 8/9/2004 10:51:59 AM

Information markets live in limited academic-based markets like the Iowa Electronic Market and offshore sites like Tradesports. For example the current price on Tradesports for Bush winning the election is 51.5 which translates to a 0.515 probability that Bush will win indicating a very close contest.

For each state, Tradesports has a security on whether Bush will win that state. They also have some bundles of states. The price for Florida is 50.1, Ohio 55.4 and Bush winning both Florida and Ohio is 47.1. This gives a surprising correlation between Florida and Ohio. If you believe the theory there is a very high 0.94 probability that Bush wins Ohio given that he wins Florida and with a 0.89 probability these two very different swing states will go the same way.

Tradesports gives David Vitter a 59 percent chance of becoming a senator from Louisiana. David Vitter is the brother of CS theorist and former SIGACT chair Jeff Vitter.

--
Posted by Lance to My Computational Complexity Web Log at 8/10/2004 11:47:59 PM

1. diversity of the members of the group,
2. independent opinions of the group members, and
3. a method for aggregation of the opinions.

Chapter 8 is devoted to science and how many widely spread scientists developing and criticizing various theories lead to explosive growth in our understanding. He also notes that this ideal world has its flaws as unknown researchers have a harder time selling their work than more established scientists.

I don't agree with all the conclusions drawn by Surowiecki but he does lay out what we need to do and not do to benefit from the pooled knowledge of a group. We can also draw lessons in computer science as computation and information gets more distributed that we need to integrate to find the best solutions we can.

--
Posted by Lance to My Computational Complexity Web Log at 8/12/2004 09:13:05 PM

Consider a simple Arthur-Merlin game: Arthur probabilistically chooses a string r sends it to Merlin who responds with y and then Arthur runs some algorithm A(r,y) to decide whether to accept. Merlin's goal is to achieve the highest acceptance probability possible p for Arthur. Suppose we run the game twice in parallel, Arthur sends r₁ and r₂ and Merlin sends y₁ and y₂ and Arthur accepts if A(r₁,y₁) AND A(r₂,y₂). The highest possible acceptance probability will be p².

Now consider the MIP model with two Merlins M₁ and M₂ who cannot communicate with each other. Arthur sends u and v to M₁ and M₂ respectively who respond with y and z. Arthur accepts based on some function A(u,v,y,z). Once again M₁ and M₂ try to achieve the highest possible acceptance probability p. Now we run the game twice in parallel, Arthur sending u₁ and u₂ to M₁ and v₁ and v₂ to M₂ receiving y₁ and y₂ from M₁ and z₁ and z₂ from M₂ and accepting if A(u₁,v₁,y₁,z₁) AND A(u₂,v₂,y₂,z₂).

One might assume that the best the provers can achieve is p² (an assumption in fact made in an early paper co-authored by a certain weblog author) but in some circumstances the provers can do better. However Ran Raz shows that if p is less than 1, one can get an exponential decrease in p with a polynomial number of parallel rounds in

This paper settles one of the more perplexing aspects of multiple prover proof systems with a highly complicated proof. The result also plays a critical role in reducing the number of queries in probabilistically checkable proof systems which led to some optimal approximation bounds.

As a side note I am off on vacation tomorrow and Adam Klivans will guest blog in my absence. Enjoy.

--
Posted by Lance to My Computational Complexity Web Log at 8/16/2004 11:14:50 AM

Not only has society's view of the future changed but even the view about the future has changed. We live in an era of massive changes in technology particularly in access to communication and information. In the "Spaceship Earth" ride that shows the history and future of communications, the future shows two kids seeing and playing games with each other through video monitors, a task easily accomplished today with webcam-equipped networked PCs. But the ride missed many aspects of computers and the web. Who would have thought when I was a kid that I would now be writing this post on a commuter train that soon will be read around the world.

On the other hand we also dreamed of flying cars and space planes but the technology of transportation has not significantly changed since I was born and I don't expect major changes in the next forty years. So the future has come but not quite as we expected.

Technology has made the world a more homogeneous place. When at the Norway pavilion at EPCOT, an American visitor asked a Disney worker from Norway about what the country was like to visit. "The towns are like mid-size American cities" was the reply. I guess it is a small world after all.

--
Posted by Lance to My Computational Complexity Web Log at 8/27/2004 07:06:47 AM

Don't let "NC⁰" scare you, it simply means that every output bit depends on a constant number of input bits. In this paper the authors show that under reasonable assumptions one can have one-way functions and pseudo-random generators where each output bit depends on only four input bits. Quite surprising that such simple functions can be so hard to invert.

Their proof uses a clever but not overly complicated reduction using randomized polynomials from a larger class (⊕L/poly) to NC⁰ and so if one-way function and PRGs exist in the larger class than slightly weaker versions exist in NC⁰ respectively. The larger class contains many functions conjectured to be one-way or a PRG, including those based on factoring.

I remember Mike Sipser mentioning in a complexity class I took back in the mid-80's that "We don't even know how to show there are no one-way functions in NC⁰." Now we know why.

--
Posted by Lance to My Computational Complexity Web Log at 8/29/2004 07:29:25 AM

Today I gave the talk at the Atlantic Theory Seminar, not Atlantic as in ocean but Atlantic, Iowa (population 7,257). Located halfway between the theory groups of Iowa State and Nebraska, the Cass County branch of the Iowa Western Community College hosts a theory seminar every couple of months. Pretty impressive that these theory groups, faculty, postdocs and students, drive two hours each just to join for a seminar and talk theory with each other. Quite an enjoyable day in rural America.

Sorry about the quality of the picture above. We didn't have a digital camera so I took the picture with my cell phone.

--
Posted by Lance to My Computational Complexity Web Log at 8/31/2004 09:28:36 PM

Today I gave the talk at the Atlantic Theory Seminar, not Atlantic as in ocean but Atlantic, Iowa (population 7,257). Located halfway between the theory groups of Iowa State and Nebraska, the Cass County branch of the Iowa Western Community College hosts a theory seminar every couple of months. Pretty impressive that these theory groups, faculty, postdocs and students, drive two hours each just to join for a seminar and talk theory with each other. Quite an enjoyable day in rural America.

Sorry about the quality of the picture above. We didn't have a digital camera so I took the picture with my cell phone.

--
Posted by Lance to My Computational Complexity Web Log at 8/31/2004 09:28:36 PM

That fragile foundation is the P versus NP question. Much of current cryptography is based on the NP problem Factoring which would have an efficient algorithm if P were equal to NP. If P = NP than no other method of public-key cryptography would be possible either. However, as I have argued before, the loss in public-key crypto would be greatly offset by the gain in efficiency of nearly every other aspect of our lives. Encryption's doom would be society's gain.

Factoring is believed to be NP-complete and we could have the worst of all possible worlds with no cryptography and no new algorithms for problems we care about, one of five possibilities explored by Russell Impagliazzo.

Racing to dismantle is a bit of an overstatement. First of all we have nothing to worry about. As Juris Hartmanis once said, "We all know that P ≠ NP, we just don't know how to prove it." Remember too that all mathematics is based on unprovable assumptions about consistencies of logical theories. Doesn't seem to seriously bother anyone.

The article quotes Adleman as saying "From my perspective, we are no nearer to solving the problem now that we were when bell-bottom pants were cool." Adleman is an optimist; we do not even currently have a good approach to showing P ≠ NP. We are much further away from solving the problem than ever before.

--
Posted by Lance to My Computational Complexity Web Log at 9/2/2004 04:12:09 PM

In short the Electoral College works as follows: 535 electors are allocated to states as the sum of the senators (2 for each state) and representatives (proportional to population). In most states, each voter picks a single candidate and the candidate that wins the most votes receives all of the electoral votes for that state. The candidate winning the majority of the electoral votes becomes president. More details here.

In computer science terms (assuming two candidates), we have a weighted majority of majorites or a depth-2 neural net. It has some properties that you would want:

• Monotonicity: If a candidate wins the election and more people vote for him, he will still win.
• Fairness: Barring a tie, if all the votes were switched the other candidate would win.

The United States is just that, a collection of fifty states each with their own laws, cultures and economies, united under some common priciples. A simple majority would have the large populations centers overwhelm the rest of the country in choosing our leader. A majority of majorities would give some states far more power than their size would dictate. So a compromise was formed, a weighted majority of majorities to give small states some but not too much influence. The fact that this process does not always agree with majority is not a bug but a feature that preserves the balance between small and big states, rural and urban America. It also keeps balance between states of the same size, an lopsided vote in California would not overwhelm a closer vote in New York.

Some things I would change in the Electoral College: Electors should be required to vote for the candidate they represent; for each state we should have a ranked voting method instead of plurality takes all; the tie-breaking rules should be changed, now they give too much power to the small states.

The winner of the World Series in baseball is not the team that scores the most runs but the team that wins the most games, a majority of majorities and most people feel it gives a better indication of the better team. Why shouldn't elections deserve a system at least as sophisticated?

--
Posted by Lance to My Computational Complexity Web Log at 9/6/2004 11:40:02 AM

I've learned to expect this attitude from adults. Often when I talk to a non-academic about being a computer scientist I get responses like, "Should I get Windows or a Mac?", "I was thinking of setting up a wireless network." or "What do you think of that Google IPO?". Of course this is on top of them thinking I have a cushy academic job teaching three hours a week with summers off.

For my daughter I just went ahead and fixed her problem. I know when she becomes a teenager she'll run circles around me on the computer and will say "When I was a kid I thought you know everything about computers. What do you computer scientists do anyway?" Then we can talk.

--
Posted by Lance to My Computational Complexity Web Log at 9/8/2004 09:00:59 AM

We're working on a journal version of a paper where we did the research back when we were both in New Jersey (Dieter is now on the Wisconsin faculty). Dieter listed our current institutions on the paper. I think that we should list our institutional affiliation when we performed the research, or more precisely the place paying the salary at that time. I don't feel that strongly about the issue so I am letting Dieter have his way, especially since he did the vast majority of the writing. I did ask that we have footnotes explaining our affiliations at the time of the research. (As a side note, footnotes should also contain other support information such as grants, where one was physically located when the research was done if different and contact information, though these days one needs only know how to spell my name correctly when using Google).

So I'll open this up to my readers. Which affiliation should one use? Or are we just arguing over an issue that nobody really cares about?

--
Posted by Lance to My Computational Complexity Web Log at 9/9/2004 05:15:03 PM

In coding theory, one typically maps a string to a code such that with some small amount of error in the code one can still recover the original string. What if the amount of error is too much to give a unique decoding? In the 1950s Peter Elias suggested the idea of list decoding, coming up with a short list of possibilities one of which is correct.

Madhu Sudan showed that list decoding can be achieved in scenarios where one cannot do unique decoding.

In this paper Sudan gives a polynomial-time list-decoding algorithm that can deal with errors in the code beyond what regular codes can handle. Later Guruswami and Sudan give a polynomial-time algorithm that handles what is believed to be the best possible amount of error.

List-decodable codes have had applications to many areas including pseudo-random generators, extractors, hard-core predicates, probabilistically-checkable proofs and a neat result by Sivakumar on the implications of SAT being membership-comparable.

We've seen many other important papers in coding theory from computer scientists over the last decade. Besides the work on list decoding I should also mention Spielman's breakthrough result showing linear time encodable and decodable codes building on the initial work of using expander graphs for codes developed by Sipser and Spielman.

For much more on coding see the surveys by Sudan on List Decoding and Guruswami on Error-correcting codes and Expander Graphs.

--
Posted by Lance to My Computational Complexity Web Log at 9/12/2004 06:00:51 PM

Why does computer science follow the job market so closely? We don't see such swings in physics or history but such swings are common in engineering disciplines. Are undergraduate viewing computer science more as engineering than science? And why?

One theory I recently heard puts the blame on the Advanced Placement (AP) Computer Science Exam given to high school students. The reasoning goes as follows: The AP exam has a strong emphasis on the Java programming language and so high school teachers, teaching to the exam, focus most of their course on syntax and coding of Java. This gives the impression to students that computer science = programming.

I don't agree with this assessment. I looked at some sample CS AP tests. The tests, particularly the AB exam, requires some knowledge of data structures and simple algorithms. Nothing deep but enough that students should realize that computer science is more than just programming.

There was a surge of interest in computer science when I started college in the early 1980's (with the advent of personal computers) before an AP test in Computer Science even existed. Also I've heard of declines in enrollments outside the US where they don't use the AP tests.

But in the end we shouldn't be that worried about shifting enrollments. Advances in computer technology have helped drive computer science from a virtually non-existent discipline forty years ago to one that many universities now consider one of their most important departments. Better to have enrollments that swing up and down with the state of the computer industry than one that stagnates at the low end.

--
Posted by Lance to My Computational Complexity Web Log at 9/14/2004 06:42:47 AM

So what went wrong? We still use email today as the primary source of communication among computer scientists. But send a message today and I've learned to wait on average a couple of days to expect a response, if I get one at all.

Spam is the obvious culprit. Spam does clog our inboxes and even worse many of us don't carefully go through our spam folders and some legitimate mail gets unread. Spam has also made some computer scientists reluctant to share their email addresses online. But spam is not the only issue.

Email has become the communication of choice in the rest of the world as well. Besides messages from other scientists, I get email about my daughter's soccer team, announcements of upcoming concerts, warnings from the local police departments, a morning summary of the New York Times, financial information, utility bills and much more. All legitimate and usually useful email but it takes longer to work through it and slows down the time to respond to other scientists. Not to mention the many other web distractions such as news and weblogs (So stop reading this blog and respond to my emails. You know who you are.)

I can't rely on older technologies; since computer scientists expect email they check even less often their phone messages and postal mail. I can't rely on newer technology; computer scientists are surprisingly slow in adapting to new tools (like mail attachments) and it'll be years before instant messaging becomes common in the scientific community.

Oddly enough in our highly connected society it becomes harder and harder to get someones attention. So what am I doing? Slowly collecting the cell phone numbers of other computer scientists. Want mine? Send me an email.

--
Posted by Lance to My Computational Complexity Web Log at 9/15/2004 03:07:04 PM

The US Senate continues to work on the appropriation bills to set funding levels for next years US fiscal year that starts October 1. The CRA has a summary of the various bills affecting research funding in computer science (see also this note from AIP). Most worriesome (as I've mentioned before) is the funding for the VA-HUD bill that covers the NSF. The House committee would cut the budget by 2%. The CRA has an Advocacy Alert, still time to contact your senators.

--
Posted by Lance to My Computational Complexity Web Log at 9/17/2004 10:06:49 AM

At Banff in the Canadian Rockies we have the BIRS Workshop on Quantum Computation and Information Theory. This workshop will examine the properties of quantum information and tie it together with people working on quantum algorithms and complexity.

Meanwhile in Córdoba, Argentina on the edge of the Sierra Chica mountain is the Conference on Logic, Computability and Randomness 2004. Much of this conference focuses on random sets, not from a probability distribution but single sets that "look" random. Rater surprisingly, whether we define random sets by passing statistical tests, foiling betting strategies or using Kolmogorov complexity, these notions often lead to equivalent definitions of random.

While circumstances keep me in Chicago I say to the participants of both meetings: Enjoy the mountains and save some theorems for me.

--
Posted by Lance to My Computational Complexity Web Log at 9/19/2004 11:41:37 AM

Let's do an example. As I write this The New York Yankees have 94 wins, the Boston Red Sox have 60 losses. The easiest way to compute the magic number comes from working backwards from the definition. There are 162 games in a season so the Yankees magic number is 162+1-(94+60) = 9. Any combination of nine Yankees wins and Red Sox losses and the Yankees wins the American League East. The "+1" comes from the fact that in a tie the Yankees would still need to win a one-game playoff to win the division.

What can the magic number teach us about complexity? Consider the RIOT Baseball Project at Berkeley. Not satisfied with the magic number, the project computes the First Place Clinch Number as the "Number of additional games, if won, guarantees a first-place finish." To compute this number one has to look not only at the current standings but the schedule of remaining games between the teams.

My main issue of the clinch number relates to complexity. Not only is it more complicated to compute; to update the clinch number after a game sometimes requires recomputing the number from scratch. The magic number has a simple update function counting down like a rocket launch. Yankees win the magic number drops by one. Red Sox lose the magic number drops by one. If the Yankees beat the Red Sox, both events happen so the magic number drops by two. And once the magic number hits zero you pop the champagne. That's the beauty of the magic number.

--
Posted by Lance to My Computational Complexity Web Log at 9/21/2004 07:39:53 AM

The hardwood floors were covered in white canvas, and tables were set in a line stretching from the master bedroom to the kitchen, each feathered with precisely positioned name cards, whose placement had been agonized over for weeks. (Avra cannot sit next to Zosha, but should be near Yoske and Libby, but not if it means seating Libby near Anshel, or Anshel near Avra, or Avra anywhere near the centerpieces, because he's terribly allergic and will die. And by all means keep the Uprighther and Slouchers on opposite sides of the table.)

What makes scientists so liberal? Why doesn't a field like computer science draw from a wide political spectrum? Does this liberal attitude stifle real political debate in scientific departments or even worse discourage those with more conservative views from entering our field?

--
Posted by Lance to My Computational Complexity Web Log at 9/26/2004 08:36:55 AM

I think most computer scientists, even conservatives vote Democrat for one reason. Democrats fund the NSF, and the NSF gives us fat paychecks.

1. Carter, 7.9%
2. Reagan, 11.0%
3. Bush Sr., 10.6%
4. Clinton, 7.6%
5. Bush Jr., 9.1%

We will invest in the technologies of the future, from renewable energy to nanotechnology to biomedicine, and will work to make permanent the research and development tax credit. We will achieve universal access to broadband services, which could add $500 billion to our economy, generate 1.2 million jobs, and transform the way we learn and work. And we will put science ahead of ideology in research and policymaking.

America's economy is undergoing a fundamental transition from one based primarily on manufacturing to one based on innovation, services, and ideas. Two-thirds of America's economic growth in the 1990s resulted from the introduction of new technology and 60 percent of the new jobs of the 21st century require post-secondary education, yet only one-third of America's workforce has achieved that level.

In order to maintain America's global leadership, Republicans have provided unprecedented support for federal research and development to help spur innovation. Federal R&D funding is up 44 percent from 2001 to $132 billion in 2005, which includes a 26 percent increase in support for basic research. The President has doubled the budget for the National Institutes of Health and increased the National Science Foundation budget by 30 percent. President Bush and the Republican Party also support making the R&D tax credit permanent.

The rapid pace of technological development demands that we remain on the leading edge of innovation and science. Republicans are committed to providing the investment and incentives needed to foster next generation technologies. The 21st Century Nanotechnology Research and Development Act, passed by a Republican Congress and signed by President Bush, increased funding for nanotechnology research. In addition, the President has dedicated $1.7 billion over five years to develop hydrogen fuel cells and related next-generation energy technologies. The President's support for NASA and vision for space exploration will also enhance scientific development and technological breakthroughs.

A researcher at the beginning of his career has to please others. In order to receive a Ph.D., get a job and eventually tenure, he has to not only produce good research but research of value to others. The researcher might think that once he gets tenure he can do the research he wants, but by that time he has become so specialized it is impossible to change direction.

When I started in grad school in the mid-80's, I could follow nearly every talk at the major theory conferences, STOC and FOCS, though I would not have followed any computer science talk which might have been true 10-15 years earlier. These days I can understand the importance of the main results of maybe half of the talks and have actual interest in only a small fraction of these. The growth of specialty conferences such as Complexity, SODA (algorithms), SoCG (Computational Geometry), Crypto, RANDOM/APPROX, COLT (Learning Theory), LICS (Logic in CS), QIP (Quantum) and so on have only increased this divide. We get less and less crossbreeding between these subfields of theory.

On the other hand, some researchers still can and do (with some effort) change research areas in theory and general computer science even after tenure. But in 15 years will we look like economics where a late change in field is difficult to impossible and soon after that like mathematics where it often takes years of graduate school just to understand the major open questions in an area.

--
Posted by Lance to My Computational Complexity Web Log at 9/30/2004 09:47:55 AM

The econ theory seminar took place in a medium-size conference room with a long table. Graduate students sat in chairs along the walls. The speaker was at one end of the table and econ professors, usually including multiple Nobel prize winners, around the rest of the table. A copy of the paper was sent with the talk announcement and almost from the first slide the faculty aggressively attacked the speaker with questions about the validity of the model or the importance of the results. (Remember this was the theory seminar, imagine the questions at the political economics seminar). At the end of the seminar time, the talk ended and everyone left the room. No applause.

I don't recommend that we follow this model in theoretical computer science. However we usually go to the other extreme and (outside of crypto) rarely ask negative questions in a seminar. Typically the only negative feedback we get in our field is from anonymous referees and reviewers. If we were forced to defend our research in an interactive setting, we would establish a better understanding of the importance of the models and results of our own research.

--
Posted by Lance to My Computational Complexity Web Log at 10/3/2004 03:27:16 PM

The first will be held at the IBM Almaden Research Center on Monday, October 25, 2004.

The second will be held in conjunction with STOC '05 in Baltimore on May 21-22, 2005.

Please join the community in honoring the memory of one of the great complexity theorists.

--
Posted by Lance to My Computational Complexity Web Log at 10/5/2004 06:32:41 AM