Skip to content

Workshop: Computation As A Lens

April 1, 2011

Not April fool, real workshop, real people, really

Dick Karp is Dick Karp.

Today I want to help announce a workshop that Dick is holding at Berkeley on May {7^{th}} and {8^{th}}.

I usually do not do announcements for workshops, but I think making an exception for anything Dick does is right.

The Workshop

The conference is: Theory of Computation as a Lens on the Sciences. It is being held on the Berkeley campus May 7 and 8. Chris Switzer is the contact—see here for more information and details. There is no charge for registration—a pretty good deal.

The conference will explore the theme that many processes in the physical, biological, engineering, and social sciences involve information processing at a fundamental level and can be studied through computational models. A conference held in Berkeley in May, 2002 helped crystallize this theme as a promising direction of research, and this second conference will highlight the impact of the computational lens on areas such as quantum information science, statistical physics, social networks, economics and game theory, genetics, molecular biology, evolutionary biology, cognitive science, mathematics, statistics and machine learning.

Featured Topics:

  • Evolution as a Form of Learning
  • Robustness and Complexity in Games
  • Algorithms, Games, and the Internet
  • Analysis of Social Networks
  • Structure and Dynamics of Networks in the Real World
  • On Joint Inference of Phylogeny and Alignment
  • Cancer Genomics
  • Statistical Physics and Computation
  • Computer Science as a Lens on Quantum Theory
  • How Does Quantum Mechanics Scale?
  • A Computational Approach to Discovery in Biology
  • Ultra-Large Phylogenetic Estimation
  • Large Phylogenies from Short Sequences: Recent Theoretical Insights

Featured Speakers:

  • Daniel Fisher
  • David Haussler
  • Michael Jordan
  • Ehud Kalai
  • Michael Kearns
  • Andrea Montanari
  • Jonathan Oppenheim
  • Lior Pachter
  • Christos Papadimitriou
  • Sebastien Roch
  • Leslie Valiant
  • Tandy Warnow
  • Umesh Vazirani
  • Mark Newman

Open Problems

Who is giving which talk? And more importantly what is Computation as a Lens?

[A consensual editorial change was made in the comments section, hence the mismatch in numbers reported by WordPress.]

25 Comments leave one →
  1. Virendra Sule permalink
    April 2, 2011 2:37 am

    I would be interested to know comments by experts on Narendra Karmarkar’s recent paper, Beyond Convexity New perspectives in computational optimization, LNCS, 6457, pp.1-23. (Karp was Karmarkar’s doctoral advisor, to my knowledge but I could be wrong).

  2. April 2, 2011 5:33 am

    This is a terrific post! It happens that this month’s Bulletin of the AMS contains two articles that focus upon “Computation As A Lens” (please forgive the pun): these articles are Peter Sarnak’s Recent progress on the quantum unique ergodicity conjecture and Misha Gromov’s Crystals, proteins, stability and isoperimetry (both Sarnak and Gromov are highly respected mathematicians).

    Broadly speaking, Sarnak’s article embraces computation as a lens for exploring dynamics on large-dimensions Hilbert state-spaces, while Gromov’s article embraces computation as a lens for exploring dynamics on reduced-dimension biological state-spaces … yet Gromov’s article recognizes that at the end of the day, biological systems are quantum systems too.

    Neither Sarnak’s nor Gromov’s article is exclusively or even primarily computational, rather for both authors large-scale computation is a tool that helps in evolving a mathematically natural and synoptic appreciation of complex systems.

    Now, being engineers, our QSE group’s standard practice is to read Sarnak’s and Gromov’s articles both forwards and backwards; and the backwards reading is particularly interesting.

    We reflect that from a quantum point-of-view, all forms of microscopy—and lenses in particular—are two-way communication channels, in which samples look at the scientists in the same sensu stricto that scientists look at samples. And the same is true obviously of computational lenses, for the common-sense reason that methods of computation tell us just as much about the STEM enterprise, as results tell us about the particular systems we are computing.

    So we are led to ask, what do we see when we look backwards through Sarnak’s and Gromov’s “lenses of computation”? To formalize our answer, let’s introduce a definition that is inspired by one of Dick Lipton’s favorite phrases, “proof technology”:

    Definition  a haeros is a set of theorems, proof technologies, and algorithms that, in aggregate, provides mathematically natural foundations for a distinctive class of STEM technologies, enterprises, and disciplines (from the Greek αἱρέω, meaning “to grasp with the mind, understand”, also “take to oneself, choose”).

    Then upon looking backwards through the lens of Peter Sarnak’s article, we perceive a familiar haeros:

    Haeros I  (Church of the Larger Hilbert Space)
    By specifying a sufficiently large-dimension Hilbert state-space, it can always be ensured that:
    (1) quantum states are pure,
    (2) measurement processes are ideal, and
    (3) dynamical evolution is unitary.

    Here we recall that “Church of the Larger Hilbert Space” is John Smolin’s celebrated and increasingly popular name for a haeros that the basis for much modern quantum information science; this same haeros is called by Neilsen and Chuang’s textbook the “Principles of Deferred and Implicit Measurement” (and it is known by very many other names too).

    Can we find a similarly concise and rigorous haeros for Gromov’s article too? This turns to be feasible; in the language of symplectic geometry that haeros is:

    Haeros II  (Canons of Quantum Systems Engineering)
    In pullback to a Kählerian state-space of any tensor rank, it can always be ensured that:
    (1) dynamical potentials respect Lie algebras,
    (2) measurements respect Lindbladian informatics, and
    (3) trajectory integration is efficient.

    We remark that this latter haeros encompasses rank-1 state-spaces and exponential-rank Hilbert state-spaces as two limiting cases, such that classical-versus-quantum is not a sharp divide; instead dynamical systems are associated to a mathematically natural continuum of quantum-ness.

    Guided by the computational lens analogy, we recall from the history of science that it is only by combining diverging and converging lenses, that we obtain microscopes and telescopes that are reasonably free of chromatic abberation. And this abberration cancellation was not easy to grasp; even so great a scientist as Newton was slow to appreciate it.

    Similarly, by a strategy of uniting Sarnak-style enlarging haeroes, with Gromov-style reducing haeroes, we can hope to construct computational lenses that will show us more clearly the (amazingly complicated) world outside ourselves. And at the same time, these computational lenses (and many more being constructed) are certain to show us more clearly too, the (amazingly complicated) worlds inside ourselves.

    As Richard Feynman might have said: “It’s gonna be terrific!” 🙂

    • April 6, 2011 11:26 am

      After seeing this very intriguing “Computation as a lens”, after finding this comment mentioning
      haeros and Gromov, I cannot stop to submit to anybody attention this paper:

      How to add space to computation? A tangle formalism for chora and difference

  3. Allen Knutson permalink
    April 2, 2011 6:18 am

    The 2002 conference not only had no charge for registration but also free gourmet box lunch! I hope I’m not lowering the tone of the comment section, but if you weren’t convinced to attend before…

    • rjlipton permalink*
      April 3, 2011 11:01 am


      Lunch is important. Thanks your comment.

    • April 5, 2011 5:39 pm

      Dear Allen,
      Unfortunately boxed lunches will not be provided this time — we apologize for the inconvenience! We hope you’ll still be able to make it. = )
      chris switzer.

  4. dmfdmf permalink
    April 2, 2011 8:18 am

    I find it ironic that it took the invention of the computer for the scientists to rediscover the importance of epistemology (i.e. a philosophy of knowledge which applies to all branches of science). How long will it take these scientists to rediscover that they need a theory of concepts and a theory of induction?

  5. April 2, 2011 9:57 am

    Will the talks be recorded and put online?

    • April 5, 2011 1:24 am

      It would be great if the organizers record and put the videos online.

    • April 5, 2011 5:40 pm

      Dear Tyson,
      Yes, the talks will be recorded and posted online.
      Many thanks for your interest,
      chris switzer.

  6. April 3, 2011 6:48 am

    I think I’ll skip this conference. Too applied for my taste.

  7. Arun permalink
    April 3, 2011 10:42 am

    Such a new concept will be very difficult for people, even experienced mathematicians, to understand. You need to stick around to explain.

    • Ravindra Chourase permalink
      April 3, 2011 11:19 am

      I just need a chance to explain.
      I am sure I can do that.

      May be I am not so good in writhing the blog, but I confident that this is the thing we are waiting for last around 50 years.

      And I can solve the problems which are so called NP complete, using the same concept, I have given an illustration also, about how it can be possible.

  8. April 3, 2011 2:14 pm

    If you have indeed shown that P=NP in a practical sense, you don’t need some award from the Clay Mathematics Institute, approval of anyone on this blog, or really anyone to believe P=NP in order to make a healthy living. Of course, there would still remain a lot of work implementing software to solve practical problems and pitching it with free demonstrations (companies want to see results before they buy), but the key there is that you don’t even need to mention that you think you’ve proven P=NP, only that your software easily beats the competition at solving some practical problem.

    However, always keep in mind the possibility that you could be wrong, and there is no shame in being wrong. I’m often wrong; often when I fervently believe that I’m right, but I always try to keep in mind that I could be wrong. Try to thing of what would be necessary to prove your hypothesis wrong, and examine whether such a thing can or cannot exist.

    A recent example where I was wrong: I believed that any open quantum system, S, coupled to a highly random environment, E, of uncoupled spins will always reach a Boltzmann distribution of S in the long-time limit, since this sounds like the 2nd law of thermodynamics. For non-random E and non-random coupling, I knew that it wasn’t true, but it turns out that even for highly random E, if the coupling between E and S is strong enough, the long-time limit is still not a Boltzmann distribution. It’s only true if E and S are coupled weakly enough or in restricted ways. I asked what would be necessary to prove my hypothesis wrong, and I was kindly given an example by a colleague.

    • April 3, 2011 3:55 pm

      You are lucky,
      I also was trying to ask for counterexamples, and guess – no answers. Probably, I do not know right people, or people I’m asking think I’m so unreasonable, that does not require any attention.

    • Ravindra Chourase permalink
      April 4, 2011 2:17 am

      If you are right then you can feel it in your heart. It happens with everyone.
      This comes form the inner edge of your heart and only you can feel it, it does not depends upon the believes and and of the opinion of the outer world.

      I am sure at some part or the other in your life you have experienced it.

    • April 4, 2011 2:59 am

      @mkatkov: You can do it yourself. Examine what would be necessary to form a counterexample, and both 1) attempt to find such a counterexample, and 2) attempt to formally prove that no such example exists. It may be the case that such an example is extremely complicated and contradicts supposedly “safe” assumptions, but nonetheless exists, so keep an open mind.

      For example, one type of heuristic for Max Clique tends to do fairly well on random graphs, and another type of heuristic for it tends to do fairly well on graphs designed to trip up the other type of heuristic, so finding graphs for which a hybrid approach does poorly is very difficult. However, they can be found.

      @Ravindra: Feelings do not make a person any more or less right about a logical matter. Moreover, they can cloud judgement, because as humans, we will tend to see the things that appear to support our hypotheses and will tend to miss things that appear to contradict our hypotheses. This is called “confirmation bias” ( It is made worse by also having a separate desire to have the hypothesis be true.

    • April 4, 2011 4:35 am

      Hi, Mr. Chourase—we have written you yesterday by private e-mail. Did that help appreciate your concept? You’re welcome to reply privately, of course.

    • April 4, 2011 10:58 am

      @Neil: You are too good in opinion on me. I cannot even communicate that sufficient condition for P=NP is that Q(x) = \sum \limits_k x_k^4 + 2 x^T(Q-I)x+t \geq 0 \forall x \in R^n \Rightarrow Q(x) is a sum of squares of polynomials (sos). And then there is easy and difficult cases. Suppose x^* is global optimum of Q(x), then there is an easy case when Q-I+diag(x_k^{*2}) is psd, than it has straightforward representation as a sum of squares with correct constant, and there is difficult case when Q-I+diag(x_k^{*2}) is not psd. In simulations, Q(x) - \min Q(x) is sos. I do not see how to deal analytically with the difficult case.

  9. April 4, 2011 2:19 pm

    By the way, I think the problem does not cost any human life sacrificed, nor million dollars. You have weigh, and may consider it to be ethical to remove any monetary prizes from the problems easily formulated, that gain seeking people can be attracted to gamble. Remember what happen with Perpetuum mobile? We are still in the world of noble people dominating.

  10. April 7, 2011 9:51 am

    Dear Mr. Chourase,
    I found your Gmail account with the Boxbe filter. I followed the instructions in this automatic return message: ‘Hello Kenneth W. Regan, I use Boxbe to prioritize my email. While I did receive your email about “P=NP … and India’s 6-wicket win…”, you are not currently listed in my priority Guest List. ‘ My mail was dated 4:25pm EDT last Sunday, and hasn’t “bounced” in almost 4 days. All the best getting on-track with your studies and ideas.


  1. Theory of Computation as a Lens on the Sciences « Algorithmic Game-Theory/Economics

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s