Test Your Intuition (23): How Many Women?

2014 Economics School poster

How many women can you find on this poster announcing the 25th Jerusalem School in Economics Theory devoted to Matching and Market Design?

Please respond to the poll:

Posted in Economics, Test your intuition | Tagged | 5 Comments

Happy Birthday Richard Stanley!

Richard_Stanley

This week we are celebrating in Cambridge MA , and elsewhere in the world, Richard Stanley’s birthday.  For the last forty years, Richard has been one of the very few leading mathematicians in the area of combinatorics, and he found deep, profound, and fruitful links between combinatorics and other areas of mathematics.  His works enriched and
influenced combinatorics as well as other areas of mathematics, and, in my opinion,
combinatorics matured greatly as a mathematical discipline thanks to his work.

Trivia Quiz

Correct or incorrect?

(1) Richard drove cross-country at least 8 times

(2) In his youth, at a wild party, Richard Stanley found  a proof of FLT consisting of a few mathematical symbols.

(3) Richard  jumped at least once from an airplane

(4) Richard is actively interested in the study of consciousness

(5) Richard found a mathematical way to divide by zero

 

Seven Early Papers by Richard Stanley That You Must Read.

cobcom

Richard’s Green book: Combinatorics and Commutative Algebra

Combinatorics and Commutative Algebra

(1) R. P. Stanley, The upper bound conjecture and Cohen-Macaulay rings.
Studies in Appl. Math. 54 (1975), no. 2, 135–142.

The two seminal papers (1) and (3) (below) showed remarkable and unexpected applications of commutative algebra to combinatorics. In each of these papers a central
conjecture in combinatorics was solved in a completely unexpected way which was the basis for a later remarkable theory. Paper (1) is the starting point for the interrelation between commutative algebra and combinatorics of simplicial complexes and their
topology. In this work Richard Stanley proved the Motzkin-Klee upper bound conjecture for triangulations of spheres. This conjecture asserts that the maximum number
of k-faces for a triangulation of a (d-1)-dimensional sphere with n vertices is attained by the boundary complex of the cyclic d-dimensional polytope with
n vertices. Peter McMullen proved this conjecture for simplicial polytopes and Richard Stanley proved it for arbitrary triangulations of spheres. The key point was that a certain ring (the Stanley-Reisner ring) associated with a simplicial polytope has the Cohen-Macaulay property.

The connection between combinatorics and commutative algebra is
far reaching, and in subsequent works combinatorial problems led to
developments in commutative algebra and techniques from the two areas were
combined.  A more recent important paper by Richard on applications of commutative algebra for the study of face numbers is: R. P. Stanley, Subdivisions and local h-vectors. J. Amer. Math. Soc. 5 (1992), no. 4, 805–851.

And here is, a few weeks old important development in this theory: Relative Stanley-Reisner theory and Upper Bound Theorems for Minkowski sums, by Karim A. Adiprasito and Raman Sanyal.

The Cohen-Macaulay property, magic squares and lattice points in polytopes

(2) R. P. Stanley, Magic labelings of graphs, symmetric magic squares,
systems of parameters, and Cohen-Macaulay rings. Duke Math. J. 43 (1976),
no. 3, 511–531.

This paper starts with a theorem about enumeration of certain magic squares. Solving a long-standing open problem, Stanley proved that the generating function for the
number of k by k integer matrices (k- fixed) with nonnegative entries and row sums and column sums equal to nis rational. This is the starting
point of a deep algebraic theory of integral points in polyhedra.

Enters the Hard-Lefshetz Theorem: McMullen’s g-conjecture

(3) R. P. Stanley, The number of faces of a simplicial convex polytope. Adv. in Math. 35 (1980), no. 3, 236–238.

The g-conjecture proposes a complete characterization of face numbers of d-dimensional polytopes. One linear equality that holds among face numbers is, of course, the Euler-Poincaré relation. This relation implies additional [d/2] equalities called the Dehn-Sommerville relations. Peter McMullen proposed an additional system of linear and nonlinear inequalities as a complete characterization of face numbers of polytopes. The sufficiency part of this conjecture was proved by Billera and Lee. Richard Stanley’s brilliant proof for McMullen’s inequalities that established the g-conjecture was based on the Hard Lefschetz Theorem from algebraic topology. Starting from a simplicial polytope P (with rational vertices) we associate to it a toric variety T(P). It turned out that the cohomology ring of this variety is closely related to the Stanley-Reisner ring mentioned above. The Hard Lefschetz Theorem implies an algebraic property of the Stanley-Reisner ring from which McMullen inequalities can be deduced by direct combinatorial reasoning. Richard found a number of other combinatorial applications of the Hard Lefschetz theorem (including the solution of the Erdos-Moser conjecture).

Here is the abstract of Lou Billera’s lecture

LOUIS BILLERA (CORNELL)

Even more intriguing, if rather less plausible…

The title is how Peter McMullen described his own conjectured characterization of the f-vectors of simplicial polytopes in his 1971 lecture notes on the upper bound conjecture written with Geoffrey Shephard. Yet by the end of that decade, the so-called g-conjecture would become the g-theorem, and algebraic combinatorics (as practiced at MIT) would have attracted the attention of mainstream mathematics, almost entirely due to the startling proof given by Richard Stanley.

I will briefly describe some of the events leading to this proof and some of its still developing consequences.

Enumeration

Enumeration is Richard’s true mathematical love.

 

ec1

Richard’s monumental books EC1 and EC2 (The picture is of EC1 and a young fan)

(4) A baker’s dozen of conjectures concerning plane partitions, in Combinatoire Énumérative (G. Labelle and P. Leroux, eds.), Lecture Notes in Math., no. 1234, Springer-Verlag, Berlin/Heidelberg/New York, 1986, pp. 285-293.

13 beautiful conjectures on counting plane partitions with various forms of symmetry.

(5) Generating functions, in Studies in Combinatorics (G.-C. Rota, ed.), Mathematical Association of America, 1978, pp 100-141.

For me this was the best introduction to generating functions, clear and inspiring. The entire MAA 1978 Rota’s blue little volume on combinatorics is great. Buy it!

Posets everywhere

(5) Supersolvable latticesAlgebra Universalis 2 (1972), 197-217.

This paper provides a profound link between group theory and the study of
partially ordered sets. It can be seen as a starting point of Stanley’s own work on the Cohen-Macaulay property and it had much influence on later works on combinatorial properties of lattices of subgroups by Quillen and many others, and also on the study of POSETS (=partially ordered sets) arising from arrangements of hyperplanes. The algebraic notion of supersolvable groups is translated to an important combinatorial notion for partially ordered sets. (There is a more detailed paper which I could not find online: R. P. Stanley, Supersolvable semimodular lattices. Mobius algebras (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1971), pp. 80–142. Univ. Waterloo, Waterloo, Ont., 1971.)

 Combinatorics and representation theory

(6) On the number of reduced decompositions of elements of Coxeter groupsEuropean J. Combinatorics 5 (1984), 359-372.

This paper gives an important result proved using representation theory. It is one of
many results by Stanley on connections between enumerative combinatorics,
representation theory, and invariant theory. Again, this paper represents an exciting area of research about the connection of enumerative combinatorics and representation theory that I am less familiar with.  A very inspiring survey paper is: Invariants of finite groups and their applications to combinatoricsBull. Amer. Math. Soc. (new series) 1 (1979), 475-511.

Here are abstracts of two lectures from the meeting on some recent developments in combinatorial representation theory and symmetric functions.

 

GRETA PANOVA (UCLA)

The Kronecker coefficients: an unexpected journey

Kronecker coefficients live at the intersection of representation theory, algebraic combinatorics and, most recently, complexity theory. They count the multiplicities of irreducible representations in the tensor product of two other irreducible representations of the symmetric group. While their journey started 75 years ago, they still haven’t found their explicit positive combinatorial formula, and present a major open problem in algebraic combinatorics. Recently, they were given a new role in the field of Geometric Complexity Theory, initiated by Mulmuley and Sohoni, where certain conjectures on the complexity of computing and deciding positivity of Kronecker coefficients are part of a program to prove the “”P vs NP”” problem.

We will take the Kronecker coefficients to asymptotics land and bound them. As an unexpected consequence of this trip, we find bounds for the difference of consecutive coefficients in the q-binomial coefficients (as polynomial in q), generalizing Sylvester’s unimodality theorem and connecting with results of Richard Stanley.
Joint work with Igor Pak.

THOMAS LAM (U MICHIGAN)

Truncations of Stanley symmetric functions and amplituhedron cells

Stanley symmetric functions were invented (by Stanley) with applications to the enumeration of reduced words in the symmetric group in mind. Recently, the “amplituhedron” was introduced in the study of scattering amplitudes in N=4 super Yang Mills. I will talk about a formula for the cohomology class of a (tree) amplituhedron variety as the truncation of an affine Stanley symmetric function.

Two combinatorial applications of the Aleksandrov-Fenchel inequalities;

(7)  Two combinatorial applications of the Aleksandrov-Fenchel inequalitiesJ. Combinatorial Theory (A) 31 (1981), 56-65.

In this amazing paper Stanley used inequalities of classical convexity
to settle an important conjecture on probability of events in partially
ordered sets. A special case of the conjecture was settled earlier by Ron
Graham using the FKG inequality. The profound relation between classical
convexity inequalities, combinatorial structures, polytopes, and
probability theory was further studied by many authors including Stanley
himself and there is much more to be done.

I see that I ran out of my seven designated slots. Certainly you should read Richard’s combinatorial constructions of polytopes, like Two poset polytopesDiscrete Comput. Geom. 1 (1986), 9-23, and his papers on arrangements. Let me mention a more recent paper of Stanley in this general area:   A polytope related to empirical distributions, plane trees, parking functions, and the associahedron (with J. Pitman)Discrete Comput. Geom.27 (2002), 603-634.

More

(Mostly from RS’s homepage.)

Chess and Mathematics

(12 page  PDF file) An excerpt (version of 1 November 1999) from a book Richard is writing with Noam Elkies.

An unusual method for proving the Riemann hypothesis.

Professor Eubanks in Zetaland

Richard Stanley’s Mathoverflow question on MAGIC

Magic trick based on deep mathematics

 

Richard the Catalan

(From RS’s homepage)

Excerpt (27 page PDF file) from EC2  on problems related to Catalan numbers (including 66 combinatorial interpretations of these numbers).

Solutions to Catalan number problems from the previous link (23 page PDF file).

Catalan addendum (Postscript or PDF) (version of 25 May 2013; 96 pages). An addendum of new problems (and solutions) related to Catalan numbers. Current number of combinatorial interpretations of Cn207.

The material on Catalan numbers is being collected into a monograph, to be published by Cambridge University Press in late 2014 or early 2015.

 

bgs

Posted in Combinatorics, Conferences, Happy birthday | Tagged | 3 Comments

Influence, Threshold, and Noise

 

poster4.1

My dear friend Itai Benjamini told me that he won’t be able to make it to my Tuesday talk on influence, threshold, and noise, and asked if I already have  the slides. So it occurred to me that perhaps I can practice the lecture on you, my readers, not just with the slides (here they are) but also roughly what I plan to say, some additional info, and some pedagogical hesitations. Of course, remarks can be very helpful.

I can also briefly report that there are plenty of exciting things happening around that I would love to report about – hopefully later in my travel-free summer. One more thing: while chatting with Yuval Rabani and Daniel Spielman I realized that there are various exciting things happening in algorithms (and not reported so much in blogs). Much progress has been made on basic questions: TSP, Bin Packing, flows & bipartite matching, market equilibria, and k-servers, to mention a few, and also new directions and methods. I am happy to announce that Yuval kindly agreed to write here an algorithmic column from time to time, and Daniel is considering contributing a guest post as well.

The second AMS-IMU meeting

Since the early 70s, I have been a devoted participants in our annual meetings of the Israeli Mathematical Union (IMU), and this year we will have the second joint meeting with the American Mathematical Society (AMS). Here is the program. There are many exciting lectures. Let me mention that Eran Nevo, this year Erdős’ prize winner, will give a lecture about the g-conjecture. Congratulations, Eran! Among the 22 exciting special sessions there are a few related to combinatorics, and even one organized by me on Wednsday and Thursday.

Combinatorics
Contact person: Gil Kalai, gil.kalai@gmail.com
TAU, Dan David building, Room 103
 Wed, 10:50-11:30 Van H. Vu (Yale University) Real roots of random polynomials (abstract)
Wed, 11:40-12:20 Oriol Serra (Universitat Politecnica de Catalunya, Barcelona)  Arithmetic Removal Lemmas (abstract)
 Wed, 12:30-13:10 Tali Kaufman (Bar-Ilan University)  Bounded degree high dimensional expanders (abstract)
 Wed, 16:00-16:40 Rom Pinchasi (Technion)  On the union of arithmetic progressions (abstract)
Wed, 16:50-17:30  Isabella Novik (University of Washington, Seattle) Face numbers of balanced spheres, manifolds, and pseudomanifolds (abstract)
 Wed, 17:40-18:20 Edward Scheinerman (Johns Hopkins University, Baltimore) On Vertex, Edge, and Vertex-Edge Random Graphs (abstract)
 Thu, 9:20-10:00 Yael Tauman Kalai (MSR, New England) The Evolution of Proofs in Computer Science (abstract)
 Thu, 10:10-10:50  Irit Dinur (Weitzman Institute)  Lifting locally consistent solutions to global solutions (abstract)
 Thu, 11:00-11:40 Benny Sudakov (ETH, Zurich) The minimum number of nonnegative edges in hypergraphs (abstract)

 

And now for my own lecture.

Influence, Threshold, and Noise:

Continue reading

Posted in Combinatorics, Computer Science and Optimization, Conferences, Probability, Quantum | Tagged , , , , , , , | 3 Comments

Erdős Lectures 2014 – Dan Spielman

erdos-dan

Image | Posted on by | Tagged , | 1 Comment

Answer to Test Your Intuition (22)

bundling-res

 

Indeed, most people got it right! Bundling sometimes increases revenues, sometimes keeps revenues the same, and sometimes decreases revenues. In fact, this is an interesting issue which was the subject of recent research effort. So here are a few examples as told in the introduction to a recent paper Approximate Revenue Maximization with Multiple Items by Sergiu Hart and Noam Nisan:

Example 1: Consider the distribution taking values 1 and 2, each with probability 1/2.
Let us first look at selling a single item optimally: the seller can either choose to price it
at 1, selling always and getting a revenue of 1, or choose to price the item at 2, selling it
with probability 1/2, still obtaining an expected revenue of 1, and so the optimal revenue
for a single item is 1. Now consider the following mechanism for selling both items:
bundle them together, and sell the bundle for price 3. The probability that the sum of
the buyer’s values for the two items is at least 3 is 3/4, and so the revenue is 3·3/4 = 2.25
– larger than 2, which is obtained by selling them separately.

Example 2:  For the distribution taking values 0 and 1, each with probability 1/2,
selling the bundle can yield at most a revenue of 3/4, and this is less than twice the
single-item revenue of 1/2.

Example 3 (and 4): In some other cases neither selling separately nor bundling
is optimal. For the distribution that takes values 0, 1 and 2, each with probability 1/3,
the unique optimal auction turns out to offer to the buyer the choice between any single
item at price 2, and the bundle of both items at a “discount” price of 3. This auction
gets revenue of 13/9 revenue, which is larger than the revenue of 4/3 obtained from
either selling the two items separately, or from selling them as a single bundle.  (A similar situation happens for the uniform distribution on [0, 1], for which neither bundling nor selling separately is optimal (Alejandro M. Manelli and Daniel R. Vincent [2006]).

Example 5: In yet other cases the optimal mechanism is not even deterministic and must offer lotteries for the items. This happens in the following example from a 2011 paper “Revenue Maximization in Two Dimensions” by Sergiu Hart and Phil Reny: Let F be the distribution which takes values 1, 2 and 4, with probabilities 1/6, 1/2, 1/3, respectively. It turns out that the unique optimal mechanism offers the buyer the choice between buying any one good with probability 1/2 for a price of 1, and buying the bundle of both goods (surely) for a price of 4; any deterministic mechanism has a strictly lower revenue. See also Hart’s presentation “Two (!) good to be true” Update: See also this paper by Hart and Nisan:  How Good Are Simple Mechanisms for Selling Multiple Goods?

Update: See also Andy Yao’s recent paper An n-to-1 Bidder Reduction for Multi-item Auctions and its Applications. The paper is relevant both to the issue of bundling and to the issue of using randomized mechanisms for auctions. (Test your intuition (21).)

 

 

 

Posted in Economics, Test your intuition | Tagged , , , | Leave a comment

Test your intuition (22): Selling Two Items in a Bundle.

bundle

One item

You have one item to sell and you need to post a price for it. There is a single potential buyer and the value of the item for the buyer is distributed according to a known probability distribution.

It is quite easy to compute which posted price will maximize your revenues. You need to maximize the price multiplied by the probability that the value of the item is greater or equal to that price.

Examples:

1) When the value of the item for the buyer is 10 with probability 1/2 and 15 with probability 1/2. The optimal price is 10 and the expected revenue is 10. 

2) When the value of the item for the buyer is 10 with probability 1/2 and 40 with probability 1/2. The optimal price is 40 and the expected revenue is 20. 

Two items

Now you have two items to sell and as before a single potential buyer. For each of the items, the buyer’s value behaves according to a known probability distribution. And these distributions are statistically independent.  The value for the buyer of having the two items is simply the sum of the individual values.

Now we allow the seller to post a price for the bundle of two items and he posts the price that maximizes his revenues.

In summary: The values are additive, the distributions are independent.

Test your intuition:

1) Can the revenues of a seller for selling the two items be larger than the sum of the revenues when they are sold separately?

2) Can the revenues of a seller for selling the two items be smaller than the sum of the revenues when they are sold separately?

PS: there is a new post by Tim Gowers on the cost of Elseviers journals in England. Elsevier (and other publishers) are famous (or infamous) for their bundling policy. The movement towards cheaper journal prices, and open access to scientific papers that Gowers largly initialted two years ago is now referred to as the “academic spring.”

spring

 

 

 

Posted in Economics, Test your intuition | Tagged | 1 Comment

Why Quantum Computers Cannot Work: The Movie!

Here are links to a videotaped lecture in two parts entitled “why quantum computers cannot work” recorded at the Simons Institute for the Theory of Computing on December 2013 and two additional videos: a short talk on topological quantum computers and a twelve minute overview.  Here are the links: OverviewPart IPart IITopological QC

Why Quantum Computers Cannot Work:

Overview and Vision.

Why Quantum Computers Cannot Work I:

From the “Trivial Flow” to Smoothed Lindblad Evolutions

Why Quantum Computers Cannot Work II:

Debate, Reasons to Disbelieve, and Experimentation

Why Topological Quantum Computers Cannot Work

The Geometry of Spacetime is Enabled by the Failure of Quantum Fault-Tolerance

nr2nr1

Left: Nick Read; Right The front page of Nick’s 1990 famous paper with Greg Moore on nonabelions, and below his email to me from March 2005 on topological quantum computation. (click for full view.)

nr3nr4

Left: the argument regarding topological QC demonstrated via Harris’ famous cartoon. While not strictly needed I expect the argument to extend from qubits to gates as well. Right: a recent discussion with Nick over Shtetl Optimized (click for full view). Update: We are actually not in an agreement as it seems from the above discussion (see the discussion below). 

Update: A subsequent post by Steve Flammia, Quantum computers can work in principle over The Quantum Pontiff. (July:) See also this post: Quantum future” just beyond our grasp.

Added later (April 18): Let me quote from what Steve wrote about the videos: The surprising part is the superior production value relative to your typical videotaped lecture (at least for the first overview video). Producing the videos was an interesting and demanding experience and I was certainly happy to read Steve’s description of the production value.  (Of course, the main purpose of Steve’s post was to express his disagreement with the content of the videos. See either the post or Co-‘s comment below.) 

Also there are two earlier versions of my lecture (in 1-hour format) that were videotaped. The first was taken by Jesus De Loera in Davis. Very interesting shooting-angle and interesting comments by Greg Kuperberg, Bruno Nachtergaele and other participants.  The second was taken in Seattle in a UW-PIMS colloquium lecture. Again interesting questions by several participants including James Lee and John Sidles.

(July:) The Simons Institite (almost identical) versions of the movies are now linked from the web-page of my November 15 lecture at SI.

 

Posted in Movies, Quantum | Tagged , , , | 94 Comments

Levon Khachatrian’s Memorial Conference in Yerevan

lk

Workshop announcement

Levon 7

The National Academy of Sciences of Armenia together American University of Armenia are organizing a memorial workshop on extremal combinatorics, cryptography and coding theory dedicated to the 60th anniversary of the mathematician Levon Khachatrian.  Professor Khachatrian started his academic career at the Institute of Informatics and Automation of National Academy of Sciences. From 1991 until the end of his short life in 2002 he spent at University of Bielefeld, Germany where Khachatrian’s talent flourished working with Professor Rudolf Ahlswede. Professor Khachatrian’s most remarkable results include solutions of problems dating back over 40 years in extremal combinatorics posed by the world famous mathematician Paul Erdos.  These problems had attracted the attention of many top people in combinatorics and number theory who were unsuccessfully in their attempts to solve them. At the workshop in Yerevan we look forward to the participation of invited speakers (1 hour presentations), researchers familiar with Khachatrian’s work, as well as contributed papers in all areas of extremal combinatorics, cryptography and coding theory.

The American University of Armenia (www.aua.am) is proud to host the workshop.

Workshop chair:  Gurgen Khachatrian

For any inquiries please send E-mail to: gurgenkh@aua.am

Levon 5

Posted in Combinatorics, Conferences | Tagged | 1 Comment

Navier-Stokes Fluid Computers

how-magneto-rheological-suspension-works-8947_2

Smart fluid

Terry Tao posted a very intriguing post on the Navier-Stokes equation, based on a recently uploaded paper Finite time blowup for an averaged three-dimensional Navier-Stokes equation.

The paper proved a remarkable negative answer for the regularity conjecture for a certain variants of the NS equations, namely (or, perhaps, more precisely) the main theorem demonstrates finite time blowup for an averaged Navier-Stokes equation. (This already suffices to show that certain approaches for a positive answer to the real problem are not viable.) The introduction ends with the following words.

“This suggests an ambitious (but not obviously impossible) program (in both senses of
the word) to achieve the same e ffect for the true Navier-Stokes equations, thus obtaining a negative answer to Conjecture 1.1 (the regularity conjecture for 3D NS equation)… Somewhat analogously to how a quantum computer can be constructed from the laws of quantum mechanics [Here Tao links to Benio ff's 1982 paper: "Quantum mechanical Hamiltonian models of Turing machines,"], or a Turing machine can be constructed from cellular automata such as “Conway’s Game of Life” , one could hope to design logic gates entirely out of ideal fluid (perhaps by using suitably shaped vortex sheets to simulate the various types of physical materials one would use in a mechanical computer). If these gates were sufficiently “Turing complete”, and also “noise-tolerant”, one could then hope to combine enough of these gates together to “program” a von Neumann machine consisting of ideal fluid that, when it runs, behaves qualitatively like the blowup solution used to establish Theorem 1.4.[The paper's main theorem] Note that such replicators, as well as the related concept of a universal constructor, have been built within cellular automata such as the “Game of Life.”

Once enough logic gates of ideal fluid are constructed, it seems that the main difficulties in executing the above program are of a “software engineering” nature, and would be in principle achievable, even if the details could be extremely complicated in practice. The main mathematical difficulty in executing this “fluid computing” program would thus be to arrive at (and rigorously certify) a design for logical gates of inviscid fluid that has some good noise tolerance properties. In this regard, ideas from quantum computing (which faces a unitarity constraint somewhat analogous to the energy conservation constraint for ideal fluids, albeit with the key di fference of having a linear evolution rather than a nonlinear one) may prove to be useful. (Emphasis mine.)

Interesting idea!

And what Tao does go well beyond an idea, he essentially implement this program for a close relative of the NS equation!  I am not sure if universal computing is established for these systems but the proofs of the finite-time blow up theorem certainly uses some computational-looking gadget, and also as Terry explains some form of fault-tolerance.

Somewhat related ideas (unsupported by any results, of course,) appeared in the seventh post “Quantum repetition” of my debate with Aram Harrow on quantum computing.  (See, e.g., this remark, and this one, and this one.) The thread also contains interesting links, e.g. to Andy Yao’s paper “Classical physics and the Curch-Turing Thesis.”  In addition to the interesting question:

Does the NS-equation in three-dimension supports universal (classical) computation,

we can also ask what about two-dimensions?

Can NS-equations in two dimension be approximated in any scale by bounded depth circuits?

One general question suggested there was the following: “It can be of interest (and perhaps harder compared to the quantum case) to try to describe classical evolutions that do not enable/hide fault tolerance and (long) computation.”

Another interesting comment by Arie Israel is: “I was surprised to learn that experimental fluid mechanics people had thought of this analogy before. Apparently the key name is ‘Fluidics’ and those ideas date back at least to the sixties.”

cih2

Update: Here is the first paragraph from a nice article by  Erica Klarreich entitled A Fluid New Path in Grand Math Challenge on this development in Quanta Magazine:

In Dr. Seuss’s book “The Cat in the Hat Comes Back,” the Cat makes a stain he can’t clean up, so he calls upon the help of Little Cat A, a smaller, perfect replica of the Cat who has been hiding under the Cat’s hat. Little Cat A then calls forth Little Cat B, an even smaller replica hidden under Little Cat A’s hat. Each cat in turn lifts his hat to reveal a smaller cat who possesses all the energy and good cheer of the original Cat, just crammed into a tinier package. Finally, Little Cat Z, who is too small to see, unleashes a VOOM like a giant explosion of energy, and the stain disappears.

And here is a follow up post on Tao’s blog (and a few more II, III), and a post on Shtetl Optimized.

The flip side

Update (June 14): It is worth noting that while the purpose of Tao’s program is to show finite-time blow up of the 3D Navier Stokes equations (as is often the case) these lines of ideas can potentially be useful also toward a positive solution of the regularity conjectures. Specifically, one can try to show that 3D Navier-Stokes equations do not support universal classical computation and even more specifically do not support classical fault-tolerance and error correction. Also here some analogy with quantum computation can be useful: It is expected that for adiabatic processes computation requires “spectral gap” and that gapped evolutions with local Hamiltonians support only bounded depth computation. Something analogous may apply to NS equations in bounded dimensions.

There are many caveats, of course,  the quantum results are not proved for D>1, NS equations are non-linear which weakens the analogy, and showing that the evolution does not support computation does not imply, as far as we know, regularity.

Three more remarks: 1) On the technical level an important relevant technical tool for the results on gapped systems with local Hamiltonians is the Lieb-Robinson inequality. (See, e.g. this review paper.)  2) for classical evolutions a repetition mechanism (or the “majority function”) seems crucial for robust computation and it will be interesting specifically to test of 3D Navier-stokes support it; 3) If computation is not possible beyond bounded depth this fact may lead to additional conserved quantities for NS, beyond the classical ones. (One more, June 28): It looks to me that the crucial question is if NS equations only support bounded computation or not. So this distinction captures places where circuit complexity gives clear mathematical distinctions.

Posted in Analysis, Applied mathematics, Computer Science and Optimization, Open problems | Tagged , , , , , | 11 Comments

Pictures from Recent Quantum Months

akm2

A special slide I prepared for my lecture at Gdansk featuring Robert Alicki and I as climber on the mountain of quantum computers “because it is not there.”

It has been quite a while since I posted here about quantum computers. Quite a lot happened in the last months regarding this side of my work, and let me devote this post mainly to pictures. So here is a short summary going chronologically backward in time. Last week – Michel Dyakonov visited Jerusalem, and gave here the condensed matter physics seminar on the spin Hall effect. A couple of weeks before in early January we had the very successful Jerusalem physics winter school on Frontier in quantum information. (Here are the recorded lectures.) Last year I gave my evolving-over-time lecture on why quantum computers cannot work in various place and different formats in Beer-Sheva, Seattle, Berkeley, Davis (CA), Gdansk, Paris, Cambridge (US), New-York, and Jerusalem. (The post about the lecture at MIT have led to a long and very interesting discussion mainly with Peter Shor and Aram Harrow.) In August I visited Robert Alicki, the other active QC-skeptic, in Gdansk and last June I took part in organizing a (successful) quantum information conference Qstart in Jerusalem (Here are the recorded lectures.).

And now some pictures in random ordering

2013-08-01 10.09.28

With Robert Alicki in Gdynia near Gdansk

seattle

With (from left) Connie Sidles, Yuri Gurevich, John Sidles and Rico Picone in Seattle  (Victor Klee used to take me to the very same restaurant when I visited Seattle in the 90s and 00s.) Update: Here is a very interesting post on GLL entitled “seeing atoms” on John Sidles work.

photo

With Michel Dyakonov (Jerusalem, a few days ago)

Gil+Mihai

With Michal Horodecki in Sopot  near Gdansk (Michal was a main lecturer in our physics school a few weeks ago.)

aramgil2

Aram Harrow and me meeting a year ago at MIT.

2013-08-01 10.12.45

2013-08-01 10.12.52

Sometimes Robert and I look skeptically in the same direction and other times we look skeptically in opposite directions. These pictures are genuine! Our skeptical face impressions are not staged. The pictures were taken by Maria, Robert’s wife. Robert and I are working for many years (Robert since 2000 and I since 2005) in trying to examine skeptically the feasibility of quantum fault-tolerance. Various progress in experimental quantum error-correction and other experimental works give good reasons to believe that our views could be examined in the rather near future.

QS

A slide I prepared for a 5-minute talk at the QSTART rump session referring to the impossibility of quantum fault-tolerance as a mild earthquake with wide impact.

GTprod2This is a frame from the end-of-shooting of a videotaped lecture on “Why quantum computers cannot work” at the Simons Institute for the Theory of Computing at Berkeley. Producing a videotaped lecture is a very interesting experience! Tselil Schramm (in the picture holding spacial sets of constant width) helped me with this production.

Posted in Conferences, Quantum, Updates | Tagged , , , , , , , , , | 3 Comments