Simplex works well in practice but it remains open whether simplex runs in polynomial time for worst-case inputs (though see this paper by Spielman and Tang). Dantzig's death comes just two weeks after the passing of Leonid Khachiyan who had the first provably efficient algorithm for linear programming three decades after Dantzig developed the simplex method. Khachiyan's ellipsoid algorithm is not at all practical as compared with the simplex method.

--
Posted by Lance to Computational Complexity at 5/17/2005 07:32:00 PM

That first movie remains my favorite of the Star Wars series to date, with the movie's single tight finale and the "Force" more mysterious than real. Special effects in movies have gotten so good that they can no longer wow you like they could back then.

In the early 90's a Chicago professor gave a welcome lecture to the incoming freshman and ended by saying "May the Force be with you". Most of the students had no idea what he was talking about. I felt old that day.

As the final Star Wars chapter officially opens in the US today, my oldest daughter is only three years younger than I was when the first movie arrived. The movie has gotten good reviews and I look forward to reliving my youth, being with the Force and traveling one last time to that galaxy far far away.

--
Posted by Lance to Computational Complexity at 5/19/2005 06:43:00 AM

Summer is also the conference season. We have conferences and workshops year round but many organizers like to have their conferences in the summer when they won't conflict with courses. Instead we have conferences conflicting with each other. Be careful that you don't want to go to too many conferences as they cut into your the summer relaxed research atmosphere.

I plan to attend at least two conferences this summer, STOC, which starts this weekend in the beautiful suburbs of Baltimore and, of course, the Conference on Computational Complexity next month in San Jose. Stop by and say hi if you are there.

It's not summer yet in Chicago. We run in quarters at the University of Chicago and have two more weeks of classes followed by finals week. I can go to STOC missing only one day of classes but there were some conferences and workshops later on I will have to skip for finals week and graduation.

We get our revenge in the fall where most universities start at the beginning of September or earlier and our classes don't start until the last week of September. We hardly see any conferences scheduled in September, particularly in the US, because it is the beginning of most universities semesters. So I use September to visit faculty at other schools. We used to take vacations in September (crowds are smaller everywhere) but now the kids have school starting in late August making our effective summer quite short.

--
Posted by Lance to Computational Complexity at 5/20/2005 09:02:00 AM

• Most of the discussion was on theory funding and on the STOC republication policy and most of those discussions survived from yesterday. Check out the new Theory Matters site advocating increased theory funding.
• The Gödel Prize went to Noga Alon, Yossi Matias and Mario Szegedy for their paper The space complexity of approximating the frequency moments.
• Omer Reingold and Vladimir Trifonov won the best paper and best student paper awards respectively for their algorithms for undirected connectivity.
• Future Conferences: Complexity 2005 in San Jose, California June 12-15. Early registration deadline is Friday. FOCS 2005 in Pittsburg October 23-25, STOC 2006 in Seattle May 20-23, Complexity 2006 in Prague July 16-20, STOC 2007 and Complexity 2007 as part of FCRC in San Diego June 9-16 and STOC 2008 will be in Victoria.
• Check out the poster of the NP-completeness and the new DIMACS Implementation Challenge.

Complexity theory is well represented in this year's conference with some very nice papers in extractors, derandomization, PCP construction, hardness amplification and much more. Check out the program to see more.

On Friday and Saturday nights, the STOC hotel hosted proms from local schools. It's easier to explain baseball to non-Americans than the concept of a prom where high school students wear fancy clothes and spend large amounts of money for a single party.

--
Posted by Lance to Computational Complexity at 5/23/2005 08:18:00 AM

Today's Chicago Tribune has an AP article on the British craze of a Japanese number game Sudoku. In this puzzle you have a 9x9 grid subdivided into 9 3x3 grids. The goal is to fill the full grid with numbers 1 through 9 such that each number appears exactly once on each row, column and subgrid given some initial partial setting.

As a computational complexity theorist, I immediately wondered how hard is the generalized game on an n²xn² grid. A little googling shows the problem is NP-complete, shown in a 2003 Master's thesis of Takayuki Yato at the University of Tokyo. His proof uses a simple reduction from the Latin Squares problem proved NP-complete by Charles Colbourn.

--
Posted by Lance to Computational Complexity at 5/25/2005 01:35:00 PM

The early registration deadline for Complexity 2005 is 5 pm EDT on FRIDAY, MAY 27, 2005 (Eastern Daylight Time == 4 hrs behind Coordinated Universal Time (UTC/GMT)). Please take special note of the time: though the conference is on the Pacific Coast, early registration ends 5pm Eastern Time.

When you register for the conference, if you are not an IEEE Member but a SIGACT/EATCS Member, please enter that number (e.g., SIGACT xxxxx) to qualify for the discounted rate.

Please consider staying at the Conference hotel, Hyatt Sainte Claire; besides being convenient, it will help limit the conference expenses.

In San Jose and around the Silicon Valley, you will experience a unique combination of cultures and cuisines (American, Asian, European, Mexican) like nowhere else. There is a large number of restaurants, coffee shops, and bars within walking distance from the conference venue; these include highly-rated upscale restaurants as well as hole-in-the-wall type places that serve authentic food from around the world. For example, you could even get falafels that pass Ziv Bar-Yossef's stringent standards, and South Indian food certified by your local organizers as the best outside of Chennai. If you're one of those poor souls that happen to be vegetarian/vegan at a theory conference, relax -- there's Good Karma, White Lotus, and Vegetarian House within walking distance.

During mid-June, San Jose is an absolutely pleasant place to be, with daytime highs close to 80 degrees Fahrenheit (about 27 degrees Celsius), and night time lows near 55 degrees Fahrenheit (about 13 degrees Celsius). Downtown San Jose, where the conference will be located, has numerous interesting places: the Cesar Chavez Plaza and the Tech Museum of Innovation are right across from the hotel. The Center for the Performing Arts (CPA), the San Jose Repertory Theatre, the San Jose Museum of Art, San Jose State University, as well as the light rail station, are all within walking distance. CalTrain station (to go to San Francisco) is only about a mile away. The Repertory features Exceptions to Gravity by Avner Eisenberg during some of the conference days. CPA has the Festival of Cultures by the SJ Jazz Society, and an American Musical Theatre show during some of the conference days (see here). The Museum of Art (no entry fee!) has the Blobjects and Beyond : The New Fluidity in Design exhibit during all of June. The Tech Museum of Innovation is a one-of-its-kind museum that you should absolutely not miss when you're in town; during June, the IMAX theater there features a limited-screening edition of BATMAN, plus the Mysteries of the Nile -- be sure to check it out. If you're bringing children along, they will definitely enjoy the Children's Discovery Museum, within walking distance of the conference. Unfortunately, Major League Soccer's San Jose Earthquakes are playing Chivas USA on the road in Los Angeles.

--
Posted by Lance to Computational Complexity at 5/26/2005 05:32:00 PM

This is an example of what I call newspaper odds. If some people's misfortune appears in the newspapers then the odds are so low that you really shouldn't worry about it. High school mass shootings. Mad Cow Disease. Carbon Monoxide Deaths. No significant need to worry about these.

When deaths become too common to appear in a newspaper then you need to take notice and act carefully, say with automobile accidents or AIDS. Of course a cause of death might not appear in a newspaper simply because it doesn't happen, like recent US major commercial airline disasters. How to we tell the difference: celebrities. If a celebrity dies of AIDS or gets seriously injured in an automobile accidents, newspapers will cover it and remind us that these remain serious concerns for us all.

--
Posted by Lance to Computational Complexity at 5/28/2005 06:57:00 AM

Despite the increase in quality, I find myself going to fewer and fewer talks in general theory conferences. I learn much more talking directly to my fellow computer scientists. As for the presentations, I can read the papers later.

A fellow computer scientist suggested that we hire a company to videotape the talks and make them available on the web. A back of the envelope calculation suggested we could make this happen for about $10 extra per participant for a reasonably sized conference. I am not a fan of making talks available on the web. Outside of a conference, who has time to sit at a computer screen and watch talks. I also worry about giving people yet another reason not to go to a conference. Remember the most important aspect of a scientific conference are not the talks and papers but bringing members of the community together.

--
Posted by Lance to Computational Complexity at 5/30/2005 09:48:00 PM

During my undergraduate years at Cornell I struggled and gave up on Spanish. Luckily a linguistics professor had a theory that people who had trouble learning English early (like me) would have too much difficulty in picking up a new language, so I could take an intro linguistics course to cover my language requirement. Pretty cool as we covered context-free languages simultaneously in linguistics and in my introduction to theoretical computer science class.

In graduate school my three years of high school French got me out of the Ph.D. language requirement. If English was not the lingua franca of our field, I would be in serious trouble. I've always been impressed how many non-native speakers of English have succeeded in computer science.

I spent an entire year on sabbatical in Amsterdam but only learned enough Dutch to navigate the supermarkets and order in restaurants. Most Dutch speak English (and 3-4 other languages) and my attempts to say most Dutch words usually got responses in English. Still I definitely missed something as when I left a conversation the language shifted to Dutch and I couldn't get back in.

Suppose I could retroactively master a single foreign language, what language should it be? At times I would have liked to know Dutch, German, Hebrew, Japanese and the occasional French, Spanish, Danish, Italian and Portuguese. In the future I suspect I would visit countries speaking Hungarian, Russian, Chinese, Swedish and many others. I've gotten very good at navigating in countries where I don't know the language. In most European countries I can pass as a local as long as I keep my mouth shut.

The University of Chicago has a rather strict TOEFL requirement that would likely have caused a problem for me had I grown up in say Germany. Our department also has a small foreign language requirement for the Ph.D. Foreign language requirements made sense in a different era when papers were written in many languages. I remember a scene in graduate school where my advisor Mike Sipser and some Russian speaking students poured over the latest paper by Razborov translating from the Russian and hoping to understand Razborov's next great result. But now with nearly all papers written in English the requirement seems like a relic from a bygone time. Perhaps we should require every student to take the test in French, for France still has a few researchers stubborn enough to keep writing in their native tongue.

--
Posted by Lance to Computational Complexity at 6/1/2005 08:37:00 AM

• Is P≠NP?
• Who was Deep Throat?

• PH⊆BPP^⊕P
• BPP^⊕P⊆P^#P

1. ⊕P^⊕P=⊕P (Papadimitriou-Zachos)
2. NP⊆BPP implies PH⊆BPP (Zachos and also here)
3. NP⊆BPP^⊕P (follows easily from Valiant-Vazirani)
4. NP^⊕P⊆BPP^⊕P⊕P (relativize 3 to ⊕P)
5. NP^⊕P⊆BPP^⊕P (apply 1)
6. NP^⊕P⊆BPP^⊕P implies PH^⊕P⊆BPP^⊕P (relativize 2 to ⊕P)
7. PH^⊕P⊆BPP^⊕P (use 5 and 6)
8. PH⊆BPP^⊕P (immediate corollary of 7)

Three friends from college went on to become a doctor, lawyer and a mathematicians. They met back at reunion and the discussion went to whether it was better to have a wife or a mistress.

The doctor said "a wife" because having a monogamous relationship limited the risk of disease.

The lawyer said "a mistress" to avoid all of those nasty legal obligations of marriage.

The mathematician said "Both." "Both?" echoed the doctor and lawyer simultaneously. The mathematician responded "Of course both. That way your wife thinks you are with the mistress, the mistress thinks you are with the wife and finally you have time to do some math."

Some topics to be careful with:

• Popular Culture: Most scientists even many American scientists have no clue what occupies the minds of most Americans. Even a Michael Jackson joke would likely fall flat at our conference. A Star Wars joke might work on a majority of our crowd but too many of them feel that anything that is popular should be ignored. One exception is children's popular culture: Not that anyone likes Barney but you can't avoid him, especially if you have young kids.
• Politics: Since our field lies in such a narrow band in American politics, political jokes are fine as long as they sit in this band (i.e. making fun of Bush and his cronies). But a seemingly harmless joke outside this band will be considered "offensive". I once talked about a paper by Allender and Gore and said "but this is not the Gore that invented the internet." Didn't go over very well.
• The P versus NP problem: Some things are too important to joke about.

Finally, and most importantly, there was no discussion of the theory community's efforts to increase NSF funding for theoretical computer science, as there was at the (also beer-free) STOC business meeting. One question in particular was never asked: Are we computational geometers still even part of the theory community? The answer should be a resounding NO!, followed by a slap to the back of the head—of course computational geometry is part of theory! Look, we have big-Oh notation! Unfortunately, reality seems to disagree. None of the new material on TheoryMatters mentions computational geometry at all, although it does mention another border community: machine learning. With few exceptions, the computational geometry community rarely submits results to STOC and FOCS; this was not true ten years ago. Lots of geometric algorithms are published at STOC/FOCS by people outside the SOCG community, but nobody calls them computational geometry. (Sanjeev Arora's TSP approximation algorithms are the most glaring example.) For many years, computational geometry has been funded by a different NSF program than the rest of theoretical computer science. (This worked to our advantage when graphics was getting lots of money, but that advantage is now gone.) At one infamous SODA program committee meeting a few years ago, one PC member remarked that nobody at SODA was interested in computational geometry, they have their own conference, they should just send their results there. (This declaration led another PC member to resign.) Apparently, the divorce has been a complete success.

The Conference on Computational Complexity started in 1986 as the Structure in Complexity Theory Conference (Structures) by some researchers who felt their interests of complexity were not being well represented in STOC and FOCS. This view becomes self-fulfilling—sometimes very good papers would be turned down from STOC and FOCS because they were considered a "better fit" for Structures. In response we changed the name in 1996 and brought a broader view in complexity to the conference (though not without some controversy) and tried to work our way back into the STOC/FOCS community.

Other conferences like COLT, LICS and SoCG have moved the other direction. Note that SoCG also decided not to join the Federated Conference in 2007 while both STOC and Complexity will be there. I don't expect to see COLT or LICS at FCRC either.

What can we do, if anything? STOC and FOCS cannot properly cover the broad range of areas that have ever been considered theory. Unless we have a major restructuring of how the general theory conferences operate, we will continue to shrink the vision of theory as the area continues to grow.

--
Posted by Lance to Computational Complexity at 6/8/2005 06:13:00 PM

My Ph.D. student Rahul Santhanam (co-advised with Janos Simon) will receive his diploma this afternoon. He did his thesis work on time hierarchies and next year will be a postdoc working with Valentine Kabanets at Simon Fraser University in Vancouver. Rahul is officially my fifth Ph.D. student following Carsten Lund, Lide Li, Sophie Laplante and Dieter van Melkebeek, all of whom graduated in my pre-weblog days.

Also from our theory group, Daniel Stefankovic graduates today. He did his thesis on "Curves on Surfaces, String Graphs, and Crossing Numbers" and will be an assistant professor at the University of Rochester in the fall.

Call me a romantic but I really enjoy the pageantry of the graduation ceremony. I enjoy putting on the gown and the hood (even with those drab MIT colors) and marching past the parents as a member of the faculty and see the students come one by one, especially my own students, and receive their degrees. Chicago has a wonderful ceremony led by bagpipes in the front of the procession and the nice tradition of rarely having outside speakers (a major exception was Bill Clinton during his presidency). The ceremony was even more impressive when it was held in the Rockefeller Chapel but even with four ceremonies the chapel is not large enough to hold all the family members who want to attend.

--
Posted by Lance to Computational Complexity at 6/10/2005 09:47:00 AM

My favorite talk on the first day came from the best student paper winner, Ryan Williams on Better Time-Space Lower Bounds for SAT and Related Problems though I'm a bit biased since he's improving on some of my earlier work. He shows SAT cannot be solved by a random-access machine using n^c time and n^o(1) space for c slightly larger than the square root of 3 (about 1.732) improving on the previous lower bound of 1.618. He had several clever ideas recursing on the previous techniques. One can hope that by extending these techniques to push the lower bound to any c<2. Above 2 you seem to lose any advantage from doing recursion.

Today Manuel Blum given an invited talk taking "steps towards a mathematical theory of consciousness." More on that and the rest of the conference later.

--
Posted by Lance to Computational Complexity at 6/13/2005 08:39:00 AM

Blum made a strong point that his theory of consciousness is just being developed and emphasizing the word "towards" in the title. Roughly his theory has an environment (representing the world at a certain time) modeled as a universal Turing machine that interacts with several entities (representing organisms or organizations) each modeled as a (possibly weak) computational device. An entity has CONSCSness (CONceptualizing Strategizing Control System) if it fulfills certain axioms.

• The entity has a model of its environment and a model of itself.
• The entity is motivated towards a goal. Blum modeled the goal as a difference between a pleasure and a pain function which looked to me like utility functions used by economists.
• The entity provides a strategy to head towards the goal.
• The entity has a simple serial interface with the environment.

Blum called on complexity theorists to take on the cause of consciousness. He pointed to an extensive bibliography on the general topic maintained by David Chalmers.

My take on the talk: Much of theoretical computer science did get its start from thinking about how the brain works but as computers evolved so has our field and theory has since the 70's focused on understanding efficient computation in its many forms. It's perfectly fine to model humans as efficient computers to understand their interactions in areas like cryptography and economics. But we should leave issues like consciousness, self-awareness and free will to the philosophers since any "theorems" we may prove will have to depend on some highly controversial assumptions.

--
Posted by Lance to Computational Complexity at 6/14/2005 09:03:00 AM

So if you are have recently taken or will take a new position we want to know. Leave a comment on this post and tell us your new job whether in industry or academic at any level (professor, postdoc or even starting graduate school).

To all who post I say in advance: "Congratulations and Good Luck!"

--
Posted by Lance to Computational Complexity at 6/16/2005 08:14:00 AM

• Lance Jeremy Fortnow was a student of Sipser
  Awarded: 1989. Dissertation: Complexity-Theoretic Aspects of Interactive Proof Systems
• Michael Fredric Sipser was a student of Blum (1938-)
  Awarded: 1980. Dissertation: Nondeterminism and the Size of Two-Way Finite Automata
• Manuel Blum was a student of Minsky (1927-)
  Awarded: 1964. Dissertation: A Machine-Independent Theory of the Complexity of Recursive Functions
• Marvin Lee Minsky was a student of Tucker
  Awarded: 1954. Dissertation: Theory of Neural-Analog Reinforcement Systems and Its Application to the Brain Model Problem
• Albert William Tucker was a student of Lefschetz (1884-1972)
  Awarded: 1932. Dissertation: An Abstract Approach to Manifolds
• Solomon Lefschetz was a student of Story
  Awarded: 1911. Dissertation: On the Existence of Loci with Given Singularities
• William Martin Story was a student of Carl Gottfried Neumann (1832-1925) and Klein (1849-1925)
  Awarded: 1875. Dissertation: On the Algebraic Relations Existing Between the Polars of a Binary Quantic
• Felix Christian Klein was a student of Julius Plücker (1801-1868) and Lipschitz (1832-1903)
  Awarded: 1868. Dissertation: Über die Transformation der allgemeinen Gleichung des zweiten Grades zwischen Linien-Koordinaten auf eine kanonische Form
• Rudolf Otto Sigismund Lipschitz was a student of Dirichlet (1805-1859) and Martin Ohm
  Awarded: 1853. Dissertation: Determinatio status magnetici viribus inducentibus commoti in ellipsoide
• Gustav Dirichlet was a student of Poisson (1781-1840) and Joseph Fourier (1768-1830)
  Awarded: 1827. Dissertation: Partial Results on Fermat's Last Theorem, Exponent 5
• Simeon Poisson was a student of Lagrange (1736-1813)
  Awarded: Unknown. Dissertation: Unknown.
• Joseph Lagrange was a student of Leonhard Euler (1707-1783)
  Awarded: Unknown. Dissertation: Unknown.

• Felix Christian Klein was a student of Plücker (1801-1868) and Rudolf Otto Sigismund Lipschitz (1832-1903)
  Awarded: 1868. Dissertation: Über die Transformation der allgemeinen Gleichung des zweiten Grades zwischen Linien-Koordinaten auf eine kanonische Form
• Julius Plücker was a student of Christian Gerling
  Awarded: 1823. Dissertation: Generalem analyeseos applicationem ad ea quae geometriae altioris et mechanicae basis et fundamenta sunt e serie Tayloria deducit
• Christian Gerling was a student of Johann Carl Friedrich Gauß (Gauss) (1777-1855)
  Awarded: 1812. Dissertation: Methodi proiectionis orthographicae usum ad calculos parallacticos facilitandos explicavit simulque eclipsin solarem die

1. My sources are various in print and online, but they originate from The Mathematics Genealogy Project.
2. Little is known of William Edward Story and Albert William Tucker and their lives.
3. Martin Ohm is the brother of Georg Simon Ohm, for whom Ohm's Law is named.
4. I find it interesting that Klein was awarded his doctorate the year of Plücker's death. Klein was Plücker's assistant for nearly three years.
5. It had been believed, but not shown that Carl Gottfried Neumann was advised by Georg Friedrich Bernhard Riemann. Neumann was, in fact, advised by Otto Hesse and F. Richelot. Hesse was also a friend of Neumann's father, Franz. Many modern mathematicians mistakenly trace their roots through Neumann to Riemann and Gauss. Riemann received his doctorate in 1851 at Göttingen. Riemann was subsequently awarded a post at Göttingen by Gauss in 1851 to allow Riemann to study for his Habilitation. Riemann delivered his lecture to earn the Habilitation under Gauss in 1854. Gauss died the following year (Dirichlet was given his chair). Carl Gottfried Neumann was awarded his doctorate in 1855 at Königsberg.

The title result of this paper gave an early example of a natural problem that provably does not have an efficient algorithm. But it is the second half of the paper that developed one of the most important concepts in computational complexity.

The class NP consists of those problems with efficiently verifiable solutions. Similar to the arithmetic hierarchy, Meyer and Stockmeyer define a hierarchy above NP inductively as follows:

• Σ₁^p=NP
• Σ_k+1^p=NP^Σ_kp, where NP^A represents the class of problems solvable in nondeterministic polynomial time with access to an oracle for solving problems in A.

• Alternation characterizations of the hierarchy using quantifiers and second-order logic.
• If for any k, Σ_k^p=Σ_k+1^p then for all j≥k, Σ_k^p=Σ_j^p. If this happens for some k we say the polynomial-time hierarchy collapses, otherwise the we say the hierarchy is infinite.
• PSPACE contains the polynomial-time hierarchy and if the converse holds then the hierarchy collapses.

• classifying some problems like succinct set cover and VC dimension that NP does not capture,
• using the conjecture that the hierarchy is infinite to imply the likelihood of a number of statements like that NP does not have small circuits and that graph isomorphism is not NP-complete,
• attempts to show the polynomial-time hierarchy is infinite in relativized worlds have led to major results on circuit lower bounds,
• led to the concept of alternation giving new characterizations of time and space-bounded classes, and
• variations on the hierarchy led to interactive proof systems that themselves led to probabilistically checkable proofs and hardness of approximation results.

1. If you ask someone about what problems they are working on you shouldn't start working on those problems or give them to others without permission. When this rule is violated, even students in the same department are sometimes afraid to discuss their own research with each other.
2. If someone discusses a problem with you shouldn't mention the problem to others without permission. Asking a question like "Do you mind if I tell this problem to my students?" is sufficient.
3. If you are an advisor and you give a problem to a student you shouldn't work on the problem yourself or give it out to other students without the first student's permission.
4. Outside the advisor-student relationship the above rule does not apply. You can work on a problem even if you give it to someone else or distribute it as you wish unless you've had a prior agreement.
5. Once you make a problem public (in a talk, in a paper or on the web) the problem is fair game to all.

I see I have subconsciously stopped calling Herbie "it" and am now calling Herbie "he." Maybe I've answered my own question. If Herbie is alive, or able to seem alive, isn't this an astonishing breakthrough in the realm of Artificial Intelligence? That's if computer scientists, working secretly, programmed Herbie to act the way he does. On the other hand, if Herbie just sort of became Herbie on his own, then that would be the best argument yet for Intelligent Design…

The real story is Herbie's intelligence. The car seems to be self-aware, able to make decisions on its own, and able to communicate with Maggie on an emotional level, and sometimes with pantomime or by example. Why then is everyone, including Lohan, so fixated on how fast the car can go? The car could be up on blocks and be just as astonishing.

It goes to show you how we in the press so often miss the big stories that are right under our noses. There is a famous journalistic legend about the time a young reporter covered the Johnstown flood of 1889. The kid wrote: "God sat on a hillside overlooking Johnstown today and looked at the destruction He had wrought." His editor cabled back: "Forget flood. Interview God."

About a month ago was the final episode of ENTERPRISE. I just saw it last week. I assume that NONE of the readers are saying "Gee, how did he do that!"

At one time many computer scientists were also science fiction fans.

At one time both were small communities (with enrollment dropping computer scientists may return to being a small community).

At one time you couldn't time-shift how you watched TV so people would talk about the same show the next day.

At one time there was not so much Science Fiction out there so all the fans graviated towards the same materials.

So in the past there was much more cohesivness to the CS/Sci-Fi community.

There is no longer.

Is this good or bad?

I thing its good to NOT be so homogenous. New ideas come from all kinds of places. And you don't want people who are not Sci-Fi fans to NOT major in Comp Sci since they think they have to be.

--
Posted by Lance to Computational Complexity at 6/24/2005 07:10:00 AM

There is also a linear version of unique games where C is a finite field and for each {i,j}, π_i,j(x)=a_i,jx+b_i,j with a_i,j and b_i,j in C and a_i,j≠0.

If a coloring fulfills all the edges then knowing the color at one edge uniquely determines all of the other colors. One can efficiently determine whether such a coloring exists by trying all possible colors at one node and seeing if any of the resulting coloring fulfills all the edges.

However it might be difficult to determine whether one can fulfill some large fraction of the edges. Subhash defines the unique games conjecture.

For every constant δ>0 there is a fixed finite color class C such that it is NP-hard to distinguish the following two cases for any unique game with color class C.

1. There is some coloring that fulfills at least 1-δ-fraction of the edges.
2. Every coloring fulfills at most a δ-fraction of the edges.

• Khot, Kindler, Mossel and O'Donnell reduce unique games to approximating Maximum Cut better than the best known approximation due to Goemans and Williamson (about 0.878567). Khot et. al. also required a "Majority is Stablest" conjecture which was later proved by Mossel, O'Donnell and Oleskiewicz. Thus under the unique games conjecture any improvement in approximating Max Cut would imply P=NP.
• Similar results showing that given the unique games conjecture (and P≠NP) it is hard to approximate Vertex Cover with 2-ε (Khot-Regev) and Sparsest Cut within any constant (Chalwa-Krauthgamer-Kumar-Rabani-Sivakumar).
• Trevisan shows that we can solve the unique games conjecture in polynomial time if we allow δ=o(1/log n) instead of a constant.
• In an upcoming FOCS paper, Khot and Nisheeth use unique games to (unconditionally) disprove the conjecture that negative type metrics (metrics that are squares of Euclidean metrics) embed into L₁ with constant distortion. They also show a superconstant lower bound on the integrality ratio for Semi-Definite Programming relaxations for Sparsest Cut.

The field of theoretical computer science is interpreted broadly so as to include algorithms, data structures, complexity theory, distributed computation, parallel computation, VLSI, machine learning, computational biology, computational geometry, information theory, cryptography, quantum computation, computational number theory and algebra, program semantics and verification, automata theory, and the study of randomness. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.

I dislike these "laundry list" definitions. They both tend to overcompensate by listing too many areas (e.g. "the study of randomness" is really subsumed by the other areas) and failure to capture all the areas we study (e.g. electronic commerce). Such lists cannot remain stable over time and need constant updating and we find it hard to delist any areas even if we should.

Most importantly laundry lists don't capture the spirit of a field. If we really wish to sell our field properly we need to start with a clear definition. Here is a suggestion.

Theoretical Computer Science is the formal analysis of efficient computation.

In complexity two of the unique games papers I mentioned on Monday will be at FOCS. Some other interesting looking complexity papers:

• Mark Braverman, On the Complexity of Real Functions.
• O'Donnell and Michael Saks and Oded Schramm and Rocco Servedio, "Every decision tree has an influential variable". I can't find the paper online but here is a talk abstract.
• Ran Raz, Quantum Information and the PCP Theorem where he shows, among other results, that every language has a quantum interactive proofs with quantum advice.

I feel a little déjà vu here. Ten years ago Karp led a NSF sponsored group with the mission of suggesting where the NSF theory group should focus its funding. The group held a panel discussion at the end of the 1995 STOC conference. Representatives from different subfields gave a short talk on the importance of their fields. After these presentations the panel opened the discussion to the audience.

Now instead of a physical panel discussion, Arora asks for a virtual one in a hope to draw from a larger base of people. Feel free to leave your ideas as comments on this post, on the committee page of the Theory Matters Wiki (edit password: tcs), or just by email to one of the committee members. Not everyone was happy with the last Karp report, so better to get your comments in now than complain afterwards.

--
Posted by Lance to Computational Complexity at 6/30/2005 04:14:00 PM

Outside of the US the Fourth has no special meaning so non-Americans have no qualms running conferences and workshop over our holiday. This will be my first time in three years spending the entire Independence Day in the US. Last year I was in Banff and in 2003 on a plane to Denmark. (I may not collect much sympathy here.)

How will I celebrate America's 229^th Birthday? A parade in the morning, a friend's house for barbecue and capping the night with fireworks. Should be a perfect Fourth.

--
Posted by Lance to Computational Complexity at 7/03/2005 09:51:00 PM

Sometimes, people express perplexity as to the nature of the problem. They do not see anything mysterious about consciousness, and do not understand in what way it is different from other neurological functions like, say, the regulation of breathing. Asked whether a computer could in principle be conscious, they answer, "why not?"

We are dumbfounded by this reaction, and can only conjecture that these people are themselves not conscious. To me, it is evident that no combination of silicon chips and wires could conceivably "experience" in the sense that I do. Consciousness involves something beyond the merely physical and mechanical.

The question whether an entity is CONSCS is a function of its algorithms, not the stuff (silicon or carbon) that implements those algorithms.

What happens when an entity stops being an entity?