Annie (age 9): How many computer scientists are there in the world?
Me (Wildly Guessing): About 100,000.
Molly (age 6): I know there are at least two. You and our computer
teacher at school. Someone asked him if he was a scientist and he
said, "yes, I am a computer scientist."
I don't think Molly's computer teacher tried to mislead; he just did a play on words. But it was enough to fool a six-year old and I suspect many adults as well. Maybe we need a new name for people in our field.
We saw The Polar Express on an IMAX screen in 3-D. Since computers stored the entire movie, converting the film to 3-D could be an automated process. I predicted to my unbelieving children that when they grow up they will not be able to distinguish between computer generated film and those filmed live. Perhaps all movies then will be stored in some specific format like papers in PDF today that could be easily converted and optimized to whatever display device a person has.
Unless you have small children, I would recommend The Incredibles over The Polar Express. Technology does not win over substance. But I have seen the future and it is cool.
All this searching power leads to the mistaken belief that the best way to find anything is by a direct search. For example many people look for a paper by Googling on the name of the paper. Usually that does lead to a version of the paper to download. But Google searches the deep recesses of the internet and often returns old versions of papers, even technical reports well after conference and journal versions have appeared. Google says "Don't be evil"; I say "Don't be lazy." If you have a reference to a paper in a particular conference or journal, search for that conference or journal and find the paper there if you have access. Or use a site like DBLP. Otherwise look on the author's web pages; good authors will keep versions of their papers up to date. If all this fails you can fall back on Googling the name of the paper. Working off the newest version of the paper will save you far more than the extra fifteen seconds you'll spend searching for it.
In layman's terms, suppose you have a big maze, far too big to fit into your computer's memory. You can only ask questions of the form: given two locations A and B, are A and B directly connected? Reingold's result shows that you can determine whether there is a path from the entrance to the exit using only an amount of memory equivalent to storing a constant number of maze locations.
In the second half of the 80's we generally still did not distribute papers electronically and the world wide web remained several years away. Nearly everyone in theory subscribed the the Theorynet mailing list (not so true today) and the call for papers were emailed to this list as well as sent out to all SIGACT members by postal mail. To submit to a conference we had to make ten copies of a paper and physically send them to the program committee chair who then sorted the papers into ten stacks and sent each stack to each program committee members. A few months later the program committee would meet and choose the papers for the conference sending out accept/reject letters through postal mail. Since MIT always had one or more PC members on the faculty we found out about our papers from them well before we got the official word.
Initially the STOC and FOCS PCs did not take deadlines seriously. For some reason about 1987 they decided to strictly enforce the deadline first by postmark and then by receipt. Federal Express made considerable money from us theorists and I can still tell you which Fed Ex offices in Boston and Chicago remained open the latest. One year an MIT faculty memeber hired a same-day service to send the papers to the PC chair giving us at MIT an extra night to work on our papers. Not many of us showed up for classes the next day.
Electronic submissions, starting in the early 90's, leveled the playing field and made the process slightly more sane. The STOC call still has the line
Authors who cannot submit electronically must send 21 printed copies (double-sided preferred) of an extended abstract, together with a cover letter, to:When I served as the Complexity PC chair in 1999 exactly one person sent me their submission by Federal Express. "Am I going to have to send a copy of this paper to each of my PC members?" I thought. Instead I emailed the author and luckily he sent me a postscript file and I could manage the PC electronically. We have since removed the non-electronic submission instructions from the Complexity call.
Alice and Bob have subsets of {1,…,n}. How much communication do Alice and Bob need to determine if their subsets have a empty intersection. In classical communication complexity even with probabilistic players, Alice and Bob need Ω(n) bits of communication to solve this Set Disjointness Problem.
What if we allow communication with quantum bits? A clever protocol by Buhrman, Cleve and Wigderson based on Grover's quantum search algorithm shows how Alice and Bob can solve Set Disjointness communicating with (up to log factors) n1/2 quantum bits. Could Alice and Bob do better? The best known lower bounds were about O(log n) until Razborov showed the Buhrman-Cleve-Wigderson protocol was essentially optimal.
In another important paper in quantum lower bounds, Andris Ambainis developed the hybrid method for proving lower bounds on quantum query complexity. This method gave researchers a new tool in proving stronger and sometimes tight bounds in the number of queries a quantum algorithm needs to an input to solve a problem like inverting a permutation. Ambainis' work formed the basis for many other papers applying the techniques and improving them including work recently presented at Dagstuhl.
A review of the usual referee process: The editor-in-chief of a journal receives a submission and assigns a member of the editorial board to act as editor for that paper. The editor will contact potential referees and ask them to review the paper. The referees read the paper and write a report on whether to recommend the paper for publication and give suggested changes. They send this report to the editor who relays this information to the authors without revealing the identities of the referees. The authors will comment on the referee reports and revise the paper. The paper often goes back to the referees and the process repeats until the editor is happy with the paper or decides the paper is not worthy of the journal. The editor then sends his recommendation back to the editor-in-chief.
An argument for posting the reports goes as follows: If we make the reports public (though still anonymous) referees will feel a greater responsibility to make their report thorough and accurate.
The process of refereeing requires considerable back and forth conversation between the three parties: the authors, the editor and the referees. Posting the original reports will give a misleading view of the process and will cause referees to act far too cautiously about pointing out problems in a paper.
We have an editor responsible for making sure that he has enough quality reports to properly make a decision about publication. Using the public as an editor will often lead to some very difficult and messy situations.
Keep in mind the distinction between the referee process and reviews of published papers. We should encourage publicly available reviews of research papers whether in Mathematical Reviews or informal settings like weblogs. These reviews help us find the gems among the sea of research papers out there.
Memo to the future 2008 STOC PC Chair: Don't even think of scheduling the STOC deadline immediately following the elections again. There is only so much stress one can take in a week.
With the great growth in theory the STOC conference can now only accept a small number of papers in computational complexity theory. For the same reasons we have seen many strong papers appear in Complexity over the past several years from a quite broad range of complexity topics. Don't take my word for it and look at our last three conferences.
With your help we can add even more strength to the Complexity conference and continue to make it the primary venue for exposition of results in computational complexity. So submit your papers and I look forward to seeing you in San Jose.
And after you submit your paper to either conference, I highly recommend also sending the paper to ECCC. You will get quick publication and more exposure than any single conference.
I'm Lance Fortnow and I approve this message.
With the US elections on Tuesday and politics on everyone's mind, let's open the comments for anyone who has anything they want to say about the presidential race. Get it off your chest. I only ask you to be civil. And don't forget to vote.
In our publish or perish society, authoring papers helps you succeed, in getting hired, promoted and receiving grants and awards. So choosing who is an author of a paper, particularly important papers, can be an important and sometimes messy decision complicated by the fact that the authors have to do the choosing.
An author should have made significant contributions to a paper. But how do we define significant? A person who produces key ideas in the proof of a main result certainly becomes an author. A person who simply writes up the proof should not be. But what about the person who works out the messy but straightforward details in a proof? What about the person who poses the questions but has no role in the proof? Tricky situations that one needs to handle on a case-by-case basis.
An advisor should hold him or herself to a higher standard. A good advisor guides the research for a student and should not become a co-author unless the advisor had made the majority of the important ideas in the proofs. Likewise we hold students to a slightly lower standard to get them involved in research and exposition of their work.
Computer scientists tend to add co-authors generously. While seemingly nice, this makes it difficult to judge the role authors have played in a paper, and sometimes makes who you know or where you are more important than what you know.
Since computer science takes its conferences more seriously than the journals and most conferences have hard deadlines, we have become a deadline-driven field. Most authors submit their papers on the deadline day, if not in the last hour or two. Papers get written to meet a deadline which has both good and bad aspects: good in that papers get written and bad in that they get written quickly and often incompletely.
Sometimes conference organizers see a lack of submissions (forgeting that most papers come on deadline day) and extend the deadline by a few days or a week. I've often heard people complain about losing their weekends if a deadline moves from Friday to Monday. Why? You could still submit on Friday. People feel their papers are never complete and they need to keep fixing it up until the last possible second even though these last minute changes will not likely affect acceptance.
One person I knew once turned down an opportunity to attend a workshop because of a grant deadline on the same week. This was six months beforehand. A little planning is all that's needed to submit the grant one week early but some in our field cannot pull this off even months ahead of time.
Remember that deadlines are upper bounds, no shame in submitting early. And it's not the end of the world if you miss a deadline; there's always another conference with another deadline right around the corner.
I prefer to use the Martian rule. Suppose we find a Martian civilization at about the same level of scientific progress that we have. If they have a concept the same or similar to one of ours than that concept would be natural, having developed through multiple independent sources.
Of course we don't have a Martian civilization to compare ourselves with so we have to use our imagination. I firmly believe the Martians would have developed the P versus NP question (or something very similar, assuming they haven't already solved it) making the question very natural. On the other hand I suspect the Martians might not have developed a class like LWPP. Other classes like UP are less clear, I guess it depends whether the Martians like their solutions unique.
Applying the Martian rule to Gasarch's post, WS1S is probably more natural than regular languages without squaring that equal Σ*. At least my Martians would say that.
Computation Complexity and Computational Learning share many aspects and goals. We both analyze and compare different models of computation either to understand what they can compute or how to find the appropriate model to fit some data. No surprise that many of the tools developed in one area have use in the other. This month's paper exemplifies the connection; it uses tools in complexity to get a nice learning theory result which in turn has very nice implications in complexity theory.
The main result shows how to learn circuits probabilistically with equivalence queries and an NP oracle. An equivalence query given a circuit C trying to learn a language L, either says C is correct or gives an input where it fails. The proof uses a clever divide and conquer argument built upon Jerrum, Valiant and Vazirani's technique for random sampling with an NP oracle.
Kobler and Watanabe observe that if SAT has small circuits we can answer equivalence queries to SAT with an NP oracle. Applying Bshouty et. al. they show that if SAT has polynomial-size circuits than the polynomial-time hierarchy collapses to ZPPNP.
Sengupta noticed that old results give a consequence of PH in S2p if SAT has small circuits. This strengthens Kobler and Watanabe because of Jin-Yi Cai's result showing that S2p is contained in ZPPNP. Cai's paper uses many techniques similar to Bshouty et. al. Shaltiel and Umans have a recent result giving weaker assumptions for derandomizing S2p by derandomizing random sampling.
If SAT does not small circuits, the Bshouty et. al. algorithm produces a small set of inputs that give a co-NP proof of this fact. Pavan, Sengupta and myself applied this fact to the two queries problem.
The Red Sox didn't win the series that year and failed to return until this year. After an amazing comeback against their rivals, the New York Yankees, the Red Sox will host the first game of the World Series on Saturday against the St. Louis Cardinals.
By far baseball is the favorite team sport among American computer scientists (at least of those that care about sports at all). Why? Mabye because it's a discrete game with a small state space. At Fenway Park (Boston's home field) they use lights to give the number of ball, strikes and outs in unary notation. The game has many nice mathematical properties and not just the myriad of statistics. For example, it is a theorem of baseball that at any point in a half inning the number of batters is equal to the sum of the number of outs, the number of runs scored and the number of men on base. Proof by induction.
The real reasons I love baseball are less tangible. Both a team sport and a one-on-one contest between pitcher and batter. A strategic game dealing with balancing probabilities. Suspense on every pitch. And much more.
By far the plurality of baseball fans in our field seem to root for the Red Sox. Probably because most of us spent at least part of our academic career in the Boston area and Boston takes its baseball far more seriously than any other city. In full disclosure, my favorite team is the Chicago White Sox but I root for the Red Sox in their absence.
Nothing beats attending baseball game live, especially in Fenway. Alas I never managed to attend a world series game though I've come very close.
October 14, 1992: The Pittsburgh Pirates won the National League East and the World Series was scheduled to open during FOCS in Pittsburgh. I wrote for and got tickets to the first game if Pittsburgh made the series. In the NLCS Atlanta scored three runs in the bottom of the ninth of game 7, meaning Atlanta and not Pittsburg would host the series. When Cabrera hit the single scoring those final two runs, I sat staring at the TV and cried.
Why is it hard for us to explain to the layperson what we do? The following true story is telling. I will label the characters MOM and BILL.
MOM: What kind of thing do you work on?
BILL: (thinking: got to give an easy example)
Lets say you have n, er 1000 numbers.
You want to find the — (cut off)
MOM: Where did they come from?
BILL: Oh. Lets say you have 50 numbers, the populations of all of the states of America, and you want to find — (cut off)
MOM: Did you include the District of Columbia?
BILL: No.
MOM: Why not?
BILL: Because its not a state. But for the example it doesn't matter because — (cut off)
MOM: But they should be a state. They have been oppressed to long and if they had their own state then — (cut off)
BILL: But none of that is relevant to the problem of finding the Max of a set of numbers.
MOM: But the problem of Statehood for DC is a more important problem.
BILL: Okay, lets say you have 51 numbers, the populations of the 50 states and the District of Columbia.
MOM: What about Guam?
BILL: I should have majored in Government and Politics…
To the person on the street the very definition of a problem is … problematic. Abstraction that we do without blinking an eye requires a conceptual leap that is hard or at least unfamiliar to most people.
Even people IN computer science may have a hard time understand what we are talking about. Here is another real life story between two characters who I will call BILL and DARLING. DARLING has a Masters Degree in computer Science with an emphasis on Software Engineering.
DARLING: Bill, can you give me an example of a set that is provably NOT in P.
BILL: Well, I could say HALT but you want a computable set, right?
DARLING: Right.
BILL: And I could say that I could construct such sets by diagonalization, but you want a natural set, right?
DARLING: Right.
BILL: And I could say that the set of true statements in the language WS1S, but you want a natural set.
DARLING: What is WS1S?
BILL: Weak Monadic Second order with one successor, but I think you agree that if you don't know what it is then it's not natural.
DARLING: Right. So, is there some set that is natural and decidable that is provably not in P?
BILL: AH, yes, the set of regular expressions with squaring that equal Σ* is EXPSPACE complete and hence provably not in P.
DARLING: Why is that problem natural?
BILL: Good Question! A problem is natural if it was being worked on before someone classified it.
DARLING: Okay. What is the first paper this problem appeared in?
BILL: It was in THE EQUIVALENCE PROBLEM FOR REGULAR EXPRESSIONS WITH SQUARING REQUIRES EXPONENTIAL SPACE by Meyer and Stockmeyer, From FOCS 1972. Oh. I guess that proves that its NOT natural.
This story raise the question—what is natural? Do we need that someone worked on a problem beforehand to make it natural? Is it good enough that they should have worked on it? Or that they could have? Logic has the same situation with the Paris-Harrington results of a result from Ramsey Theory that is not in Peano Arithmetic, but the first time it was proven was in the same paper that proved it was not provable in PA.
Incidentally, there are more natural problems that are not in P. Some games on n by n boards are EXPSPACE or EXPTIME complete and hence not in P. Would have been a better answer, though it would not have made as good a story.
To answer one of Lance's previous posts, the Internet is definitely harming conferences: most everyone who stayed up until 5 AM to watch the Red Sox beat the Yankees in 14 innings on MLB.TV has not made it to James Lee's talk at 8:30 AM on embeddings (in fact I think I'm the only one who did make it here). Krauthgamer, Lee, Mendel, and Naor presented a powerful new method for constructing embeddings of finite metric spaces called measured descent which, among other things, implies optimal volume-respecting embeddings (in the sense of Feige).
I checked the registration numbers and indeed only 172 people have officially registered for the conference—that's 100 less than the registration at STOC in Chicago.
Yesterday I mentioned the winners of the best paper award. I should also mention the best student paper award winners: Lap Chi Lau's An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem shared the prize with Marcin Mucha and Piotr Sankowski's Maximum Matchings via Gaussian Elimination. Lau's paper gives the first constant factor approximation to the problem of finding a large collection of edge-disjoint trees that connect an undirected multigraph. Mucha and Sankowski give a nice method for finding maximum matchings in general graphs in time O(nω) where ω is the matrix multiplication exponent. Lovász showed how to test for a matching in a graph using matrix multiplication, and Mucha and Sankowski extend this and actually recover the matching.
Valiant's talk on Holographic Algorithms was well attended: he described a new, quantum-inspired method for constructing polynomial-time algorithms for certain counting problems. The algorithms are classical (no quantum required) and give the first efficient solutions for problems such as PL-Node-Bipartition: find the cardinality of a smallest subset of vertices V' of a max-degree 3, planar graph such that deletion of V' (and its incident edges) causes the graph to become bipartite. At the end he gave a simple criterion for proving P = P#P via these techniques!
Rome is the host city for this year's FOCS conference. While everyone enjoys visiting one of the world's great capitals, attendance at the sessions can occasionally suffer, and the sessions this year do seem noticeably smaller. Another explanation could be the the high cost of traveling to and staying in Rome. On the plus side, I get to see many European theorists of whom I had known in name only.
For those who did make the trek to the southern tip of the Villa Borghese, the first day featured the presentation of the two results which won best paper: Subhash Khot's Hardness for Approximating the Shortest Vector in Lattices and Applebaum, Ishai, and Kushilevitz's Cryptography in NC0. Subhash was an author of two other impressive hardness results in the same session: Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique (the title is self-explanatory) and Optimal Inapproximability Results for Max-Cut and Other 2-variable CSPs? (with Kindler, Mossel, and O'Donnell) which gives evidence that the Max-Cut approximation algorithm of Goemans-Williamson is the best possible.
The cryptography session featured the above Cryptography in NC0 paper which Lance mentioned in an earlier post as well as an intriguing result due to Salil Vadhan, An Unconditional Study of Computational Zero Knowledge showing how to establish important properties of computational zero knowledge proofs without assuming the existence of a one-way function.
The controversial topic of what to do with the special issue of FOCS continued at last night's business meeting. It appears as though Elsevier will lose another opportunity to publish a special issue of STOC/FOCS, as a vote last night indicated a strong desire to give SICOMP the responsibility instead (a similar thing occurred at STOC this year).
We also saw a series of presentations by Andris Ambainis, Robert Špalek and Mario Szegedy. Ambainis described his improved method for showing lower bounds for quantum algorithms that provably beats the degree method. Špalek talked about his work with Szegedy showing that Ambainis techniques as well as different tools developed by Zhang, Laplante and Magniez, and Barnum, Saks and Szegedy all gave the same bounds. Szegedy, in his presentation, called this measure the div complexity and showed that the size of a Boolean formula computing a function f is at least the square of the div complexity of f.
Although Dagstuhl has expanded, rooms not only have phones but WiFi throughout. We can answer email, read news, write weblog posts (as I am doing now) from the comfort of our own isolated desks. We're watching baseball games and the debate over the internet. But worse than being connected, the rest of the world knows we're connected. I find myself having to take time to fix problem sets for my class and deal with departmental issues as do many of my other colleagues here.
The internet has greatly helped science by bringing us closer together but also prevents us from being disconnected losing many of the advantages of these workshops. A sign here proclaims "Are you here for computer networking or human networking?" Something to remember next time you go to a conference.
A group of German software engineering professors share Dagstuhl with us this week. They are meeting to discuss future directions of German software engineering research and to find ways to increase student enrollment. The drop in students desiring a computer science degree is not just an American phenomenon.
The Grace Hopper Celebration of Women in Computing was held in Chicago on October 6-9. This was the fifth such conference, since its inception in 1994. This year there were over 800 attendees from all over the country.
This conference is a forum for discussion of issues faced by women and a showcase for achievements of women in the fields of computing and technology. There were a number of talks on social issues, some technical presentations by young investigators, and a few invited technical talks. There were also a number of social and networking events hosted by IBM, Microsoft, Google and others.
Among the invited talks, there were three I particularly enjoyed.
Jessica Hodgins of CMU talked about connections between ideas in robotics and computer graphics and animation, especially simulation of human movements.
Cynthia Dwork of Microsoft Research spoke about the problem of publishing (transformed) data from public databases (such as census data) so as to maintain a balance between the utility of the published information and the protection of the privacy of individuals represented by the data. Her approach to privacy is influenced by ideas from cryptography.
Daniela Rus of MIT spoke about self-reconfiguring robots. These robots are distributed systems, consisting of a number of identical modules which can dynamically adapt the way that they are connected to each other to best fit the task at hand.
She had no problem solving questions like: Beginning and ending at the entrance, describe the shortest route you can take that will allow you to see 4 different kinds of animals.
"You're doing computer science," I said.
"I don't see any computers," she responded.
"Computer science is problem solving like finding the shortest path."
"Then computer science is pretty easy."
"OK, is there a way to visit every animal exactly once?"
She found this question much more challenging.
The names get their meaning from a structure you still see in many other countries (Germany is a good example). Here you have research groups, where a lead professor has nearly complete control of hiring and the budget. The equivalents of assistant and associate reflect the temporary and permanent faculty members of those groups.
How does this affect graduate studies? In Germany a grad student joins a group and works within that group. In the United States a student joins a department usually without a specific advisor in mind and often not initially committing to a specific subfield of computer science.
So to those who send me and other American computer scientists requests to join our groups, the US system doesn't work that way. Instead go to the departmental web page and follow the appropriate links to find information on how to apply to that department. If you have a specific researcher that you want to work with, use the personal statement to say this and your reasons for it.
Trust me, we read the applications carefully and choose Ph.D. candidates as best as we can. It just doesn't help to send personal requests, I just point to our web page and trash the email.
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.
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.
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.Looking at economics can give us a glimpse into the near future of computer science as a discipline. Though economics as a field has been around for a very long time, only since the 1950's did economics develop as a rigorous mathematical discipline. This gives economics about a 15-year head start on computer science.
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.
I think most computer scientists, even conservatives vote Democrat for one reason. Democrats fund the NSF, and the NSF gives us fat paychecks.From discussion I have with other computer scientists, I don't find science funding a major factor in their voting decisions. On top of that the preface doesn't hold water. I went and computed the average yearly increase in the NSF budget during the tenures of the last several presidents.
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.The Republican Platform takes two pages to give the same ideas (except for that last sentence). Here is the section on Research and Development.
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 short the parties do not differ much on a future research investment. Both platforms also push science education. The Republicans have had a better historical record of science funding but Bush has come under fire for ignoring science in policy making. Better not to worry about science and use other factors in your choice of president.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.
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?
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 Uprighthers and Slouchers on opposite sides of the table.)
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.
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.
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 worrisome (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.
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.
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.
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.
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?
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 knew everything about computers. What do you computer scientists do anyway?" Then we can talk.
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 not 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.
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.
Don't let "NC0" 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 NC0 and so if one-way function and PRGs exist in the larger class than slightly weaker versions exist in NC0 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 NC0." Now we know why.
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.
Varsha Dani emailed a note about an article describing an Amazon tribe with no concept of numbers. I guess they don't send anyone to the olympics where numbers seem king.
Watching gymnastics I am always amazed how winning seems to depend on sticking the landing. After a rather complicated and lenghty routine why should whether your feet move at the end be the difference between Gold and Bronze? The answer lies in the ε; the best gymnasts can uniformly hit the major elements of their routines but consistently sticking the landing is much more difficult and that what makes or breaks the result.
We see the ε issue in many scenarios, most notably the 2000 US presidential election where confusing ballots in one county created a huge controversy. The budget of the NEC Research Institute is miniscule compared to the revenue of NEC corporate. A couple of years ago NEC eeked out a profit about the same size of the cost of the Institute and all of a sudden the NEC Research Institute looked very expensive to NEC. In another example, consider the relatively large power a small party can have in a coalition in a parlimentary system.
The best way to avoid the ε problem is by decisive victories. Solidly beat your opponent in an election or have enough parlimentary seats so you don't need small partners. Make enough of a profit so that a cheap research lab stays that way. One only gets the ε problem when one has a statistical tie and then the small things take on great importance.
In gymnastics one would want a system where a greatly superior gymnast can score high enough that a small jump on the landing won't make a difference. But the current system doesn't allow that; with a top score of 10 the world's best gymnasts all get well over nine, making it impossible to put enough of a gap between a the best and the rest.
At the end of most technical talks is the obligatory "Conclusions and Open Problems" slide, usually the least thought out moment of the presentation, which consists of a brief summary of the talk and a list of the most obvious (difficult) open problems. For the last few years, COLT has glorified the open problems section and allocates about an hour of time for a presentation of open problems. The open problems themselves must be submitted months beforehand and are refereed (how rigorously is anyone's guess); accepted problems appear in the proceedings. A list of this year's open problems can be found on the COLT 2004 program schedule -- the session was held on Friday evening.
Are there any other computer science conferences where open problems are refereed and given their own slot in the program? It always seems to work out well at COLT, and while I am aware of open problems being presented at rump sessions at various conferences, I don't know of other venues which require advance submission of problems.
With that, gentle reader, I return you to Lance's wise embrace. If I ever get to guest blog again, I will reveal what's hidden in Lance's "Private" directory here on fortnow.com. Some "lost" theorems apparently-- here's an aborted post entitled "Soon I will be famous: a simple proof that NP = coNP" -- and here's another unfinished note with some not so nice things to say about Algorithms. And what's this? A love letter to Jessica Simpson? Oh if only we had more time.
Many top notch researchers come to visit the Toyota Technological Insitute here in Chicago. This fall alone Lenore Blum, Bruno Codenotti, Prahladh Harsha, and Jaikumar Radhakrishnan will be in residence along with TTI's regular faculty.
Yishay Mansour visited in August for about two weeks, and I had the chance to ask him about his work along with N. Linial and N. Nisan which pioneered the use of discrete Fourier analysis in computational learning theory. The paper Constant Depth Circuits, Fourier Transform, and Learnability gives a quasi-polynomial time learning algorithm for constant depth circuits with respect to the uniform distribution. More importantly, it pointed out a connection between the Fourier concentration of a Boolean function and its learnability.
If f is a Boolean function, we could imagine writing f as a multilinear polynomial in n variables mapping {-1,1}^n to {-1,1}. Every Boolean function can be written as such a polynomial whose total degree is at most n. Each coefficient of this polynomial measures the correlation of f with that monomial. These are the Fourier coefficients of f. Linial, Mansour, and Nisan showed that if the sum of the squares of the coefficients of monomials of degree d and larger is small, then there is an n^{O(d)} time algorithm for learning f with respect to the uniform distribution-- roughly speaking it is sufficient to estimate the coefficients of only the low degree monomials and output this polynomial.
What does any of this have to do with constant depth circuits? They also proved that for any circuit of depth d, the sum of the squares of the coefficients on the terms of degree (log n)^d and higher decays rapidly. From the above paragraph this gives us a quasi-polynomial time algorithm. For a rough intuition as to why this is true, consider one implication of Hastad's Switching Lemma, namely that parity cannot even be approximated by constant depth circuits. Thus every coefficient of a sufficiently large monomial (each monomial is a parity function) must be small.
As it turns out, according to Yishay, the work stemmed from an effort to prove circuit lower bounds, rather than a plan to develop new learning algorithms. The authors were inspired by Kahn, Kalai, and Linial's work on the influence of variables on Boolean functions and thought that discrete Fourier analysis might be the right tool for studying circuits. They happened to be correct-- in an unexpected way.
A few weeks ago Lance reported on the events from a complexity workshop he was attending at the Banff International Research Station, an institute similar to the International Space Station except that it's in Canada rather than outer space.
What Lance didn't mention was that at the exact same time, some important computer science conferences were taking place just down the street at the Banff Park Lodge. I was participating in the 17th annual Conference on Learning Theory (COLT) which was co-located with the International Conference on Machine Learning (ICML) and the Conference on Uncertainty in Artificial Intelligence (UAI).
Back when COLT stood for Computational Learning Theory (circa 1988-2002), the conference was known for focusing on the computational complexity of machine learning. Nowadays the conference still operates from a theoretical perspective, but, as the Conference on Learning Theory, the program covers everything from game theory and economics to kernel methods in addition to traditional PAC style results.
A PAC style result that appeared in COLT 2004 which may be of interest to the readers of this web log is Polynomial-Time Prediction Strategy with Almost Optimal Mistake Probability by Nader Bshouty. His paper solves a problem in the online learning setting. In this setting, an unknown function f is chosen from some fixed concept class and at time t a learner is presented with an input x chosen according to some distribution D.
The goal of the learner is to run in time polynomial in log t (and all of the other relevant parameters) and predict the value of f(x) with mistake probability O(1/t) (Haussler, Littlestone, and Warmuth proved that this mistake probability is optimal). Bshouty shows that if the concept class is PAC learnable, then there exists an online learning algorithm which runs in time polynomial in log t and achieves mistake probability O(log t/ t). His algorithm has an exponential improvement in running time as previous solutions ran in time polynomial in t. The algorithm works by iteratively creating a branching program based on hypotheses considered at previous time steps. A boosting-type procedure dictates which branch to take for any new input.
In the spirit of being controversial (Lance asked me to be controversial), I could discuss the pros and cons of the change from Computational Learning Theory to Conference on Learning Theory (as a concrete example of differences in the community, about half the participants at the COLT business meeting wanted to see COLT co-located with STOC in 2006-- University of Washington folks make your move-- and the others wanted to co-locate with ICML). I'll leave that, however, for my faithful readers to debate. I will point out that it's hard to argue with the increase in attendance at COLT over the last few years.
Considering the topic of yesterday's post, if there were a list of favorite theorems in computational learning theory, a field which makes only brief appearances here on the weblog despite its many connections to computational complexity, Jeff Jackson's algorithm for learning DNF formulas would certainly be on it.
A DNF formula is a Boolean formula written as an OR of ANDs (e.g. x_1 and x_2 OR x_3 and x_5). The size of a DNF formula is equal to the number of terms or ANDs. The problem of PAC learning an unknown polynomial-size (in n, the number of variables) DNF formula with respect to an arbitrary distribution remains one of the most notorious open problems in the field (for background on PAC learning see this post or Kearns and Vazirani's excellent book An Introduction to Computational Learning Theory).
In fact, even if we restrict the underlying distribution on examples to be the uniform distribution, the fastest algorithm for learning DNF formulas runs in quasi-polynomial time (a result due to K. Verbeurgt-- the main idea being that only terms of logarithimic length have a chance at being satisfied, so longer terms can be ignored).
If, however, we allow the learner to make queries to the unknown DNF formula, i.e. if the learner can choose any input x and ask for the value of the DNF formula evaluated on x, then the learner can succeed in polynomial-time.
The solution, due to Jeff Jackson in 1994, shows how to learn polynomial-size DNF formulas with respect to the uniform distribution in polynomial-time (again assuming the learner has query access to the unknown DNF). His algorithm, which he has called the Harmonic Sieve due to its use of Fourier analysis, builds on work due to Blum, Furst, Jackson, Kearns, Mansour, and Rudich (``Weakly Learning DNF and Characterizing Statistical Query Learning Using Fourier Analysis'') which showed that for any DNF formula with s terms, there exists a parity function which agrees with the DNF formula on roughly a 1/2 +1/s fraction of inputs.
The next step of the algorithm involves a novel application of Boosting algorithms (see this post for more on Boosting) for combining these parity functions to obtain an accurate hypothesis. The output of the Harmonic Sieve is not a DNF formula but a threshold of parity functions.
The Harmonic Sieve is one of the rare examples in computational learning theory of a polynomial-time algorithm for an expressive concept class. It is natural to ask whether the queries are essential for the algorithm. Unfortunately it seems like the answer is yes-- we do not know how to learn decision trees or even juntas (both strictly weaker concept classes than DNF formulas) in polynomial-time with respect to the uniform distribution unless the learner has query access to the unknown function. Removing the dependence on queries would be a real breakthrough.
By the way, the interface on blogger.com is worse than I ever could have imagined. Apologies in advance for formatting errors.
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 r1 and r2 and Merlin sends y1 and y2 and Arthur accepts if A(r1,y1) AND A(r2,y2). The highest possible acceptance probability will be p2.
Now consider the MIP model with two Merlins M1 and M2 who cannot communicate with each other. Arthur sends u and v to M1 and M2 respectively who respond with y and z. Arthur accepts based on some function A(u,v,y,z). Once again M1 and M2 try to achieve the highest possible acceptance probability p. Now we run the game twice in parallel, Arthur sending u1 and u2 to M1 and v1 and v2 to M2 receiving y1 and y2 from M1 and z1 and z2 from M2 and accepting if A(u1,v1,y1,z1) AND A(u2,v2,y2,z2).
One might assume that the best the provers can achieve is p2 (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.
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.
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.
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.
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.
Vinod Variyam recently observed that the class PP which is not known to contain S2p also cannot have nk-size circuits. Here is his proof: If PP has nk-size circuits then PP is in P/poly which implies the polynomial-time hierarchy and in particular Σ2p is in MA which is in PP which has nk-size circuits contradicting Kannan.
Read Variyam's paper for details and references.
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.Indeed Stockmeyer developed many of the important early concepts in complexity such as alternation and the polynomial-time hierarchy, concepts that have laid the foundation for many important works in computational complexity. He had a number of great results throughout his career in complexity and nearly all areas of theoretical computer science. Our community has lost one of its giants.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.
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.
