# Democracy!

I strongly recommend playing Oiligarchy a brilliant online game about American politics from the point of view of the oil industry. You should play to the end to see which ending you get: There are four, though one of them may be unattainable. But at the very least make sure to get to a presidential election. Its depiction is memorable. (Incidentally, many other games on the website are well worth a look.)

Turning to what is unfortunately not a videogame, this time we have a candidate, let us call them candidate X, whom many think is exceptionally unqualified to be President. I disagree in an unimportant way. I am not sure X really is more unqualified, or more dangerous, than some of the other candidates in recent history, including at least one who actually became President for two terms. The one distinctive feature of X seems to be that X is more colorful and more openly arrogant than other candidates. But I don’t find this to be a substantial difference. I certainly wouldn’t mind it too much if what X said made any sense at all.

I also suspect that X and their entourage know well that the chance of X winning the election is negligible, but want to rake in and maximize publicity, according to the old dictum that there is no bad publicity.

# Bounded indistinguishability

Countless papers study the properties of k-wise independent distributions, which are distributions where any k bits are uniform and independent. One property of interest is which computational models are fooled by such distributions, in the sense that they cannot distinguish any such distribution from a uniformly random one. Recently, Bazzi’s breakthrough, discussed earlier on this blog, shows that k = polylog(n) independence fools any polynomial-size DNF on n bits.

Let us change the question. Let us say that instead of one distribution we have two, and we know that any k bits are distributed identically, but not necessarily uniformly. We call such distributions k-wise indistinguishable. (Bounded independence is the special case when one distribution is uniform.) Can a DNF distinguish the two distributions? In fact, what about a single Or gate?

This is the question that we address in a paper with Bogdanov, Ishai, and Williamson. A big thank you goes to my student Chin Ho Lee for connecting researchers who were working on the same problems on different continents. Here at NEU the question was asked to me by my neighbor Daniel Wichs.

The question turns out to be equivalent to threshold/approximate degree, an influential complexity measure that goes back to the works by Minsky and Papert and by Nisan and Szegedy. The equivalence is a good example of the usefulness of duality theory, and is as follows. For any boolean function f on n bits the following two are equivalent:

1. There exist two k-wise indistinguishable distributions that f tells apart with advantage e;

2. No degree-k real polynomial can approximate f to pointwise error at most e/2.

I have always liked this equivalence, but at times I felt slightly worried that could be considered too “simple.” But hey, I hope my co-authors don’t mind if I disclose that it’s been four different conferences, and not one reviewer filed a complaint about that.

From the body of works on approximate degree one readily sees that bounded indistinguishability behaves very differently from bounded independence. For example, one needs k = Ω(√ n) to fool an Or gate, and that is tight. Yes, to spell this out, there exist two distributions which are 0.001 √ n indistinguishable but Or tells them apart with probability 0.999. But obviously even constant independence fools Or.

The biggest gap is achieved by the Majority function: constant independence suffices, by this, while linear indistinguishability is required by Paturi’s lower bound.

In the paper we apply this equivalence in various settings, and here I am just going to mention the design of secret-sharing schemes. Previous schemes like Shamir’s required the computation of things like parity, while the new schemes use different types of functions, for example of constant depth. Here we also rely on the amazing ability of constant-depth circuits to sample distributions, also pointed out earlier on this blog, and apply some expander tricks to trade alphabet size for other parameters.

The birthday paradox is the fact that if you sample t independent variables each uniform in {1, 2,,n} then the probability that two will be equal is at least a constant independent from n when t n. the The word ”paradox” refers to the fact that t can be as small as n, as opposed to being closer to n. (Here I am not interested in the precise value of this constant as a function of t.)

The Wikipedia page lists several proofs of the birthday paradox where it is not hard to see why the n bound arises. Nevertheless, I find the following two-stage approach more intuitive.

Divide the random variables in two sets of 0.5n each. If there are two in the first set that are equal, then we are done. So we can condition on this event not happening, which means that the variables in the first set are all distinct. Now take any variable in the second set. The probability that it is equal to any variable in the first set is 0.5n∕n = 0.5n. Hence, the probability that all the variables in the second set are different from those in the first is

(1 0.5n)0.5n e0.25 < 1.

# You do not need to leave your room

You do not need to leave your room. Remain sitting at your table and listen. Do not even listen, simply wait. Do not even wait, be quiet still and solitary. The world will freely offer itself to you to be unmasked, it has no choice, it will roll in ecstasy at your feet.

In this time of emphasis on collaborative, interdisciplinary, cross-fertilizing research, I find these words by Kafka refreshing.

# How to buy a house

When I asked for a mortgage pre-approval the bank advised me to first find a house that I like, and then get back to them to prepare a pre-approval letter for the exact amount that I was going to offer. At the time I took the advice seriously, but now I can finally laugh with them at my ingenuity.

My idea of buying a house was that it is a slow process that works roughly as follows. First, you get pre-approved. Then you go to open houses, and you start making offers. If one is accepted you have a house inspection. Depending on the results, you go back to the negotiating table. After that is done, you get your mortgage, and finally you get the property. In a few years, you have made a lot of money.

This idea is completely wrong, and not only in the area where I have been looking.

First, if you need a mortgage you are already in big, big trouble. Most of the decent houses are bought for cash, even if another offer with a mortgage goes a lot higher. With a mortgage you only have access to a limited pool of problematic properties that nobody wants.

Second, the process is extremely fast. If you would like to sleep over it, the house will remain your dream house. Sales occur days or even hours after the listing is posted.

A good model for today’s buyer seems to be that of a derelict in a toxic wasteland who by chance suddenly becomes billionaire and so decides to buy real estate in various “hot spots” of which they know nothing, just in case they happen to be there one day.

Here is how the only offer I made went. First, there was absolutely no way to visit the property before the open house. And at the open house, after one hour the seller’s broker announces that bids close in thirty minutes. I actually scrambled together an offer. So hastily this was done that in hindsight I am very thankful that the seller did not even want to talk to us, despite the fact that we went over the asking price by 20%.

I have heard many calculations of the money you supposedly save by buying a house with a mortgage instead of renting. But all of these seem to omit an important point. Even if you do get the house, you will have to pay a lot more than if you had cash.

# From the Simons institute

Last year I had a great sabbatical at Harvard university, and this semester, thanks to the flexibility of the NEU administration, I am at the Simons institute in Berkeley for their program on fine-grained algorithms and complexity. The institute is amazing, and there is an avalanche of interesting talks which is overwhelming, even by Boston standards.

As with all great things, one can wonder if the institute could be made even better. Here are two small thoughts about this. The first is about housing. I think it would be nice to have a block of houses managed by the institute. And I think I would think so even if my experience with finding housing hadn’t been what it has been. The starting point is that I could not find anything that suited me. Whatever the reason for this, it was definitely *not* because of lack of support from the institute. At some point a good listing did come out, and I immediately grabbed it, but after a long exchange the landlord changed their mind. By that time it was very late in the game, and it was harder to find anything. Since I was about to spend more time looking for an apartment than actually living there, I decided to go all-out and pay a rent that is ridiculous even for someone who rented in New York city. Naturally, I ended up in a terrible place. For one thing, I happen to disagree with the landlord’s calculation that a human being needs less than 100 square feet to survive. Shame on me for not inquiring about the size of the unit. So, even if the market looked completely hopeless, I had to get back into it. Here again the institute’s staff was extremely supportive, and in a reversal of fortune they spotted an ad for a place which turned out to be fantastic.

The second is equipment. I was given a nice corner office, substantial financial support, a bike, a keyboard/mouse set, and a monitor, but not a computer. Admittedly, this is not a great loss, because setting up a new machine is almost as much hassle as bringing your own. This brings me to a point which has nothing to do with the institute, but which I’ll make here. What I would like are machines where you just need to push a button to have your exact workbench appear. This would be great even if it took a little installation time, as long as everything was automated, because you could just push that button ahead of time. Of course we do have Chromebooks, rollApp, Remote Desktop, et cetera, but none of this comes close to having your own settings. Indeed, today’s solution to the problem amounts to travelling with your own laptop — something which brings to my mind the expression “downfall of mankind.”

I am reminded of a Java project that I did during my undergraduate at La Sapienza. We had to program an application at home, and then show it to the professors in the department. My group was perhaps the only one which did not drag their own desktop computer to run the application. So much for Java. We were quite proud of showing up with just a floppy disk, until our application did in a few minutes something that had never done in days of intense domestic beta-testing.

Going back to the talks that we had, Zuckerman gave a talk about his impressive 2-source extractor with Eshan Chattopadhyay. One component of their construction is an extractor for n-bit sources where n-n0.99 bits are polylog(n)-wise independent, and the other n0.99 are an arbitrary function of the former, which answers a question raised in a paper of mine. Alexander Kulikov spoke about his better-than-3n lower bound for the circuit complexity of an explicit function, with Magnus Gausdal Find, Alexander Golovnev, and Edward Hirsch. Their strongest lower bounds are for computing extractors for degree-2 GF(2) polynomials, an object that is not currently available. And I talked about the Local Reductions developed with Jahanjou and Miles.

# The Tournament

My mother and I write fiction together. Our works have a philosophical/mathematical bent, and touch on topics such as cryptography, paradoxes, randomness, and the P vs. NP problem. We write in Italian, but we are slowly translating some works into English. Below is the first of these.  For the Italian readers, more material is available here.

The Tournament

Morning. A ray of sunlight hits me scorching hot. Through the decubitus ocular mask, squashed against my glued eyelids, I perceive a reddish wavering, a distant blown out candle. I know the way to the bathroom and I don’t need sound indicators. The light comes on as I go in, but I do not see it. I place the mask in the sterilizer, and cleanse my eyelids with a solvent based solution. In front of the mirror I try to unclench them. But I can only squint for a moment through the bars of my filamentous prison, and I see my two burned eyes, languid, back from the work for Ordesmond. A stitch on the left makes me tighten them. I wash and comb my hair by heart. I get dressed, put on the titanium glasses and enter the declimatization chamber. The door shuts behind me with a snap, and the one in front of me opens, on the world. Immersed in the dark I am engulfed by the searing heat.

Today the Tournament final begins: a DEUS (Digital Experience United Societies) delegate came to take me and he’s waiting for me downstairs.

“Good day, Dominic. Over here, please – I blindly advance towards the voice, because I want to spare my eyes.

I breathe: the air is a warm and recycled vortex that dusts me inside. Its smell of encrusted propellers and burnt plastic brings back in me distant images of the Earth, when my gaze still meandered among the burnt bodies, laid on mineral gardens, and measured the vertiginous height of the anti-radiation monoliths, sheltering under the screened mushroom-shaped pavilions.
After a step I am drenched in sweat, and I can feel the fire sky that hangs over the city. I rush inside the air-conditioned vehicle. We go through Spring boulevard and Tulip alley that I remember adorned with statues of flowers. In town there is a new epidemic: screams, hands banging against the door, a smell of rot seeps inside the cockpit.

“Did Matiasevic make it?” At the preselections I had visited his New Atlantis. What an incredible feeling to swim with palmate hands, in the cool, through underwater temples and giant seashells.

The delegate seemed regretful: “Unfortunately he has become blind. Since then is heard no more.”

We arrive at the Home Garden, location of the Tournament. In the declimatization chamber I disrobe and a water jet tones me and washes away the sweat. Then I wear the ergonomic suit. I will never get out. The delegate gently holds my hand and leads me to the building: “This is the room that we have prepared according to your wishes: 200 year old Nepalese forest air after the rain, bed tilted at 5 degrees, idroplast pillow. Now we go out. The left leads you to the Genesis hall. The second cabin on the right is yours. Anti-reflective walls, perfect lighting, and a giant active matrix screen. The dining room is over here. This is your chair. Like all of them, it has electro stimulators to keep the muscles in motion. Your breakfast is ready: carrot juice – a cold wrapping touches my left hand – bran and blueberry capsules – my right hand is on top of a pillbox.

“I present to you your colleagues: Yoko, Spiros, and Bill. This is Dominic. For any need I am at your disposal. You know the rules. I wish you good work.”

We are the four finalists for the World Tournament announced by DEUS at its first and only edition. Its purpose is to create a new home for mankind. In fact, the world is by now uninhabitable. Any form of vegetable life is dry or forced into artificial caskets, the ocean has become a boiling mire, and the only surviving animal is the Kiutcke, that lives 300 feet underground, hiding in the stalagmite forests to throw off the last hunters. Twenty billion people live on earth. They are on the brink of extinction, exasperated, prey to hunger and disease; and they besiege the city with lamentations and their rotting corpses, asking for a new life to DEUS, the masters of the world. Virtual buildings are today the only hope for mankind. For this we specialists are privileged: if we get sick we are treated in the best hospitals, our diet is varied and sometimes we even do eat meat. But we are, unfortunately, imperfect creators: you can’t live in our worlds; only DEUS has the appropriate technology to turn them into reality. And as soon as the tournament will have as winner the most accurate, comfortable, and functional of all possible worlds, there will be a mass transfer.

I started at the age of 12. It’s a devastating job. Polygon by polygon, gene by gene, quark by quark. In four dimensions, at 16384×16384. That’s why all we architects of virtual worlds are almost blind. We only use our eyes to work, as for the rest we keep them closed and bandaged. Eye drops, vitamins, cortisone injections. We grope around to our computers, and there, just there, we unwrap the eyelids as the shell of a crystal.

I take one blueberry pill, I let it slip and I have to look for it feeling around the table. I bump into a hand, soft and smooth.

“Hello – thin female voice, the sound of pearls falling into a glass bottle – I’m Yoko. Sorry, but didn’t you win the Metropolis prize last year?”

“So we have a celebrity! – Male voice – my pleasure, I am Spiros.”

He indicates the position of his hand banging it on the table. I look for him: I get an energetic handshake. Then Yoko’s adds to it, soft, with a scent of violet.

“Yoko, you are the tall and green-haired Korean? I remember a few images from the preselections …”

“I’m not. I am Japanese, short. My hair … I do not remember how I have dyed it the last time anymore. I’ll tell you when I look in the mirror.”

“I designed an egalitarian society, where everyone has the same opportunities. I’m working on it for 10 years now, it’s a great bet, the only way to ensure that life has a meaning. Certainly it’s terribly difficult to distribute resources without creating privileges. It is much easier to make unjust worlds. Like Spiros’, so to speak!”

“Wha …”

“Wait – I interrupt him – let me remember. Tall, beard, slightly receding hairline.”

“Congratulations: photographic memory.”

“You’re the one from the Ancient Greece? I remember a few screenshots.”

“Now it’s called Olympus. I added …”

“Another bit of injustice – intercalated Yoko, rather sharply.

“Better injustice than squalor. It’s better suicide rather than dying of boredom in your world.”

It was obvious that they couldn’t stand each other. Soon after, ignoring her, Spiros turned to me:

“Mine is funny, on the contrary: the gods are wandering in it, in the flesh. You can meet Diana hunting, drink with Bacchus. If you’re lucky you can become a friend of Apollo … And how is it yours?”

I was proud of my world: “It is something never seen before. Hard to describe … There are different beings, at different evolution levels. You go from primitive forms, such as the tolpo that has a hard time crawling, to super-dynamic forms, such as the tigullo that has no motion constraints: it runs, jumps, swims and flies – I smiled inside me: it was the place that I had reserved for myself. But the extraordinary novelty of Ordesmond is that it is a world in becoming: every being mutates, and it gains or loses the ability to move, depending on the degree of his mind’s development. With more or less effort, to make myself clear, taking into account the starting point. What you are inside you become outside. For example if you lie, or deceive yourself or someone else, you regress.”

“So if I understand correctly, I would fly like a hawk – said Spiros – while
Yoko, for instance, would barely crawl.”

One of us had not spoken yet. I turned my head towards the area that had not emitted sounds but just a slow and labored breath, some rubbing and chewed pills:

“And what about you? Bill, right? – I had glimpsed him at the preselections: fragile, diaphanous as if to shield himself he had lived inside a protecting suit – What world did you make?”

“Cities in space, three-dimensional. You live in orbit assisted by androids.”

Bill continued: “If I manage to finish it … My eyes are killing me.” I sympathized. I was suffering as well. Not even the Virsus, a galenic preparation of my own invention, gave me relief anymore. The first times it was enough a drop and I was able to work 16 hours straight without any pain. As a matter of fact, I was at the computer like an eagle aiming its prey. Now not even with 20 drops I was able to achieve that effect.

I’m inside my cabin, the only part of the Home Garden that I will ever see. The electro stimulators are functioning, the giant screen is on: everything is stretched towards the moment when I’ll open my eyes to work. But I remain motionless for a moment to ponder my situation, and I feel overwhelmed by anguish.

It was just as I feared. My opponents were wasting an exceptional occasion. They were building stereotyped worlds, grounded in reality, slaves of history. They brought with them the usual heavy and weak body, chained to the ground, prey to the whims of biology. Where were they when there was no shelter even at night, when the moon bombarded by the sun rays unleashed its heat against the earth? Had they not seen fish crawling like worms out from the dried out oceans? Had they not searched for the streets hidden under the corpses? Now that we finally had the chance to start all over again, with new bodies, new laws, they confined themselves to merely insignificant changes. In a few years everything would be like it is now.

I am certainly the most skilled in virtual constructions. Some of my cities have won prestigious awards. But this time my life is at stake. If Ordesmond wins a dream life is waiting for me: I will be a tigullo, virtually unlimited mutation capacity. I will fly high up in the mountains and I will dive into the depths, I will be able to assume any form at the speed of an arrow.
But if the winner was going to be a different world? What would it be the end of me?

In theory, according to the tournament rules, there can’t be exchanged favors between the contestants, in reality it’s quite different: the DEUS cannot control everything. I had to take the opportunity to dig a comfortable recess also in the others’ worlds.
Who worried me the most was Yoko, a Thomas More fanatic. I could hear her serious voice, enliven with authoritative sweetness, speaking of the need to take care in turns of the agriculture, and it was as if I saw myself already hoe in hand. Even her working methods were inflexible: methodical, straight, with the blindfold lifted to rid the face of the hair. When I get up, she’s already at the computer. She stops at 14:00 for lunch break. Resuming is at 14:30. At 22:00 she goes to bed, even if just one bit is left to finish one of her cities. One of her horrifying cities that she showed me with pride: rigorous and wide, all the same, with straightforward and flat roads that intersect. Square towns, no downtown and no suburbs, windows that frame an equal portion of green and blue, the same particle of sun. If it was her world to win I’ll ask myself what was the point to spare my eyes just to see the same view from every window. I had to convince her to do something for me, but with caution: she was just the kind of person that holds its ground.
During lunch break, while enjoying the rare white Kiutcke meat, I jokingly approached her:

“Can you build for me a house with a northern exposure, Yoko? Can I be exonerated from growing potatoes?”

She did not answer, she went to get the eye drops and then returned to work.
I had never been in Bill’s world. I wanted to examine it, but he said it was not worth the effort: “I am far behind. I guarantee that you’ll want to spare your eyes for Ordesmond. Or you will have them like mine’s that they seem glued with tar in the morning. It takes me an hour of lavations to be able to open them.” It was true, Bill was always the last to get into the cabin.

Spiros, instead, he invited me himself, perhaps because he had an admiration for me. How can I forget that walk in Ancient Greece! Under a blue sky blazing with mermaids and mermen I swam in the sea rendered calm by Zeus to allow the birth of the twins conceived with Latona. I rode a centaur among golden vines and green olives, I rested in the majestic shade of a beech, drank frothy milk from a white heifer. I visited Olympus, home of the gods. Spiros was making them one by one, Zeus the caster of lighting bolts, Hermes with winged feet. He reserved for himself the place of Apollo, the zither-player. I would have loved to be a god. But it was not the kind of favor that he could do for me: it would have required at least four months of work. I then asked him to find me a place where I could live without doing anything, revered and respected. He proposed me to be a philosopher, and I accepted. But what could I give him in return?

“You could be one squittel.”

“What do you mean?”

“Try.”

He stayed two whole minutes inside Ordesmond. When he came out I keeked to understand his reaction. A thick drool was dripping from his conjunctival sacs, but his mouth was contracted in an ecstatic grin, and yes, he accepted.

“We understand each other – commented Spiros – nothing with Yoko instead. If I knew her password I swear that I would unleash to her a proper earthquake at the cost of ruining my eyes.”

I sleep on my back, motionless. Because otherwise the blindfold slips away, and my eyes must take advantage of every drop of the ophthalmic cocktail. But tonight I cannot stay put. I’m thinking over about Spiros’ world. The silk beaches, Olympus that hides his top among the clouds. Will ever Ordesmond be able to compete?

I’m hungry, and I head towards the freezer gropingly. Turning a corner, I bump into something:

“Who are you?”

“I’m Bill, are you awake too?”

“I cannot sleep, I’m thinking about Spiros’ world.”

“Is it nice?”

“It’s divine. In my opinion it could win, and it would be a disaster. See, it has the usual things: men, women, animals. Gravity, photosynthesis, evaporation. Dust, the sky, the sea, the sun …. How long do you think it would last? In six months’ time we are in the same situation we are now. Ordesmond is different. If I win, nothing will be like before. Do you want to see it?”

“I’d like … but …”

“The eyes right? If they improve …” The last sentence came out fake, and I heard his breathing becoming labored.

He raised a hand and he put it on my shoulder: “I hope to see it soon. Now I go back to bed, but before, out of curiosity, why did you call it Ordesmond?”

“From Baudelaire – I was telegraphic, he would not understand anyway.

“Ah, Ordesmond: hors de ce monde! I love that poem.” He seemed to be smiling, and it was the first smile that I felt since when I was in the Home Garden. “I was inspired by Leibniz – continued – but I think I’ll call it a day, I can’t keep up watching. I don’t want to end up like Matiasevic.” His voice was like the muffled gasp of the Kiutcke when he gets dragged to the surface.

“Do you want to try my eye drops? They’re pretty good – I took the Virsus from my pocket – put two drops as soon as you wake up tomorrow.”

The next morning I got up early to create for Bill a place in my world, although he didn’t ask for it. I transformed him into it a triottolo, a highly evolved life form, of joyous nature, and with great freedom of movement: it could roll up, twirl, and above all, fly.
After a few minutes I heard from the ticking of Yoko’s steps that she was heading to her cabin. We were alone: now or never.

“Yoko, have you thought of a place for me, then?”

Her voice was standoffish: “You don’t need it. In my world there is room for everybody.”

“In that case you’ll be a tolpo in my world- and I started to randomly drum with my fingertips on the keyboard – A myopic first generation pedalopodus.”

“Hey! No jokes.”

But I wasn’t joking, and she understood. I remained silent, forcing her to find me just according to her sound recollection. After a collision with the other cabins she knocked on mine. A smell of violets spread around.

“Do you actually realize it or not that mine is a just world? I cannot do favors. I said no to Spiros as well. Furthermore, did you ask Bill? You don’t even know his world, but you claim a place in mine.”

“Do you want to take a look at how it feels to be a tolpo?”

She whispered: “Okay, okay: you win.”

And so I became a syphogrant, involved only in study and research. Even in her perfect world the division of labor and hierarchy existed. Satisfied, I worked very well until lunch.

“A bit better, thank you, but they still burn. This afternoon I’ll let them rest.” I remained amazed: it wasn’t possible that, having used the Virsus for the first time, he did not scream with happiness. But there was no time anymore for thoughts that were not finishing Ordesmond.

They were the last days, soon DEUS would have chosen the winner. We were all utterly exhausted and the final details were added with difficulty after increasingly longer pauses. The eyes didn’t react anymore to the relief of the eye drops: my eyelids were like sandpaper, and I was bleeding at every movement of the pupils. Errors after errors. Yoko had yet to finish the rivers and she was having a hard time building the purifiers. Spiros had to reluctantly give up Diana the huntress. I heard them arguing, while Bill’s cabin was silent: was he no longer working?

Ordesmond was practically finished, and I took a last inspection tour. The most advanced forms that I had created filled the space with joyous flights, always new patterns. Thrilling. But then I noticed that one was not flying properly. It was disharmonic, and it ended up falling to the ground.
From there he tried several times to take flight again, but it only managed to limp pathetically. When I recognized it a flash of light and terror crossed my mind: it was the triottolo in which a few days before I had turned Bill into, and it was regressing.

It was as if all of a suddden a door was opening, and this door was leading to other doors that I had never went through. Why Bill had never shown me his world? Why The Virsus had no effect?
I left Ordesmond, and rushed into the room where Bill was sleeping. I tore his blindfold off and with my fingers I separated his eyelids. With an unprecedented effort I put his eyes into focus.

He had eyes like mine when I was a child, two transparent blue globes floating in snow white eye sockets, shaded by dry and thick lashes. Only those who had never worked with worlds could have similar pupils.

I grabbed him by his neck: he hissed the password.

I limped toward the cabins. The eye pain was so intense that it seemed to damage the other senses as well. I lost my balance and started to crawl, while the irate voices of Yoko and Spiros, which were unaware, bartering favors, guided me through the depths of my nightmare.
I accessed Bill’s computer.

At first I didn’t want to believe it, so I opened my eyes widely like before an apparition. Then for hours I explored his world, I breathlessly raced on its gardens, through the enormous valleys, I climbed the monoliths and scanned the horizon, I filled every pulmonary alveolus with the swirling air. I looked for too long: when I came out (but then again did I come out?) the effort had made me completely blind. But it is no longer important.

I ran away from the Home Garden. No, no more tournament, no more life. Except the one with the Kiutckes in their underground tunnels, where gravity is so strong that you can only roll. The darkness so utter that blindness is a gift. Now even I emit their wheeze, even I run from the last hunters disguising myself in the stalagmite forests. And I whisper with Matiasevic the wonders of our worlds that will never be created. He tells me about underwater landscapes, about paths carved into the corals, leading to shimmering underwater squares, where currents give life to a golden algae shower. And I tell him about the extraordinary metamorphosis of Ordesmond, where nothing is and everything is becoming, and everyone, free from the tyranny of the flesh, endlessly continues to be reborn in new forms.

Never I will head to the surface again. I resolved this as I accessed Bill’s computer, as I cast my last glance at the world that won the Tournament, at the perfect copy of reality.

# How difficult is it to prove new lower bounds?

Two recent papers address the challenge of proving new correlation bounds for low-degree polynomials, which as depicted in a previous post are also necessary for a number of other long-standing problems, such as lower bounds for number-on-forehead communication protocols and depth-3 Majority circuits.

Nonclassical polynomials as a barrier to polynomial lower bounds, by Bhowmick and Lovett brings non-classical polynomials into the picture and shows that those polynomials of degree only log(n) are capable of various things that classical polynomials we know or conjecture are not. Consider for example the correlation between the mod 3 function on n boolean variables, and polynomials of degree d modulo 2. It has been natural to conjecture that this correlation is say super-polynomially small (less than 1/nc for every c) for degrees d up to d = n0.1, but despite substantial effort we cannot even show correlation at most 1/n for degree log(n). However, we can show exponentially small correlation bounds for degrees at most 0.1 log(n), and correlation bounds of 1/n0.1 for degrees up to n0.1, see this survey.

Bhowmick and Lovett construct a non-classical polynomial of degree O(log n) that achieves correlation 99% with the mod 3 function. What is the trick? First, suppose that my polynomial was defined modulo 1, i.e., over the torus, and that I was allowed to divide by 3. Then I could consider the polynomial p(x1, x2, …, xn) = (x1 + x2 + … + xn)/3, which has degree 1, and obtain maximum correlation 1. You can’t quite do that, but close. Non-classical polynomials are indeed defined over the torus, and allow division by powers of 2 of their integer coefficients. Basically, you can arrange things so that with polynomials of degree d you can divide by 3(1+1/2d). Setting d = O(log n) gets you close enough to a division by 3 that you obtain correlation 99%.

They also exhibit degree-O(log n) non-classical polynomials that correlate well with the majority function, and that weak-represent Or. In all cases, the polynomial is (x1 + x2 + … + xn) divided by a suitable number — the square root of n in the case of majority.

It is not clear to me how serious an obstacle this is, since as mentioned above and in their paper we can still prove vanishing correlation bounds for classical polynomials of degree O(log n), so we do have techniques that separate classical from non-classical polynomials in certain regimes. But it is refreshing to have this new viewpoint.

You can see their title and abstract following the link above. Mine would have been something like this: The power of non-classical polynomials. We show that non-classical polynomials of logarithmic degree are capable of several feats that we know or conjecture classical polynomials are not.

Anti-concentration for random polynomials by Nguyen and Vu proves that real polynomials (as opposed to polynomials modulo 2) have correlation zero (not small, but exactly zero) with the parity function, up to degree log(n)/loglog(n), improving on a degree bound of loglog(n) in this paper with Razborov. Here the polynomial is supposed to compute the parity function exactly: any non-boolean output counts as a mistake, thus making proving correlation bounds supposedly easier. Again, we can’t prove bounds of 1/n on the correlation for degree log(n), a problem which as also depicted in the previous post appears even more fundamental than correlation bounds for polynomials modulo 2 (and formally is a necessary first step).

Nguyen and Vu obtain their exponential improvement by a corresponding improvement in the anti-concentration bound in our paper, which was in turn a slight improvement over a special case of a previous result by Costello, Tao, and Vu. (Our improvement was only for the probability of hitting one element, as opposed to landing in an interval, but that was sufficient for the application.) Nguyen and Vu simultaneously improve on both results.

Whereas our proof is more or less from first principles, Nguyen and Vu use a lot of machinery that was developed in theoretical computer science, including invariance principles and regularity lemmas, and it is very cool to see how everything fits together.

Having discussed these two papers in a sequence, a natural question is whether non-classical polynomials help for exact computation as considered in the second paper. In fact, this question is asked in the paper by Bhowmick and Lovett, who conjecture that the answer is negative: for exact computation, non-classical polynomials should not do better than classical.

# Write. ArXiv. Repeat.

As discussed in earlier posts, I believe that two simple and effective ways to improve the publication process are to require that only papers available on the arxiv can be be submitted for publication and to eliminate all formatting requirements. (Throughout this blog I use the arxiv for concreteness only; several other repositories should work just as well.) In this post I want to consider a broader, radical publishing reform, and discuss several related issues.

Here’s how I would like the publication process to be:

As an author, you write your paper. When you are done, you post it on the arxiv. Period. You now move to your next paper.

Forget reverse-engineering the chronology of progress: there would now exist a unique citation for your paper: its arxix entry. Forget bibtex and its BeaST. And also forget trying to pick the best venue. Forget “are they going to invite me for the special issue? In fact, is there even going to be a special issue?” Forget the conference vs. journal debate. Forget a lengthy camera-ready production process whose goal is to put your paper in an electronic format that is only read by library computers.

Papers would be ranked by a system of badges. For starters, the badges will correspond to the current entities. So we have the STOC badge, the JACM badge, etc. We also have some badges like ECCC, which are assigned to papers that satisfy minimal requirements, such as not making sweeping unsupported claims. Badges cannot be removed but can be added. This last aspect makes the new system more flexible. Today, it is a bit funny to find out that a seminal paper appeared in an obscure venue, but it is hard to update that paper’s status. With the new system one could just add another badge.

Q: Which papers are the committees supposed to evaluate?

A: Committees will need to monitor papers like many people already do. Note that for the year 2014 the ECCC repository lists 184 reports, for the year 2013 191. These are fairly small numbers, comparable to the number of submissions to a top conference.

Q: What if a paper does not get noticed? What mechanism would there be for giving it additional chances?

A: The current default mechanism is that the author resubmits the paper, to signal that venue’s committee that they should give the paper an n+1 chance. The same can be done with the new system, for example by posting an arxiv revision with the comment “no changes from previous version”. In both systems, what prevents authors from flooding committees with resubmissions is the reputation loss, so I expect this aspect to work in roughly the same way. A more rare current mechanism is that the paper gets invited or is selected for an award. This would work in the same way in the new system.

Q: What about the cycle of getting feedback from the reviewers and revising the paper accordingly?

A: In the spirit of “only papers available on the arxiv can be be submitted for publication”, I would like the public to have access to the same information that is given to authors and referees. So I would like this cycle to take place in a public forum. If there is a serious issue with an arxiv paper, I would like to see a comment pointing this out right away, instead of having to wait for authors and referees to converge on a new version to release to the public. I also believe that the feedback/revision cycle is less prominent in theoretical fields than it is elsewhere. In other fields, it is common to receive feedback of the type: “Result X is interesting but not enough. Please run experiment Y. If you get outcome Z then we’ll talk.” With theoretical papers you hardly get a request for obtaining better results. If there is any feedback it is mostly about presentation, references, and correctness. Also, especially with conferences, it is not uncommon to get inessential feedback.

As a first step towards implementation, one could keep the publication venues as they are, but replace the cumbersome submission process with an email containing a link to the arxiv record. The production of a camera-ready version and copyright transfers are eliminated. Conferences going solo have a great opportunity to implement this first step. Alas, the Computational Complexity Conference did not quite go for it; think about it next time you get an email about an overfull hbox. Once this step is taken, one can ask if even the submission email is required.

NSF now requires its grantees to make their peer-reviewed research papers freely available within 12 months of publication in a journal. This move by NSF is the answer, at least in part, to this petition, which I signed. (Incidentally, my inability to advertise this petition through the available channels is one of the factors that eventually led me to start my own blog.) However, I don’t find this change very significant. For one thing, 12 months after the publication time is a very long time for research.

# Restricted models

Map 1



Map 2



To understand Life, what should you study?

a. People’s dreams.

b. The AMPK gene of the fruit fly.

Studying restricted computational models corresponds to b. Just like microbes constitute a wealth of open problems whose solutions are sometimes far-reaching, so restricted computational models present a number of challenges whose study is significant. For one example, Valiant’s study of arithmetic lower bounds boosted the study of superconcentrators, an influential type of graphs closely related to expanders.

The maps above, taken from here, include a number of challenges together with their relationships. Arrows go towards special cases (which are presumably easier). As written in the manuscript, my main aim was to put these challenges in perspective, and to present some connections which do not seem widely known. Indeed, one specific reason why I drew the first map was the realization that an open problem that I spent some time working on can actually be solved immediately by combining known results. The problem was to show that multiparty (number-on-forehead) communication lower bounds imply correlation bounds for polynomials over GF(2). The classic work by Hastad and Goldman does show that k-party protocols can simulate polynomials of degree k-1, and so obviously that correlation bounds for k-party protocols imply the same bounds for polynomials of degree k-1. But what I wanted was a connection with worst-case communication lower bounds, to show that correlation bounds for polynomials (survey) are a prerequisite even for that.

As it turns out, and as the arrows from (1.5) to (1.2) in the first map show, this is indeed true when k is polylogarithmic. So, if you have been trying to prove multiparty lower bounds for polylogarithmic k, you may want to try correlation bounds first. (This connection is for proving correlation bounds under some distribution, not necessarily uniform.)

Another reason why I drew the first map was to highlight a certain type of correlation bound (1.3), discussed in this paper with Razborov. It is a favorite example of mine of a seemingly very basic open problem that is, again, a roadblock for much of what we’d like to know. The problem is to obtain correlation bounds against polynomials that are real valued, with the convention that whenever the polynomial does not output a boolean value we count that as a mistake, thus making the goal of proving a lower bound presumably easier. Amazingly, the following is still open:

Prove that the correlation of the parity function on n bits is at most 1/n with any real polynomial of degree log(n).

To be precise, correlation is defined as the probability that the polynomial correctly computes parity, minus 1/2. For example, the constant polynomial 1 has correlation zero with parity — it gets it right half the times. Whereas the polynomial x1+x2+…+xn does a lot worse, it has negative correlation with parity or in fact any boolean function, just because it is unlikely that its output is in {0,1}.

What we do in the paper, in my opinion, is to begin to formalize the intuition that these polynomials cannot do much. We show that the correlation with parity is zero (not very small, but actually zero) as long as the polynomial has degree 0.001 loglog(n). This is different from the more familiar models of polynomials modulo m or sign polynomials, because those can achieve non-zero correlation even with constant degree.

On the other hand, with a simple construction, we can obtain non-zero correlation with polynomials of degree O(sqrt(n)). Note the huge gap with the 0.001 loglog(n) lower bound.

Question: what is the largest degree for which the correlation is zero?

The second map gives another slice of open problems. It highlights how superlinear-length lower bounds for branching programs are necessary for several notorious circuit lower bounds.

A third map was scheduled to include Valiant’s long-standing rigidity question and algebraic lower bounds. In the end it was dropped because it required a lot of definitions while I knew of very few arrows. But one problem that was meant to be there is a special case of the rigidity question from this work with Servedio. The question is basically a variant of the above question of real polynomials, where instead of considering low-degree polynomials we consider sparse polynomials. What may not be immediately evident, although in hindsight it is technically immediate, is that this problem is indeed a special case of the rigidity question. The question is to improve on the rigidity bounds in this special case.

In the paper we prove some variant that does not seem to be known in the rigidity world, but what I want to focus on right now is an application that such bounds would have, if established for the Inner Product function modulo 2 (IP). They would imply that IP cannot be computed by polynomial-size AC0-Parity circuits, i.e., AC0 circuits which take as input a layer of parity gates that’s connected to the input. It seems ridiculous that IP can be computed by such circuits, of course. It is easy to handle Or-And-Parity circuits, but circuits of higher depth have resisted attacks.

The question was reasked by Akavia, Bogdanov, Guo, Kamath, and Rosen.

Cheraghchi, Grigorescu, Juba, Wimmer, and Xie have just obtained some lower bounds for this problem. For And-Or-And-Parity circuits they obtain almost quadratic; the bounds degrade for larger depth but stay polynomial. Their proof of the quadratic lower bound looks nice to me. Their first moves are relatively standard: first they reduce to an approximation question for Or-And-Parity circuits; then they fix half the variables of IP so that IP becomes a parity that is “far” from the parities that are input to the DNF. The more interesting step of the argument, in my opinion, comes at this point. They consider the random variable N that counts the number of And-parity gates that evaluate to one, and they observe that the distribution of several moments of this variable is the same in the case where the parity that comes from IP is zero or one. From this, they use approximation theory to argue about the probability that N will be zero in the two cases. They get that these probabilities are also quite close, as long as the circuit is not too large, which shows that the circuit is not correctly computing IP.