Today I did an Instagram Live with Mohammad H. He was the host, asking me questions. We discussed
Our lives
Blogging (which I do but he does not)
Parenting (which he does but I do not)
P vs NP (which we both care about)
Zero Knowledge and Zcash
and
How to inspire young minds (since I mentor many students, including Mohammad's 9 year old son)
The conversation is on you-tube here
Enjoy!
I will be on instragram:
We, Prof. Mohammad Hajiaghayi and Prof. William Gasarch plan to have an Instagram Live at @mhajiaghayi this SAT FEB 26, 1:30PM EDT (in English).
We talk about our lives as well as blogging, research, and how to inspire young minds. Please join if you can.
#PvsNP #blogging #youngminds #instagram
-------------------------------------
This is the answer to the problem posted in the last post which was a guest post by David Marcus. This post is also a guest post by him.
We restate the problem:
-------------------------------------------------
PICK THE LARGEST NUMBER:
There are two distinct reals in a box (how do they fit! aren't reals infinite!). They are called the first and second number.
You want to pick the larger one. You can pick one of the numbers at random and look at it
before deciding which one you want.
Is there a strategy that will win with probability > 1/2.
CLARIFICATIONS:
1) We do not want a strategy that does well on average or in the long run. Even if the games is played just once, we want the probability of winning to be > 1/2.
2) It must have prob of winning > 1/2 for EVERY pair of reals.
3) Here is an example of a strategy that does NOT work: Pick the first number with prob 1/2. If its positive then keep it, else dump it. If the numbers are{1,2} this only works half the time.
-------------------------------------------------
There is a strategy. In fact, we give two.
STRATEGY ONE
Before looking at any number, pick a number x on your own from the reals according to a distribution with full support (every open interval has prob greater than 0). Then pick a number from the box (prob 1/2-1/2), which we call y. If x<y then keep y. If y\le x then take the other number.
If x is between the two numbers, then the strategy works. If not then the strategy does not hurt, so the prob in that case is 1/2. Hence you do better than 1/2.
STRATEGY TWO
Let f: R--> (0,1) be strictly increasing. Pick a number from the box, call it y. Keep it with prob f(y).
I will be on instragram:
We, Prof. Mohammad Hajiaghayi and Prof. William Gasarch plan to have an Instagram Live at @mhajiaghayi this SAT FEB 26, 1:30PM EDT (in English).
We talk about our lives as well as blogging, research, and how to inspire young minds. Please join if you can.
#PvsNP #blogging #youngminds #instagram
-------------------------------------
(David Marcus emailed me this for a guest post, inspired by my posts on a similar problem where I gave the question here and the answer here.)
This is a well known problem, but I have learned over time that not everyone knows things that are well known.
PICK THE LARGEST NUMBER:
There are two distinct reals in a box (how do they fit! aren't reals infinite!). They are called the first and second number.
You want to pick the larger one. You can pick one of the numbers at random and look at it
before deciding which one you want.
Is there a strategy that will win with probability > 1/2.
CLARIFICATIONS:
1) We do not want a strategy that does well on average or in the long run. Even if the games is played just once, we want the probability of winning to be > 1/2.
2) It must have prob of winning > 1/2 for EVERY pair of reals.
3) Here is an example of a strategy that does NOT work: Pick the first number with prob 1/2. If its positive then keep it, else dump it. If the numbers are{1,2} this only works half the time.
(Warning: I will NOT block comments that give away the answer, so if you want to work on it without knowing the answer, do not look at comments.)
Allan Borodin turned 80 in 2021. This post is to belatedly wish him a very happy 80th, and to give a short personal perspective.
Three things come to mind when I think of Allan:
Photos from Allan’s 60th can be seen at Amos Fiat’s page.
Thank you for everything Allan, and wishing you continued robust health and enjoyment of your academic work!
I got the writing bug back while working on my recent CACM article and I'd like to try my hand at another book. Not sure the exact topic but something related to the changing nature of computing and its implications.
I'll cut down my blogging for a while. I'll still post or tweet when I have something I want to say. Bill will continue to post regularly and keep this blog active.
Bill asked me if I have time to write this book as dean but he already knew the answer. Writing keeps me sane in a world that seems less and less so.
(This post was inspired by Lance's post on Zero Knowledge, here, which was inspired by a video he has in the post which was inspired by... (I think this ordering is well founded.))
ZK= Zero Knowledge.
When it was shown that NP \subseteq ZK this was a big deal. This was by Goldreich-Micali-Wigderson (see here (FOCS-1986, JACM-1991). In the JACM paper they have the following passage:
Our result that all languages in NP have zero-knowledge proof systems, has been extended to IP, assuming the same assumptions. (The result was first proved by Impagliazzo and Yung, but since their paper [53] contains only a claim of the result, the interested reader is directed to [11] where a (different proof) appears.) In other words, whatever can be efficiently proven can be efficiently proven in a zero-knowledge manner. This may be viewed as the best result possible, since only languages having interactive proof systems can have zero-knowledge interactive proof systems.Later the papers of Lund-Fortnow-Karloff-Nisan and Shamir showed IP=PSPACE. Hence
11. BEN-OR, M., GOLDREICH, O., GOLDWASSER, S., HASTAD, J., KILLIAN, J., MICALI, S,, AND ROGAWAY, P. Everything provable is provable in zero-knowledge. In Proceedings of Advances in Cryptology— Crypto88. Lecture Notes in Computer Science, vol. 403. Springer-Verlag, New York, 1990, pp. 37-56.
53.IMPAGLIAZZO. R., AND YUNG, M. Direct minimum-knowledge computations. In C. Pomerance, ed., Proceedings of Advances in Cryptology— Crypto87. Lecture Notes in Computer Science, vol. 293. Springer-Verlag, New York, 1987, pp. 40-51.
When I realized this I thought OH, that's interesting! I then looked around the web and could not find any mention of it. I asked Lance and some people in crypto and yeah, they all knew it was true, but nobody seemed to care.
Why the apathy? Speculation:
1) ZK is a notion people actually want to use in real crypto (and there has been some progress on that lately). The prover for ZK in PSPACE has to be way to powerful to be practical. I don't really like this explanation since we are talking about theorists. Even in crypto, which has more of a connection to the real works then, say, Ramsey Theory, there are still plenty of non-useful results.
2) IP=PSPACE was the big news and had interesting proof with nice ideas. Nothing crypto-ish about it. So the corollary that PSPACE \subseteq ZK is an afterthought.
3) SAT in ZK was big news. IP in ZK is nice, but uses mostly the same ideas.
4) I am WRONG- it is a celebrated result and I somehow missed the celebration.
5) The proof that ZK is in PSPACE USES two interesting results, but adds NOTHING to the mix. In short, the proof is to easy.
Any other ideas?
Wired runs this video series where topic expert explain concepts to five levels of difficulty, typically a child, teen, undergrad, grad student and expert. UCLA professor Amit Sahai took this on for zero-knowledge.
I'd recommend the whole thing but I'd like to focus on the last segment with USC Professor Shanghua Teng (starts at 17:05). Amit nicely summed up the importance of the paper.
What was such a beautiful insight is that the idea of zero-knowledge being something that you can already predict. If you can already predict the answer, then you must not be gaining any knowledge by that interaction. This insight of being able to predict the future accurately, and that being an evidence of a lack of new knowledge.
Like Shanghua I was also assigned the seminal zero-knowledge paper by Goldwasser-Micali-Rackoff from my advisor. In many ways the original STOC paper was rough. The definitions were buggy, the examples uninspiring. Supposedly the paper didn't even get accepted into a conference in its first try. And yet as you read the paper you realize the potential, the beauty of not one but two new models that would go on to change both cryptography and complexity forever.
In the fall of 1985 when I started graduate school I took a cryptography class from Manuel Blum. Much of that class was spent on protocols that would convince you that, for example, a number was the product of three primes. By the spring of 1986, Goldreich, Micali and Wigderson distributed their paper showing, among other things, all NP problems has zero-knowledge proofs, making many of the protocols discussed in Blum's course a few months earlier trivial corollaries.
But it wasn't just zero-knowledge. Goldwasser, Micali and Rackoff (and independently Babai and Moran) developed the notion of interactive proof, a proof system with statistical confidence, a model that would lead to probabilistically checkable proofs and helping us understand the limits of approximation.
I owe most of my early research to the models developed in the GMR paper and glad that Amit has found a way to share these ideas so well.
