Recent Comments

Recent Posts
 Mathematical Gymnastics
 Media Item from “Haaretz” Today: “For the first time ever…”
 Jim Geelen, Bert Gerards, and Geoﬀ Whittle Solved Rota’s Conjecture on Matroids
 Media items on David, Amnon, and Nathan
 Next Week in Jerusalem: Special Day on Quantum PCP, Quantum Codes, Simplicial Complexes and Locally Testable Codes
 Happy Birthday Ervin, János, Péter, and Zoli!
 My Mathematical Dialogue with Jürgen Eckhoff
 Test Your Intuition (23): How Many Women?
 Happy Birthday Richard Stanley!
Top Posts & Pages
 Believing that the Earth is Round When it Matters
 The KadisonSinger Conjecture has beed Proved by Adam Marcus, Dan Spielman, and Nikhil Srivastava
 When It Rains It Pours
 Media Item from "Haaretz" Today: "For the first time ever..."
 Why Quantum Computers Cannot Work: The Movie!
 Polymath 8  a Success!
 Aaronson and Arkhipov's Result on Hierarchy Collapse
 Happy Birthday Richard Stanley!
 Polymath 3: Polynomial Hirsch Conjecture
RSS
Answer to Test Your Intuition (22)
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 ﬁrst 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
singleitem 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 oﬀer 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 oﬀer 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 oﬀers 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 nto1 Bidder Reduction for Multiitem 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 Auctions, Noam Nisan, Sergiu Hart, Test your intuition
Leave a comment
Test your intuition (22): Selling Two Items in a 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.”
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: Overview, Part I, Part II, Topological 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 FaultTolerance
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.)
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 1hour format) that were videotaped. The first was taken by Jesus De Loera in Davis. Very interesting shootingangle and interesting comments by Greg Kuperberg, Bruno Nachtergaele and other participants. The second was taken in Seattle in a UWPIMS 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 webpage of my November 15 lecture at SI.
Posted in Movies, Quantum
Tagged Quantum computation, Quantum computers, Quantum faulttolerance, Videotaped lectures
93 Comments
Levon Khachatrian’s Memorial Conference in Yerevan
Workshop announcement
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 Email to: gurgenkh@aua.am
NavierStokes Fluid Computers
Smart fluid
Terry Tao posted a very intriguing post on the NavierStokes equation, based on a recently uploaded paper Finite time blowup for an averaged threedimensional NavierStokes 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 NavierStokes 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 effect for the true NavierStokes 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 Benioff'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 “noisetolerant”, 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 difference 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 finitetime blow up theorem certainly uses some computationallooking gadget, and also as Terry explains some form of faulttolerance.
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 CurchTuring Thesis.” In addition to the interesting question:
Does the NSequation in threedimension supports universal (classical) computation,
we can also ask what about twodimensions?
Can NSequations 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.”
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 finitetime 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 NavierStokes equations do not support universal classical computation and even more specifically do not support classical faulttolerance 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 nonlinear 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 LiebRobinson 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 Navierstokes 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.
Pictures from Recent Quantum Months
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 evolvingovertime lecture on why quantum computers cannot work in various place and different formats in BeerSheva, Seattle, Berkeley, Davis (CA), Gdansk, Paris, Cambridge (US), NewYork, 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 QCskeptic, 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
With Robert Alicki in Gdynia near Gdansk
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.
With Michel Dyakonov (Jerusalem, a few days ago)
With Michal Horodecki in Sopot near Gdansk (Michal was a main lecturer in our physics school a few weeks ago.)
Aram Harrow and me meeting a year ago at MIT.
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 faulttolerance. Various progress in experimental quantum errorcorrection and other experimental works give good reasons to believe that our views could be examined in the rather near future.
A slide I prepared for a 5minute talk at the QSTART rump session referring to the impossibility of quantum faulttolerance as a mild earthquake with wide impact.
This is a frame from the endofshooting 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 Aram Harrow, Connie Sidles, John Sidles, Michal Horodecki, Michel Dyakonov, Quantum computers, Rico Picone, Robert Alicki, Updates, Yuri Gurevich
3 Comments
Joel David Hamkins’ 1000th MO Answer is Coming
Update (May 2014): The second MO contributor to answer 1000 questions is another distinguished mathematician (and a firend) Igor Rivin.
Joel David Hamkins’ profile over MathOverflow reads: “My main research interest lies in mathematical logic, particularly set theory, focusing on the mathematics and philosophy of the infinite. A principal concern has been the interaction of forcing and large cardinals, two central concepts in set theory. I have worked in group theory and its interaction with set theory in the automorphism tower problem, and in computability theory, particularly the infinitary theory of infinite time Turing machines. Recently, I am preoccupied with the settheoretic multiverse, engaging with the emerging field known as the philosophy of set theory.”
Joel is a wonderful MO contributor, one of those distinguished mathematicians whose arrays of MO answers in their areas of interest draw coherent deep pictures for these areas that you probably cannot find anywhere else. And Joel is also a very highly decorated and prolific MO contributor, whose 999th answer appeared today!!
Here is a very short selection of Joel’s answers. To (MO founder) Anton Geraschenko’s question What are some reasonablesounding statements that are independent of ZFC? Joel answered; “If a set X is smaller in cardinality than another set Y, then X has fewer subsets than Y.” Joel gave a very thorough answer to my question on Solutions to the Continuum Hypothesis; His 999th answer is on the question Can an ultraproduct be infinite countable? (the answer is yes! but this is a large cardinal assumption.) Update: Joel’s 1000th answer on a question about logic in mathematics and philosophy was just posted.
Joel also wrote a short assay, the use and value of MathOverflow over his blog. Here it is:
The principal draw of mathoverflow for me is the unending supply of extremely interesting mathematics, an eternal fountain of fascinating questions and answers. The mathematics here is simply compelling.
I feel that mathoverflow has enlarged me as a mathematician. I have learned a huge amount here in the past few years, particularly concerning how my subject relates to other parts of mathematics. I’ve read some really great answers that opened up new perspectives for me. But just as importantly, I’ve learned a lot when coming up with my own answers. It often happens that someone asks a question in another part of mathematics that I can see at bottom has to do with how something I know about relates to their area, and so in order to answer, I must learn enough about this other subject in order to see the connection through. How fulfilling it is when a question that is originally opaque to me, because I hadn’t known enough about this other topic, becomes clear enough for me to have an answer. Meanwhile, mathoverflow has also helped me to solidify my knowledge of my own research area, often through the exercise of writing up a clear summary account of a familiar mathematical issue or by thinking about issues arising in a question concerning confusing or difficult aspects of a familiar tool or method.
Mathoverflow has also taught me a lot about good mathematical exposition, both by the example of other’s high quality writing and by the immediate feedback we all get on our posts. This feedback reveals what kind of mathematical explanation is valued by the general mathematical community, in a direct way that one does not usually get so well when writing a paper or giving a conference talk. This kind of knowledge has helped me to improve my mathematical writing in general.
So, thanks very much mathoverflow! I am grateful.
Thanks very much, Joel, for your wonderful mathoverflow answers and questions!
Amazing: Peter Keevash Constructed General Steiner Systems and Designs
Here is one of the central and oldest problems in combinatorics:
Problem: Can you find a collection S of qsubsets from an nelement set X set so that every rsubset of X is included in precisely λ sets in the collection?
A collection S of this kind are called a design of parameters (n,q,r, λ), a special interest is the case λ=1, and in this case S is called a Steiner system.
For such an S to exist n should be admissible namely should divide for every .
There are only few examples of designs when r>2. It was even boldly conjectured that for every q r and λ if n is sufficiently large than a design of parameters (n,q,r, λ) exists but the known constructions came very very far from this. … until last week. Last week, Peter Keevash gave a twenty minute talk at Oberwolfach where he announced the proof of the bold existence conjecture. Today his preprint the existence of designs, have become available on the arxive.
Brief history
The existence of designs and Steiner systems is one of the oldest and most important problems in combinatorics.
18371853 – The existence of designs and Steiner systems was asked by Plücker(1835), Kirkman (1846) and Steiner (1853).
19721975 – For r=2 which was of special interests, Rick Wilson proved their existence for large enough admissible values of n.
1985 Rödl proved the existence of approximate objects (the property holds for (1o(1)) rsubsets of X) , thus answering a conjecture by Erdös and Hanani.
1987 – Teirlink proved their existence for infinitely many values of n when r and q are arbitrary and λ is a certain large number depending on q and r but not on n. (His construction also does not have repeated blocks.)
2014 – Keevash’s proved the existence of Steiner systems for all but finitely many admissible values of n for every q and r. He uses a new method referred to as Randomised Algebraic Constructions.
Update: Just 2 weeks before Peter Keevash announced his result I mentioned the problem in my lecture in “Natifest” in a segment of the lecture devoted to the analysis of Nati’s dreams. 35:3837:09.
Update: Some other blog post on this achievement: Van Vu, Jordan Ellenberg, The aperiodical . A related post from Cameron’s blog Subsets and partitions.
Update: Danny Calegary pointed out a birdeye similarity between Keevash’s strategy and the strategy of the recent KahnMarkovic proof of the Ehrenpreis conjecture http://arxiv.org/abs/1101.1330 , a strategy used again by Danny and Alden Walker to show that random groups contain fundamental groups of closed surfaces http://arxiv.org/abs/1304.2188 .
Many Short Updates
Things in Berkeley and later here in Jerusalem were very hectic so I did not blog much since mid October. Much have happened so let me give brief and scattered highlights review.
Two “real analysis” workshops at the Simons Institute – The first in early October was on Functional Inequalities in Discrete Spaces with Applications and the second in early December was on Neoclassical methods in discrete analysis. Many exciting lectures! The links lead to the videotaped lectures. There were many other activities at the Simons Institute also in the parallel program on “big data” and also many interesting talks at the math department in Berkeley, the CS department and MSRI.
To celebrate the workshop on inequalities, there were special shows in local movie theaters
My course at Berkeley on analysis of Boolean functions – The course went very nicely. I stopped blogging about it at weak 7. Just before a lecture on MRRW upper bounds for binary codes, a general introductory lecture on social choice, and then several lectures by Guy Kindler (while I was visiting home) on the invariance principle and majority is stablest theorem. The second half of the course covered sharp threshold theorems, applications for random graphs, noise sensitivity and stability, a little more on percolation and a discussion of some open problems.
Back to snowy Jerusalem, Midrasha, Natifest, and Archimedes. I landed in Israel on Friday toward the end of the heaviest snow storm in Jerusalem. So I spent the weekend with my 90years old father in law before reaching Jerusalem by train. While everything at HU was closed there were still three duringsnow mathematics activities at HU. There was a very successful winter school (midrasha) on analytic number theory which took place in the heaviest storm days. Natifest was a very successful conference and I plan to devote to it a special post, but meanwhile, here is a link to the videotaped lectures and a picture of Nati with Michal, Anna and Shafi. We also had a special cozy afternoon event joint between the mathematics department and the department for classic studies where Reviel Nets talked about the Archimedes Palimpses.
The story behind Reviel’s name is quite amazing. When he was born, his older sister tried to read what was written in a pack of cigarettes. It should have been “royal” but she read “reviel” and Reviel’s parents adopted it for his name.
Posted in Conferences, Updates
4 Comments