Miscellaneous

• I was recently thinking about the possibility of uniformly sampling from the set of integers, the set of real numbers and (0,1). Here are two blogs I think is rather informative: Is it possible to choose an item from an infinite set of items such that each one has an equal chance of being selected?, 是否可以等可能地从实数集/正整数集中任意取一个数. Now I've been thinking about nonuniform sampling from the set of integers, clear we can do such thing on the set of real numbers (e.g. Gaussian), can we do something like that on integers? (e.g. set the probability to be geometric series). I really should take some time and read real analysis and something about measure theory based probability...


• I'm being TA for Professor Levent Tunçel's course CO471/671 Semidefinite Optimization this term (Spring 2024). In our meeting today, Levent gave me a very interesting metaphor of grading homework: The reason why grading is easier than coming up with a solution myself is exactly the same as the reason that proving a problem is in NP is easier than proving a problem is in P (building a verifier for an NP problem is easier than coming up with a poly-time algorithm for a problem in P). In this context, I--the grader--am the verifer, the problem is an instance, student's proof is a certification (witness). But there is a slight difference: With the witness, I'm only able to determine whether the statement is true or false. However the metaphor enlights me to think about the tradeoff of between the hardness of a problem and the hardness of proving it. In a sense, if the problem itself is easy, then proving it (give an algorithm) is hard for human. But if the problem is indeed hard, then proving it to be in P is immediately impossible unless P=NP so we are done. We need to put a lot of effor to prove a problem is easy! Is there a hidden principle behind this fact even though it sounds trivial?


• The Lovasz-Schrijver lift and projection method can be seen as a bridge between a terrible relaxation that we can easily solve and an exact program that is impossible to solve. It reveals the power of higher dimension, yet not so much breakthrough in this direction, nor many applications other than Lovasz's Theta function. Is there something we can do to make it widely used?