The Privacy Paradox of Rann Smorodinsky

  

The following paradox was raised by Rann Smorodinsky:

Rann Smorodinsky’s Privacy Paradox

Suppose that you have the following one-time scenario. You want to buy a sandwich where the options are a roast beef sandwich or an avocado sandwich. Choosing the sandwich of your preference (say, the avocado sandwich) adds one to your utility, but having your private preference known to the seller,  reduces by one your utility. The prior people have on your preferences is fifty-fifty.

If you choose the avocado sandwich your utility is zero, hence you can improve on this by picking each type of sandwich at random with probability 1/2. In this case your private preference remains unknown and you gain in expectation 1/2 for having the sandwich you prefer with probability 1/2.

But given this strategy, you can still improve on it by choosing the avocado sandwich.

Happy Birthday Ron Aharoni!

Ron Aharoni, one of Israel’s and the world’s leading combinatorialists celebrated his birthday last month. This is a wonderful opportunity to tell you about a few of the things that Ron did mainly around matching theory.

Menger’s theorem for infinite graphs

Hall’s marriage theorem

Hall marriage theorem (Philip Hall, 1935) gives a necessary and sufficient condition for a perfect matching in bipartite graphs. Suppose that you have a set A of n men and a set B of n women and a list of pairs of men and women that know each other. A perfect matching  is a bijection from A to B which matches every man to a woman he knows.

Hall’s marriage theorem asserts that a necessary and sufficient condition for a perfect matching is that every set S of men knows together at least |S| women.

This is an extremely important theorem and the starting point for a wonderful matching theory. It is a primary example of combinatorial duality. Other theorems of this kind are Menger’s theorem on connectivity in graphs, Dilworth’s theorem (1950) on covering posets with chains, the max-flow min-cut theorem (1956), and quite a few more.

Menger’s theorem

Menger Theorem (Karl Menger, 1927). Let G be a finite  graph and let x and y be two distinct vertices. Then the minimum number of edges whose removal disconnects x and y is equal to the maximum number of pairwise edge-disjoint paths from x to y.

Infinite Menger

Ron Aharoni and Eli Berger proved the following theorem (here is a link to the arxived version):

Aharoni and Berger Theorem (2005): Given two sets of vertices, A and B, in a (possibly infinite) digraph, there exists a family P of disjoint A to B paths, and a separating set consisting of the choice of precisely one vertex from each path in P.

A Few Mathematical Snapshots from India (ICM2010)

Can you find Assaf in this picture? (Picture: Guy Kindler.)

In my post about ICM 2010 and India I hardly mentioned any mathematics. So here are a couple of mathematical snapshots from India. Not so much from the lectures themselves but from accidental meetings with people. (Tim Gowers extensively live-blogged from ICM10.) First, the two big problems in analysis according to Assaf Naor as told at the Bangalore airport waiting for a flight to Hyderabad.  Next, a lecture on “proofs from the book” by Günter Ziegler. Then, some interesting things I was told on the bus to my hotel from the Hyderabad airport by François Loeser, and finally what goes even beyond q-analogs (answer: eliptic analogs) as explained by Eric Rains. (I completed this post  more than two years after it was drafted and made major compromises on the the quality of my understanding of the things I tell about. Also, I cannot be responsible today for the 2-year old attempts at humor.)

The two big problems in analysis according to Assaf, and one bonus problem

Karim Adiprasito: Flag simplicial complexes and the non-revisiting path conjecture

This post is authored by Karim Adiprasito

The past months have seen some exciting progress on diameter bounds for polytopes and polytopal complexes, both in the negative and in the positive direction.  Jesus de Loera and Steve Klee described simplicial polytopes which are not  weakly vertex decomposable and the existence of non weakly k-vertex decomposable polytopes for k up to about  was proved  by Hähnle, Klee, and Pilaud in the paper  Obstructions to weak decomposability for simplicial polytopes. In this post I want to outline a generalization of a beautiful result of Billera and Provan in support of the Hirsch conjecture.

I will consider the simplicial version of the Hirsch conjecture, dual to the classic formulation of Hirsch conjecture. Furthermore, I will consider the Hirsch conjecture, and the non-revisiting path conjecture, for general simplicial complexes, as opposed to the classical formulation for polytopes.

Theorem [Billera & Provan `79] The barycentric subdivision of a shellable simplicial complex satisfies the Hirsch Conjecture.

The barycentric subdivision of a shellable complex is vertex decomposable. The Hirsch diameter bound for vertex decomposable complexes, in turn, can be proven easily by induction.

This is particularly interesting since polytopes, the objects for which the Hirsch conjecture was originally formulated, are shellable. So while in general polytopes do not satisfy the Hirsch conjecture, their barycentric subdivisions always do! That was a great news!

Shellability is a strong combinatorial property that enables us to decompose a complex nicely, so it does not come as a surprise that it can be used to give some diameter bounds on complexes. Suprisingly, however, shellability is not needed at all!  And neither is the barycentric subdivision!

A simplicial complex Σ is called flag if it is the clique complex of its 1-skeleton. It is called normal if it is pure and for every face F of Σ of codimension two or more, Lk(F,Σ) is connected.

Theorem (Adiprasito and Benedetti):  Any flag and normal simplicial complex Σ satisfies the non-revisiting path conjecture and, in particular, it satisfies the Hirsch conjecture.

This generalizes the Billera–Provan result in three ways:

– The barycentric subdivision of a simplicial complex is flag, but not all flag complexes are obtained by barycentric subdivisions.

– Shellability imposes strong topological and combinatorial restrictions on a complex; A shellable complex is always homotopy equivalent to a wedge of spheres of the same dimension, and even if a pure complex is topologically nice (if, for example, it is a PL ball) it may not be shellable, as classic examples of Goodrick, Lickorish and Rudin show. Being normal still poses a restriction, but include a far wider class of complexes. For example, every triangulation of a (connected) manifold is normal, and so are all homology manifolds.

– Instead of proving the Hirsch conjecture, we can actually obtain the stronger conclusion that the complex satisfies the non-revisiting path conjecture, which for a given complex is stronger than the Hirsch conjecture.

A geometric proof of our theorem appeared in a recent paper “Metric geometry and collapsibility”  with Bruno Benedetti. . I will give here a short combinatorial proof.

Construction of a combinatorial segment

The Quantum Debate is Over! (and other Updates)

Quid est noster computationis mundus?

Nine months after is started, (much longer than expected,) and after eight posts on GLL, (much more than planned,)  and almost a thousand comments of overall good quality,   from quite a few participants, my scientific debate with Aram Harrow regarding quantum fault tolerance is essentially over. Some good food for thought, I hope. As always, there is more to be said on the matter itself, on the debate, and on other”meta” matters, but it is also useful to put it now in the background for a while, to continue to think about quantum fault tolerance in the slow pace and solitude, as I am used to, and also to move on in other fronts, which were perhaps neglected a little.

Here are the links to the eight posts: My initial post ”Perpetual Motion of The 21st Century?“ was followed by three posts by Aram. The first ”Flying Machines of the 21st Century?“ the second ”Nature does not conspire“ and the third “The Quantum super-PAC.“ We had then two additional posts ”Quantum refutations and reproofs” and ”Can you hear the shape of a quantum computer?.” Finally we had  two conclusion posts: ”Quantum repetition“ and ”Quantum supremacy or quantum control?“

EDP 22-27

We had six new posts on the Erdos Discrepancy Problem over Gowers’s blog (Here is the link to the last one EDP27). Tim contributed a large number of comments and it was interesting to follow his line of thought.  Other participants also contributed a few comments. One nice surprise for me was that the behavior of the hereditary discrepancy for homogeneous arithmetic progression in {1,2,…,n} was  found by Alexander Nikolov and  Kunal Talwar. See this post From discrepancy to privacy and back and the paper. Noga Alon and I showed that it is  and at most , and to my surprise Alexander and Kunal showed that the upper bound is the correct behavior. The argument relies on connection with differential privacy.

Möbius randomness and computation

After the -prime number theorem was proved by Ben Green, and the Mobius randomness of all Walsh functions and monotone Boolean function was proved by Jean Bourgain, (See this MO question for details) the next logical step are low degree polynomials over Z/2Z . (The Walsh functions are degree 1 polynomials.) The simplest case offered to me by Bourgain is the case of the Rudin-Shapiro sequence. (But for an ACC(2) result via Razborov-Smolensky theorem we will need to go all the way to polynomial of degree polylog.) I asked it over MathOverflaw. After three months of no activity I offered a bounty of 300 of my own MO-reputations. Subsequently, Terry Tao and Ben Green discussed some avenues and eventually Tao solved the problem (and earned the 300 reputation points). Here is a very recent post on Möbius randomness on Terry Tao’s blog.

Influences on large sets

In my post Nati’s Influence I mentioned two old conjectures (Conjecture 1 dues to Benny Chor and Conjecture 2) about influence of large sets on Boolean functions. During Jeff Kahn’s visit to Israel we managed to disprove them both. The disproof is inspired by an old construction of Ajtai and Linial.

Tel Aviv, New Haven, Jerusalem

Last year we lived for a year in Tel Aviv which was a wonderful experience: especially walking on the beach every day and feeling the different atmosphere of the city. It is so different from my Jerusalem and still the people speak fluent Hebrew. I am now in New Haven. It is getting cold and the fall colors are getting beautiful. And it also feels at home after all these years. And next week I return to my difficult and beautiful  (and beloved) Jerusalem.

Looking Again at Erdős’ Discrepancy Problem

Over Gowers’s blog Tim and I will make an attempt to revisit polymath5. Last Autumn I prepared three posts on the problems and we decided to launch them now. The first post is here. Here is a related MathOverflow question. Discrepancy theory is a wonderful theory and while I am not an expert we had several posts about it here. (This post on Beck-Fiala and related matters; and this news item on Beck’s 3-permutation conjecture.) I am aware of at least one important recent development in the theory that I did not report.  My posts go around the problem and do not attack it directly but I hope people will have a chance to think about the problem again and perhaps also about polymathing again. Meanwhile, polymath7 (over the polymath blog) is in a short recess but I hope a new research thread will start soon.

Tokyo, Kyoto, and Nagoya

Near Nagoya: Firework festival; Kyoto: with Gunter Ziegler; with Takayuki Hibi, Hibi, Marge Bayer, Curtis Green and Richard Stanly; Tokyo: Peter Frankl; crowded crossing

I just returned from a trip to Japan to the FPSAC 2012 at Nagoya and a workshop on convex polytopes in Kyoto. As in my first visit to Osaka in 1999 I found Japan stunning, and this time I was able to share the experience with my wife.

Kyoto: The week before FPSAC there was a workshop at RIMS devoted to convex polytopes. Some highlights: A classical result by Venkov and McMullen characterizes polytopes whose translates tile the Euclidean d-space.  Sinai Robins talked about his work with Nick Gravin and Dima Shiryaev about k-tilings (every point is covered k times).  Not a full characterization yet but already some impressive results. Gunter Ziegler talked about his work with Karim Adiprasito disproving an old conjecture by Shephard which asserts that there are only finitely many projectively unique d-polytopes for every dimension d. This is false above dimension 81.  Eran Nevo talked about his solution with Satoshi Murai of the generalized lower bound conjecture and some subsequent works on triangulated manifolds. There were several talks relating Ehrhard polynomials of polytopes with enumerative combinatorics,  and several talks on algebraic geometry, toric varieties, Fano varieties, and mirror symmetry. Here are the slides of my lecture entitled open problems on convex polytopes I’d love to see solved (but some further explanations for some parts are needed). I hope to return to some of the topics of the workshop in a later post.

Nagoya: FPSAC (Formal power series and algebraic combinatorics) is a central annual  combinatorial meeting with special emphasis on enumerative and algebraic combinatorics. This year it was the 24th such event although I could have swear that I took part in an FPSAC in Montreal already in 1985 but apparently this was a conference with a similar flavor and different name. Much is going on in enumerative and algebraic combinatorics. Cluster algebras, miraculously discovered a decade ago by Fomin and Zelevinsky are going strong in combinatorics as well as in other areas. Alternating sign matrices continue to offer amazing problems and answers. There were quite a few lectures on representation theory, symmetric functions, random matrices, and also on relations of enumerative combinatorics with hyperplane arrangements with polytopes and with physics. There were lectures involving massive computations and new computerized method and packages for symbolic computations  were described. Here are the slides of my lecture entitled Discrete isoperimetry: problems, results, applications and methods. The program page now contains slides for most lectures.

What are alternating sign matrices?

I suppose that you all know what a permutation matrix is (an n by n matrix with 0,1 entries and one non zero entry in each row and each column) and alternating sign matrices are amazing generalization of permutation matrices discovered by William Mills, David Robbins, and Howard Rumsey. (See also this article by Bressoud and Propp) They are integral n by n matrices with 0,1 and -1 entries. In every row and every columns  the non zero aliments (and there must be at least one such element)  should alternate between 1 and -1 and start and end with a ’1′. Alternating sign matrices are in one to one correspondence with monotone triangle. Thos are triangles of integers starting with a row: 1,2,…,n. With the following rules: (a) all rows are strictly increasing; (b) every element in row i is weakly between the two elements above it.

The amazing thing is that the number of alternating sign matrices of order n is precisely

1!4!7!…(3n-2)!/n!(n+1)!…(2n-1)!

This was a conjecture by Mills, Robbins and Rumsey and it took over a decade until it was proved by Doron Zeilberger. Later Greg Kuperberg found a short proof and by now several proofs are known. If you have some information or ideas on alternating sign matrices that you would like to share or some questions about them, or about anything else, please contribute a comment.

A Weak Form of Borsuk Conjecture

Problem: Let P be a polytope in with n facets. Is it always true that P can be covered by n sets of smaller diameter?

 

I also asked this question over mathoverflow, with some background and motivation.

Some Updates

Jeff Kahn was in town: so we worked together also with Ehud Friedgut and Roy Meshulam (and others) quite intensively. Very nice! Stay tuned for a report!

Polynomial Hirsch conjecture (polymath3): While the conjecture remains wide open there are some interesting developments. The conjecture asserts that the diameter of every d-dimensional polytope with n facets is at most polynomial in d and n. Jesus de Loera and Steve Klee described simplicial polytopes which are not  weakly vertex decomposable and the existence of non weakly k-vertex decomposable polytopes for k up to about was proved  by Hähnle, Klee, and Pilaud in the paper  Obstructions to weak decomposability for simplicial polytopes. Karim Adiprasito and Bruno Benedetti proved the Hirsch conjecture for flag polytopes (and manifolds) using CAT(0) methods. Karim will write a guest blog post about it. Stay tuned.

Erdos discrepancy problem (polymath5): Tim Gowers and I have a plan to try soon to revive the EDP project at least for a short while. We plan 3 posts about it in the second half of August over Tim’s blog. Update: The first post EDP22 just appeared.

Polymath7 is going strong on the polymath blog.

Quantum computer debate with Aram Harrow: The most recent post was entitled Can you hear the shape of a quantum computer? Quite an interesting discussion, also on the Quantum pontiff.

“Gold open access” new Forum: See the post and extensive discussion over Gowers’s blog (and also on Tao’s blog).

Telling spheres: Joel Hass was in town and gave a talk about a recent work with Greg Kuperberg: Telling if a 3-manifolds  is a sphere is in co-NP (assuming GRH). This extends Greg’s work on telling unknots. Topology, provides remarkable questions in NP and coNP where proving both sides are hard. My claim to fame is replacing Joel in grading an exam in 1986 (or so) when he got married!

High dimensional expander. My course with Alex Lubotzky on high dimensional expanders ended. A lot of nice things to tell about and we learned quite a few new things. Roy Meshulam concluded his course with a crystal clear lecture on Garland’s method. Maybe we will teach it again after a year break. Meanwhile, Ori Parzanchevski promised me to write something about some recent developments over here. Stay tuned for that too.

16th Midrasha Mathematicae: Our yearly midrasha ran by Aner Shalev was devoted to Words and Growth. Delicious approximate groups and word maps were observed!

Interactive quantum lecture: We had an unususal quantum seminar presentation by Michael Ben-Or on the work A multi-prover interactive proof for NEXP sound against entangled provers by Tsuyoshi Ito and Thomas Vidick. Michael ran Vidick’s videotaped recent talk on the matter and from time to time he and Dorit acted as a pair of prover and the other audience as verifier. (Michael was one of the authors of the very first paper introducing multi-prover interactive proofs.)

Peter Frankl: I plan on meeting Peter on Friday. Will report.

Eyal Sulganik: Towards a Theory of “Mathematical Accounting”

The following post was kindly contributed by Eyal Sulganik  from IDC (Interdiciplinary Center)  Herzliya. Eyal was motivated by our poll on certainty “beyond a reasonable doubt,” which is related to several issues in accounting.

Mathematicians, I believe, are always looking for new areas where their models and concepts can make a difference. Physics, Economics, CS, Biology are just some examples, surely not exhausting a longer list of such areas. Although the origins of accounting emanate from mathematicians (for example: L. Pacioli, and even  A. Cayley found interest in it), it is a fact,  though not unexplained,  that these days  (almost) no mathematicians are interested in accounting and there is no field of “mathematical accounting”.  In the following few paragraphs I would like to thus draw attention to accounting as a possible field for mathematicians. Surprisingly, a possibly “profitable field”. I believe that accounting can be subject, inter-alia, to use of theories of Formal Systems, Information Theory, Voting  theory, Fuzzy Logic, Graph theory and even Catastrophe theory. In brief, accounting (Financial Reporting) deals with the measurement and reporting of economic events .  As such, it is a measurement system interlaced with an information system. (Results such as Blackwell theorem on the comparison of information systems are of relevance).

Financial reporting of firms, the lifeline of the Capital Markets, is dictated by “reporting standards”. Those reporting standards are determined by “standard boards” (according to voting rules and procedures, which are very interesting for analysis)  and interpreted and evolve over time (as is the case with other languages).   The reports are audited by accounting firms.  Auditing theory became more sophisticated  but even fairly standard tools like Benford Law are not yet routine.

Moreover, a huge debate centers on whether to adopt a rule-based system where “every” possible scenario is prescribed in advance or whether to adopt a principle based system which gives” freedom” to every reporting entity in reflecting the economic substance of an event.

It is well known that a rule-based systems provide greater comparability (between firms), but at the same time, as they are more rigid and make use of “bright lines”,  can be more easily forced to reflect form over substance . Indeed, Bright line Accounting rules are not continuous functions and hence small changes in the description or design of an event can lead to enormous differences in the reported values. For example, given that the definition of “CONTROL” was based on a “50% legal test” ,until recently it was the case that  if company A was holding 50.01% of the shares of company B (other holders being each  much smaller)  and sold only  1.02% it could recognize a profit, due to “loss of control”,  as though it sold the whole holding and bought back 49.01%. Needless to say that although holding “only” 49.01% , A CONTROLs B (Danny Ben Shahar, Desmond Tsang and Myself are in the process of demonstrating that “accounting theory of control” is inconsistent with Shapley Value).

Principle based systems, on the other hand, must make sure that its principles are common knowledge. For example, if a provision for loss regarding a claim against a firm depends on the chances of loss being “Probable” or  “remote” or “reasonably possible” a question arises what the preparers and users of the financial statements think about those terms. Many years ago, me and my colleague Yossi Aharoni found out-through questionnaires- that different types of agents have different probabilistic interpretations to those terms and we explained the mis-communication it can cause. I attach two simple papers (one co-authored with Danny Ben Shahar, the other one in hebrew),  that can shed some more light on the above point of view and I dare state a wish that a new field of “mathematical accounting” will be created .