As a way to celebrate this blog turning one year old, I’m going to talk about one of my favorite topics, Godel Incompleteness. It is discussed endlessly, seldom correctly. It stands as one of the greatest achievements of human thought; however, it is not a triumph of mankind inasmuch as a cold rejection of our naive idealism. Godel Incompleteness says that we are crippled in our quest for the Truth, nullifying David Hilbert’s epitaph, “Wir mussen wissen, wir werden wissen” – We must know, we will know.Instead, engraved upon the cosmic firmament is: We will never know.
I was wondering when these would show up! Finally, all the FOCS talks are up for your theoretical computer science learning pleasure! Grab ‘em while they’re hot! Provided by Dan Spielman.
I know this is late; but I said I would provide a summary of my time there, so here it is:
FOCS Day 2
Attended several algorithmic game theory talks; the most interesting being Amin Saberi’s on modeling the spread of ideas or technologies, where an epidemic-consume-all model isn’t accurate. People usually like to conform to the ideas of people around them, and with that principle in mind, he studied how long it took different types of networks to converge to complete saturation of a single idea or technology. It turns out that the better connected the graph (i.e. a random graph), the longer it takes (exponentially longer) to spread the idea. Well, it’s a bit more complicated than that, but that’s the intuition.
The PCP talks (PCP stands for Probabilistically Checkable Proof, not the drug) were exceptionally good. They were clear, lucid, and just got me even more interested in this topic. I especially enjoyed Pradladh Harsha’s talk on “Composition of 2-query low-error decodable PCPs”. I spoke with him earlier before his presentation and learned quite a bit about proof complexity.
That night I went out with Urmila, Dustin, and a bunch of other people to eat out in a reputedly amazing Indian restaurant. We took a train ride to a suburb of Atlanta only to find that it was closed; but no matter, I was in good company. Learned even more proof complexity from my Swedish friend Jakob.
I ran into Rong Ge, one of the authors of the (in my opinion) stunning paper “Computational Complexity and Information Asymmetry in Financial Products,” and we had a good conversation about applications of theoretical computer science to areas like finance and sociology.
FOCS Day 3
Attended the Quantum Information session. Rahul Jain, Upadhyay and Watrous’ paper on “Two message Quantum interactive proofs are in PSPACE” was the one I looked forward to most; but I was expecting them to talk about their newest result that subsumed this: that QIP actually equals PSPACE (equals IP). I asked Jain about this, and he said that they discovered QIP=PSPACE after submission to FOCS, and it will appear in STOC (most likely). The talk was great nonetheless.
Listened to Xin Li from UT Austin present their work on 2-Source randomness extractors. Randomness is an incredible intriguing topic. I still wonder if randomness can still exist.
Ryan Williams closed out FOCS with his delightfully funny presentation on “Regularity Lemmas and Combinatorial Algorithms”. He showed us a new upper bound on the problem of boolean matrix multiplication – the first in nearly 40 years! I’m now going to adopt the “Four Dudes” Algorithm instead of the “Four Russians” Algorithm terminology and hope it catches on.
Theory Day (FOCS Day 0)
Saw the greats of Theoretical Computer Science speak; Richard Karp gave a presentation on “What makes an algorithm great?” He provided a grand tour of the great algorithms that man has invented since the dawn of time. However, I wish he talked a little bit more about what he thinks will be characteristics of the great algorithms of the next 5, 10 years. I mean, if you’re such an eminent figure in the TCS community, you might as well play the role of the prophet-visionary, right?
Manuel Blum talked about his views on consciousness, and how his life was actually shaped by his curiosity about the mechanism behind conscious thought. “I was a very dumb boy,” he modestly claimed, “But my father told me that, if you wanted to get smarter, you should figure out how that works.” And so he went on in college to work with some of the pioneers of artificial intelligence, including Marvin Minsky, McCullough and Pitts, and others. Dick Lipton provides a very nice summary of Blum’s talk.
I’ll be terse, because after a full day of conferencing I’m mentally exhausted, but here are some of my highlights:
I learned a little about circuit complexity: I attended A. Chattopadhyay’s talk about “Linear Systems over Composite Moduli”, and Paul Beame’s “Multiparty Communication Complexity and Threshold Circuit Size of AC^0″. The latter was intriguing; Beame and Ngoc used Communication Complexity to prove complexity lower bounds on circuit complexity.
My favorite talk of the day came early in the morning when Saugata Basu presented his work on the Real Analogue of Toda’s Theorem, the incredible result that the polynomial hierarchy is contained in the class of all polynomial time turing machines with access to #P, the class of turing machines that counts (say) satisfying assignments to the SAT problem. Though P is at the bottom of the polynomial hierarchy, allowing easy counting gives P an enormous advantage – a testament to the power of counting. Basu and Zell worked out Toda’s Theorem over the reals using the Blum-Shub-Smale model of computation, using “semi-algebraic” techniques (algebraic geometry over the reals I presume?). They would like to prove a generalized Toda’s Theorem for any arbitrary ring, which would be simply astounding.
Of course, everybody had to attend “Bounded Independence Fools Halfspaces.”
It was great meeting and conversing with people whose names I have been reading about for quite some time. It is very humbling to come into contact with such smart and talented people.
It’s been a very, very long day, but full of intriguing, inspiring, insightful ideas, as well as the warmth and hospitality of the theoretical computer science community.
The fun continues tomorrow; talks I eagerly anticipate: our very own Shang-hua Teng’s “Settling the Complexity of Arrow-Debreu Equilibria in Markets with Additively Separable Utilities” (one of his many, many papers in this year’s FOCS), “The Intersection of Two Halfspaces Has High Threshold Degree” (one of the winners of the Best Student Paper), and “Combinatorial PCPs with Efficient Verifiers”.
I apologize for the lack of posts. October has been quite a time drain; it’s the month of midterm examinations, and the month before applications are due. I had to take the GRE several weeks back, and since then it’s been a never-ending onslaught of assignments and tests. I’m also applying to the NSF graduate fellowship, so a lot has been on my plate.
But more excitingly, this weekend I will be in Atlanta, Georgia at the 50th Foundations of Computer Science (FOCS) conference! I will try to type up a summary of my time there every day – what talks I’ve attended, my thoughts, inspirations. As my Friday red-eye flight draws near, my excitement grows without bounds. I’ll be able to see the debut talk of QIP=PSPACE, or “Combinatorial PCPs with Efficient Verifiers”, and hang around the greats of the Theoretical Computer Science community. I’ll be back in several days.
Leonard Adleman, of RSA and DNA computing fame, and also my mentor, has posted his essay on his views of interpreting Quantum Mechanics on Clifford Johnson’s blog. Coming from a mathematical logic angle, Quantum Mechanics does not require a (in my opinion outlandish) theory of many-worlds or ridiculous interpretations such as a “wavefunction collapse”. The uncertainty and inherent “randomness” of the universe is merely a manifestation of the complexity of the universe; it is simply too complex for us mere mortals to comprehend everything in it. Godel’s Incompleteness provides a rigorous framework to describe this phenomenon in mathematics, and there should be no reason why it should not apply to our physical universe.
Here’s an excerpt from Len’s note:
For a long time, physicists have struggled with perplexing “meta-questions” (my phrase): Does God play dice with the universe? Does a theory of everything exist? Do parallel universes exist? As the physics community is acutely aware, these are extremely difficult questions and one may despair of ever finding meaningful answers. The mathematical community has had its own meta-questions that are no less daunting: What is “truth”? Do infinitesimals exist? Is there a single set of axioms from which all of mathematics can be derived? In what many consider to be on the short list of great intellectual achievements, Frege, Russell, Tarski, Turing, Godel, and other logicians were able to clear away the fog and sort these questions out. The framework they created, mathematical logic, has put a foundation under mathematics, provided great insights and profound results. After many years of consideration, I have come to believe that mathematical logic, suitably extended and modified (perhaps to include complexity theoretic ideas), has the potential to provide the same benefits to physics. In the following remarks, I will explore this possibility.
I encourage everyone to join in on the discussion following the post!
This is just in time, as well, for my one-year anniversary post for this blog, where I will be discussing why I personally love Godel’s Incompleteness so much. It shall hopefully come out sometime this week.
For a long time, physicists have struggled with perplexing “meta-questions” (my phrase): Does God play dice with the universe? Does a theory of everything exist? Do parallel universes exist? As the physics community is acutely aware, these are extremely difficult questions and one may despair of ever finding meaningful answers. The mathematical community has had its own meta-questions that are no less daunting: What is “truth”? Do infinitesimals exist? Is there a single set of axioms from which all of mathematics can be derived? In what many consider to be on the short list of great intellectual achievements, Frege, Russell, Tarski, Turing, Godel, and other logicians were able to clear away the fog and sort these questions out. The framework they created, mathematical logic, has put a foundation under mathematics, provided great insights and profound results. After many years of consideration, I have come to believe that mathematical logic, suitably extended and modified (perhaps to include complexity theoretic ideas), has the potential to provide the same benefits to physics. In the following remarks, I will explore this possibility.
What do you think are the best (quantitative) indicators of a good football team? Let’s not talk about rankings here, they’re subjective and have a lot of assumptions implicit in them. One example of a good indicator is the win-loss record from the previous season. However, this isn’t the best indicator, because you have teams like Boise State racking up 13-0 seasons, but within a pathetically weak conference. Then you have teams from the SEC who invariably get beat-up (LSU of past seasons), but are pretty awesome. Another might be the average margin-of-victory (or margin-of-loss) of their games. If you have any ideas, lay ‘em on!
Recently, I have been working on a fun little side project. It’s not ready be divulged just yet, but rest assured, the world will know soon. Today I’d like to talk about a tiny problem that’s curious and amusing: how to randomly walk on an n-dimensional hyperplane. It’s been a useful part of this project; I hope that someone might find it of use as well, or at the very least, find it interesting.
Again, this technical post comes with the usual warning for people who are reading this on other sites, such as Facebook: the LaTeX will not show up properly. Just navigate to my blog. Continue reading
A couple days ago I was on an evening flight from New York to Los Angeles. Just as our plane pulled into Los Angeles, I was fascinated by the view below. Looking down, one can see the glow of the Southern California megalopolis, the giant sprawl unbounded in size. But the thing that intrigued me most was the sight of the freeways; the steady, arterial motion of traffic through the vast grid of Southern California’s freeways. It was a distinctly an impression of a circulatory system.
The monster of the SoCal sprawl is a living body. Continue reading
Recent Comments