Amazing breakthrough in theory of computation

I learned from a colleague at JD.com that a professor Huang Hao from Emory math department made breakthrough just weeks ago in the following conjecture of Gotsman and Linial:

Given any induced subgraph G of the hypercube graph Q_n, with V(G) \geq 2^{n-1} + 1, its maximum degree is at least \sqrt{n}. This by itself is already a big deal since the previous best result by famous people like Fan Chung was on the order of \log(n), and presumably not obvious either.

Since the prof is Chinese, it was well advertised in the Chinese blogging community, though not to the extent of Yitang Zhang’s prime gap result.

The connection to other areas of complexity theory is even more remarkable, and well-exposed in the author’s original paper. In fact, I found that the subsequent advertising blogs by other mathematicians and journalists to be largely not adding much expository value.

A notion of complexity is given by the so-called sensitivity s. For a boolean function f: F_2^n \to F_2^1, where F_2 := \{0, 1\} viewed as a set, the sensitivity function is defined by s(f, x) := |\{i \in [n]: f(x^{\{i\}}) \neq f(x)\}|, where x^{\{i\}} stands for the binary vector x with the i-th coordinate flipped. In other words, point-wise sensitivity is the number of ways the function f can be perturbed by a single coordinate, or more metaphorically, the co-dimension of its null tangent space at x. Global sensitivity of f is simply s(f) := \max \{s(f, x): x \in F_2^n\}. This is a natural measure of complexity of f since if f is constant, sensitivity is clearly 0. But maybe it’s not fundamental enough to let us tackle P versus NP because for a simple function like the parity function f(x) := |\{i \in [n]: x_i = 0\}| % 2, s(f) = n already achieves maximum sensitivity.

Now the connection between sensitivity and maximum degree is proved by Gotsman and Linial in a quarter-page proof, so I encourage everyone to read it. But here is my digested version:

The following two statements are equivalent:

  1. The max degree of G and the induced subgraph on Q_n \setminus G is bounded below by h(n), provided |V(G)| \neq 2^{n-1}.
  2. The sensitivity of a boolean function f: F_2^n \to F_2 with d(f) = n satisfies s(f) >= h(n) where d(f) is the degree of f, viewed as a polynomial. More precisely, \max \{|\{i \in [n]: x_i = 1\}|: f(x) = 1\}.

To see the equivalence, simply consider the indicator function g of V(G) with domain F_2^n, multiplied by the parity function p. The degree of gp at x \in Q_n is clearly related to its sensitivity at x \in F_2^n. Indeed the parity makes so that neighbors in the original graph G change the function value.

The requirement of  |V(G)| \neq 2^{n-1} corresponds to \mathbb{E} g \neq 0, which in turn corresponds to d(f) = n. The rest should be pretty straightforward.

I will devote another post for Huang’s actual proof.

Advertisements
Posted in Uncategorized | Leave a comment

Click a form button to open a new tab in flask

Unfortunately online support for flask is somewhat limited. It is not treated as a mature web programming language. But I use it mainly for internal demo purpose, and it simplifies things tremendously. The trick is often that a technique is not specific to flask, but html in general.

It is relatively easy to redirect to a new tab with a hyperlink in html:

<a href=”google.com” target=”_blank”> my awesome link </a>

will do that.

With forms, target is a top level attribute that controls rendering of the entire form

<form target=”_blank”> … <input type=”submit” value=”submit”> … </form>

To redirect to new tab for an individual button within the form, try

<form> … <input type=”submit” value=”submit” formtarget=”_blank” > … </form>

I also found that POST actions do not support Ctrl + Click, since the target url cannot infer the POST parameters directly.

Several useful links on flask:

 

Posted in Uncategorized | Leave a comment

Healthy meal for muscle

Today I want to share some new revelation about cooking. After joining the Chinese e-commerce company for half a year, I have consumed some 200 odd lunch boxes in the Chinese street style, not to mention the extra ones I brought home for my family. While my wife seems totally complacent about the recipes, I start questioning its long term sustainability and impact on health. Some of my colleagues already reported various vital metrics at alert levels, conceivably attributable to diet. Since about a month ago, I had been taking to jogging as a way to counter the high fat/calories in the company catering. But then my left knee gave in consistently for 2 mile daily routine and I started to have some serious lifestyle change, namely little to no exercise. To be fair, I tried swimming in cold water once, and more recently I have been picking up on ab wheel, which was not a bad turn of fate either, as we shall see later. In addition, my para-radiologist for kidney CT explained to me how asian food is replete with salt, which makes joint wear hard to recover, unless I drink plenty of water. Now I am not a believer in more water the better, but rather that one should take in what’s needed. Instead of solving the salt problem with dilution, I’d rather fix the source of the problem.

Now as a father of two, husband of a shrew, I rarely have time to experiment with lifestyle outside the one prescribed by my partner, who holds deeply the belief that genetics trumps life-style and that one should carpe diem. Her own grandma exemplified this doctrine by living to the ripe age of 95 while serial-smoking until 75, and eating preserved presumably carcinogenic dried meat all throughout her life. My own grandma on my father’s side just passed away last month, at age 85, which certainly makes me more cognizant of longevity related issues than her.

After rolling out my ab wheel for a few days, I decided to do more research into the science of muscle building, and soon realize that the celebrated six-pack is a result not of muscle growth alone, but the shedding of belly fat as well. So long story short, I decided to try all chicken breast meals. On this auspicious Christmas Day evening, I finally had the opportunity to cook my own meal once, with kids and wife’s family gone for tasty Chinese food on Castro. So here comes my recipe:

  1. Prepare two pieces of chicken breasts (inorganic is fine), cut into small slices of any convenient shape
  2. Put half a teaspoon of avacado oil in a non-sticky pan and once fizzling, dump the chicken slices in with the oil, and stir until no blood is showing. Ladle out in a big dish for later reheating.
  3. Prepare the following vegetables in separate containers (feel free to swap out any with available kinds):
    1. 8 leaves of Napa, cut into thin slices
    2. one enoki mushrooms, with root discarded and the rest cut into 1 inch pieces
    3. one tomato sliced conveniently
  4. Cut two pieces of garlic into small chunks, and dump along with half a teaspoon of avacado oil, into the same empty pan, until the garlic smell comes out.
  5. Dump the enoki mushroom first into the pan, then Napa, then tomato.
  6. After vegetables look reasonable well-cooked, dump the earlier half-cooked breast in, and sprinkle some black pepper.
  7. Finally if time permit, add sprinkles of green onions, before turning off the stove in 10 seconds.

The final result is at least visually impressive, thanks to my years of experience cooking the real greasy/ingredient-rich Chinese food. I ended up eating about 3/5 of the hodge-podge, and minimal number of dirty dishes. Also don’t forget to add some carb (in my case noodle) for practical reason, and chilly pepper sauce is also imperative.

Posted in Uncategorized | Leave a comment

poetry

离离山火燎加北,

风烟南下半岛衰。

今朝喜得及时雨,

感恩难忘异乡泪。

Posted in Uncategorized | Leave a comment

on financial security

Recently I have moved out of google inc and joined jd.com. This afforded me some precious opportunity to experience both oriental and occidental cultures in depths. One thing I started thinking about is which side is the future of humanity. This is a pretty heavy topic that I cannot be completely unbiased on given my ethnic upbringing. Today I would like instead to elaborate on a small sliver of the subject, namely financial security.

There was a recent film that came out called “crazy rich asians”, as I learned on NPR. I haven’t bothered watching it. But the title caught my attention. Why are Asians known to be filthy rich? There was a story about a Beijing retiree who got hospitalized for pneumonia during the smog winter season, whose medical bill eventually cost the family all their wealth, including 2 apartment homes they owned, and all savings. By American standards, that family is already pretty well-off, at least a middle class family. On the other hands, most Americans don’t have much savings, and yet seem to live a reasonably happy life of 80 years. In China, life insurance is recently gaining popularity, because employers rarely offer coverage. From that extreme story, it seems medical bill can easily consumes a middle income family’s entire saving. The social safety net is fragile, even though normal hospital visit is much cheaper than the US.

Is US a socialist country then? By no means. But US does have better environment and much lower popularity density, even in money hubs like the Bay Area. The living space generally feels less oppressive. Financially hospital bills can usually be forgiven, unlike college loans. There are probably fewer superbugs than in China. That made up for the net worth difference with Chinese middle class.

Living in a financially stressed environment is not just bad for personal satisfaction, it affects people’s ability to do honest work. Recently NYU is giving all its junior and senior medical school students free tuition, saving each student about 200k total. I think a big  motivation is that medical students have to carry their debt into too many of their productive years, usually something like age 40, before they can breathe freely like other professions. This naturally leads to prioritizing money over satisfaction from their actual job. Corruptible behaviors easily result, such as getting paid to use certain drugs, a practice that’s common in both US and China, and being ultra-conservative (to the point of being useless) in diagnosis to avoid lawsuits. The latter is arguably universal rational behavior, but having peer doctors who went through financial distress can only make one even more cautious. After all doctors should aim for both precision and recall.

Providing a social safety net is not easy, even in a country like US. Cultural tradition plays another important role in how much one values money. In more advanced cultures like China or Jewish societies, people have grown used to the importance of money as a universal measure of success and safety, so that all biological resources tend to be devoted to its accumulation. In other words, the threshold for reaching a psychologically safe level of net-worth or income is much higher than other societies. The social cost of this is obvious: people require hoarding a much larger portion of the collective wealth in order to function properly in their roles. Such momenta can catapult certain exceptional individuals into the rank of billionaires, at which point their rudimentary yet critical functions as individual contributors in labor production inevitably get replaced by management or other leveraging roles. Thus it is very rare to find highly paid individual contributing software engineers or scientist in China. Outside google it is also rare even in the US, but I at least know quite a few individuals. All of this hierarchical spiral of productivity death is attributable to how society distracts its members from money. Christianity, academic pursuit, etc all played important roles in this distractive effort. Equally important is the ability of the society to grant its members the free will to pursue a subject of true interest, rather than based on planned economic need. Of course not all career paths should be equally profitable, but there should be a sufficient variety of them each of sufficient quantity, that can meet basic living standards free from existential worry. This is currently absent in China, and arguably also in the US, such as liberal arts majors. Perhaps the ultimate direction is for everyone to have leisure for two careers, one making serious money, another for pure personal interest. Those who truly excel at the latter should be rewarded to pursue one exclusively, while the amount of time allowed to spend on the latter should not be pro-rated by the profit it generates.

Posted in Uncategorized | Leave a comment

What can life do to me now?

I am pretty pissed by life these days. Just bought an expensive house for no good reason, only to realize there are several major problems with the new home. Now I am locked up for the next 30 years with a monthly debt close to 10k. Not exactly happy with how my career is advancing. Even though I appear productive, I do all the menial work without good understanding of the fundamentals. I am treated as an cheap overtime labor. I am probably somewhat stupid, given my defective long/short term memory. I often can’t recall things happening more than a week ago, no matter how major. I have big trouble coming up with creativity and appropriate things to say or put into slides. I have so much self-doubt that I keep postponing decision making towards the end of every project, leaving a litter of experimental flags. I wish I can study deep things more regularly and not just read the headlines, but kids and other family obligations keep me from doing that, and wife’s chastise is the main catalyst. I was never confident of my english/presentation skill anyway. I can pretend to be fluent or well-versed in front of novices or unsuspecting subjects, but get crushed instantly by people of intellectual swiftness and criticality.

Not exactly happy with my family. There is very little common things I can talk to my wife about. She isn’t into politics. Both of us have been driven to 997 work schedule due to the financial burden and sheer workload in the tech industry. Yesterday I thought about leaving the bay area, but then I will miss my dad, who is my main source of consolation.  Kid is way too hyperactive for me to handle. I cant’ even muster enough energy to save my own ass, let alone chasing kids around.

I don’t know if I am in a pit of depression at the moment. My confidence is certainly low, but that’s a perennial problem. I am swamped by the breadth and depth of multitasking imposed on me. I felt sold into a slave market that I never imagined myself getting into. I and my wife buy stuff without the ability to properly organize them. My memoryless trait often makes me buy the same thing two to three times. I never write code without copy/paste entire blocks from somewhere. I cannot retain stream of consciousness any more sometimes when I read novels, or technical report. These are worrisome signs of aging, and destroy me weekends and nights because I always have to put in extra miles than others to get things done. Never did I manage to make progress on first attempt.

So in retrospect, I made three poor decisions: 1. having kids, 2. buying that expensive house, 3. getting my parents and wife into the feud they are in now. If the 3rd one didn’t exist, I could have avoided 2 by talking to my parents before the purchase, and 1 could be solved easily by living together and taking advantage of their help. But now it’s all too late.

I know others also struggle similarly to me. But my lack of confidence and good decision making skill distinguishes myself from all the rest, since I can’t even easily communicate my problem to the outside world. On the other hand, if I get emboldened to decide on impulse always, I might have ended up in a jail already. Bankruptcy, felony charge, auto accidents. These things just seem not too far from me any more. I need some serious therapy.

Posted in Uncategorized | 1 Comment

Annotated pro-China articles I have been reading on Quora over the past year

These are in no way chronological, and if anything start from the more recent. Caveat: Quora tends to promote lots of pro-China articles simply because

  1. It is not banned in mainland China.
  2. most Chinese mainlanders are pro-PRC, because (take it as personal opinion if you will), PRC is not a mere reincarnation of Marxism or Leninism or Platonic Republicanism, it is more thoroughly soaked in Confucian Mencius tradition of universal love, order, and responsibility than the promulgation of violence, as depicted by western capitalism.
  3. China has a huge online blogging/forum presence amongst the youths.
  4. Perhaps I have expressed my sympathy towards PRC through various click throughs and hovering stances, or simply my first and last names. Personalization is quite rampant. However similar phenomenon did not occur on facebook, leaving me room for suspicion.

I am sure Quora has its own internal metric of popularity due to China or perhaps China-adjusted upvote score or click through rate, to account for the above unique phenomenon.

  1. What is your opinion about China and Chinese people?: this only angers me in terms of possible preferential treatment of foreigners compared to locals.
  2. What is it about the Chinese “One Belt, One Road” initiative (beside the economic aspect of it) that has a lot of European leaders critical of it? One said it threatens western liberalism, for example.: I do not hold fantasy about the American prospect of buying Chilean copper at 20% below market rate, since the highly partisan government has no means of justifying long term friendly gestural end. 
  3. STRIPPERS AND POLE DANCING AT FUNERALS FACES NEW CRACKDOWN IN CHINA: Colleagues of mine have expressed concern about UK government’s new law on porn site age verification. While critics are always there to tear a plan apart, it is clearly a good move to improve the overall mental wellbeing of the population. Similarly China’s overall ban on overseas pornography (and by extension, funeral strippers) helps ensure a healthy social atmosphere.
  4. How will China being caught illegally selling oil to North Korea affect relations between the United States and China after Trump complained about it?: one should never forget pass transgression of trust. Trump has clearly done a disservice of misinformation as he always has (despite the fact that I voted for him, since Hillary would likely do the same, and is far weaker physically: don’t give me the Benghazi hearing bullshit, a 3 year old can sit on a plane for 15 hours, watching 7 movies and talking the whole time.)
  5.  Don’t people in China wish to live in a democratic country?: It’s almost considered cheating (statistically shameless outlier) nowadays to bring up Trump in a debate about China v US governmental superiority. The problem is every US election since Clinton was an outlier.
  6. Why is Facebook banned in China?: I am somewhat sympathetic of the move: any secessionist move warrants military attention by the ruling party, just like during the US civil war. The mutual appreciation between Zuckerberg and Chinese populace at large suggests the ban has been at least neutrally received and lived with. Just imagine the number of idling working hours saved, despite being redirected to wechat et al. Coming to China is somewhat akin to exiting the google stratosphere, and Chinese citizens are more upset about that.
  7. What do Russians think about China?: It is humbling to know that some Russians view west as a source of hegemony. I think both constitutional capitalism and totalitarian communism can be sources of hegemony. It is historically fortunate for the two to peacefully coexist at least for now. I am more worried at the moment about the west camp, since constitutionality makes it highly inert to good changes, while China can piggyback on the western role model and media pressure, as mentioned before.
  8. Does China have cars?
  9. Why do the Chinese still care about the Nanjing massacre so much?
  10. Despite the ‘brotherly’ and ‘deep strategic’ relations China and Russia supposedly share, does China really consider Russia a potential military threat ? Why does Russia not realize this?
  11. As an Indian, how do we stop China from becoming a superpower?
  12. How many Chinese people really know about the Tiananmen incident and how many of those still support the Communist Party?
  13. Why is Duterte friendly with China even when China claims all the Spratly Islands as their territory?
  14. Why does the CPC still use anti-Japanese propaganda even though Japan is very different now than it was in 1937?: the key point is that Japan as the military extension of its fascist/genocidal past is remembered by generations of Chinese with the most bitter venom, not from significant reallocation of national resource towards propaganda, but a corollary of national propaganda on the importance of peace and anti-fascism in general.
  15. Why do Chinese citizens support the Chinese government despite its record of human rights violations?: the top answer made a salient point that no other countries will care about the well-being of its citizens more than the mother country herself, and by ways of examples, we get Iraq, Libya, Afghanistan, etc. The break-even point for an outside party to do the same amount of good as a potentially corrupt and inefficient domestic governing body is very high for the level of domestic corruption and inefficiency, and/or the level of outside patronage and altruism.
  16. What is it about Chinese society that makes China such a peaceful country?
  17. Does traditional Chinese medicine work?
  18. Why does the world allow China to rule Xinjiang?: To quote one of the answers: “The western world doesn’t care about Tibet because they want Tibet to be free, they care about it because that allows the US to place troops on China’s western plains.”
  19. Why is China being demonized?
  20. Why doesn’t China welcome refugees?: Political correctness in the US is replaced by party leader reverence. Just like west evades topic about intelligence and skull size, China reports mostly rosy aspect of lives. Both aim similarly: provide psychological safety to ordinary citizens. If I were black or native Australians and were told that skull sizes were correlated with intelligence, I would naturally feel diminished as a human being, though in modern US there are far worse things to worry about if I were in the former category, and blacks often exhibit the kind of indignant optimism found on the faces of FoxConn workers. Back from the digression, the mention of IQ requirement among refugees is something of a taboo in US, partly because academic objection to its accuracy in reflecting real intelligence, but Chinese has had big enough sample size and hardworking enough workforce to internally acknowledge the validity of such tests. The anti-muslim sentiment is also obvious. Most Chinese I talk to are pretty frank about such sentiment. This is what makes working in the US so difficult for us ex-patriots not fully educated (brain-washed) in the west: people of muslim origins are certainly among those of the highest intellectual calibers, but the religion may use some serious updates, both from the Judeo-Christian and atheist point of view.
  21. How do PRC Chinese and Americans view politics fundamentally differently?: This is a refreshing article by a (namesake) Caucasian, that brought up a sinister twist on separation of power: the separation of power from accountability. The uber example reminded me of gun control. To quote the author: “So we’ve been debating for 5 years, having strikes every year, with real dead people to prove it, and that’s all we have. Nothing else.” Indeed debate and taxonomy are the two central epithet of western progress-making. Mass social unrest has been largely kept at bay since the end of McCarthyism and social welfare is really up to the humanitarian impulse/whim of the presiding authority.

As a punchline, I won’t resist quoting one of the answers regarding Chinese attitude towards democracy:

“In the West, people use the human rights issue as an excuse to diminish the sheer amount of good the CPC has done. It is estimated that since the establishment of the People’s Republic of China in 1949, well over 800million people have been lifted out of poverty. The World Food Programme has now enlisted China as a forefront to counter world hunger.

Why does CNN not mention this?

Why does Fox not mention this?

Why is China always being trampled on?

People in China are legitimately satisfied with their current government and are proud of how China has clawed its way up from being the “Sick Child of Asia” to the world’s largest economical power using PEACEFUL means!

This means NO IMPERIALISM.

This means NO INVASION.

This means NO WAR.

The majority of the Wealth of the West was built on a foundation made up of bodies of slavery and the beaten blood of Africans, torn from their families.

The People in China Just want a peaceful and prosperous life, and the government has provided a lot of that.

Ask yourselves, is democracy really the answer to everything?”

 

Posted in Uncategorized | Leave a comment