FSTTCS 2021 deadline is this Monday…

The link is here. Due to the pandemic it is going to be virtual.

Quoting Bob Dylan, this blog is not dead, it is just asleep.


I have only known, by Rachel

I have only known how to tell of myself.
My world is like the ant’s, my pack
just as much burden to me,
to heavy for my frail back.

My way, like her way to the top of the tree,
is a way of pain and struggle, mocked
by a contemptuous giant hand
and maliciously blocked.

All my paths twists, are wet with tears
because of my fears of a giant hand.
Distant beacons, you have deceived me.
Why did you beckon, miraculous land?

by Rachel

For more information about Rachel, see https://en.wikipedia.org/wiki/Rachel_Bluwstein .


How to have irritating files in subdirectory…

If you are formatting a paper for lipics, but don’t want all their files in the paper directory, add the following to the top of the main latex file:


This is under the assumption that lipics/ subdirectory contains the .cls file.


biblatex on the arxiv…

It is possible to submit a paper with biblatex to the arxiv, but you need to include the relevant biblatex files in what you submit. Fortunately, there is a script that seems to work, and collect all these files:



CS UIUC is hiring in quantum computing

In addition to the hiring in theory I mentioned earlier, we are also, independently, looking for people working in Quantum Computing. In particular, we might be able to hire several people doing QC this year. So, if you are in QC and interested, then you should apply!


UIUC CS is hiring in theory

UIUC CS is hiring faculty this academic year in all areas. All areas include theory. So please apply if you are doing CS theory.

Job ad:https://cs.illinois.edu/about-us/faculty-positions.


UIUC is looking for quantum people

UIUC is looking for quantum and not necessarily quantum people to hire. See here for details.

The advertisenent on cstheory-jobs.


Radon plays the urn

In Radon’s urn there are \(n\) balls — \(r\) of them are red, and the rest are blue. In each iteration of the game is as follows:

  1. The player picks \(t\) balls out of the urn (\(t\) is a small constant, say \(4\)) [the picking is done with repetition], and let \(s\) be the number of red balls in the sample.
  2. The player returns the sample back to the urn.
  3. The player picks a random ball from the urn and replaces it with a red ball if \(s \geq 2\) and by a blue ball otherwise.

As such, the number of balls in the urn remains the same throughout the game, and we are interested in the event that all balls become blue (or all red [but that would be bad]).

Let assume that \(r\), the initial number of red balls, is quite small – say \(r \leq n/(4t^2)\).

Several questions:

  1. In expectation, how many iterations of the game one has to play till all the balls in the urn are blue?
  2. Same as above, but we want the probability of failure to be smaller than some parameter \(\psi\)?
  3. What happens if the initial number of red balls is larger, say \(r \geq 8n/t^2\)?

This problem is inspired by a similar process analyzed in the following paper (by Clarkson, Eppstein, Miller, Sturtivant, and Teng) – where Radon’s point makes a surprising appearance. (As pointed out by David Eppstein, a free version of the paper, unfortunately without the figures, is available here.)


UIUC, VPN, and ssh on linux

Recently UIUC had started requiring using vpn to ssh into computers in UIUC. After some time spent on this, here is the easiest way to work with this under linux (from my own experience – YMMV). It does not seem to require root permissions (except for installing the relevant packages).

  1. No need to use the cisco stuff. openconnect works well. Another package that is quite useful is ocyproxy. Assuming you have debian/ubuntu system, first do the following:

    sudo apt-get install openconnect ocproxy

  2. Next, you create a proxy socks port on your local computer which goes through the vpn (run this from a terminal/shell script/etc):

    echo "your_netid_password" \
           | openconnect --script-tun --script "ocproxy -D 9052" \
                              --authgroup=SplitTunnel -b \
                              --user=your_net_id --passwd-on-stdin \

  3. You need to let your ssh setup know to use this local port for ssh into your remote UIUC machine. To this end, add to the file ~/.ssh/config the following lines:

    Host yourhostname.cs.illinois.edu
      ProxyCommand nc -X 5 -x %h %p

  4. And thats it – you should be in business. Doing

    ssh yourhostname.cs.illinois.edu

    should happily connect you to your uiuc host.


Peeling a corner of the grid


Things spiral out…

I feel like a spinning top for a dreidel
The spinning don’t stop when you leave the cradle
You just slow down
Round and around this world you go
Spinning through lives of the people you know
We all slow down
— Dreidel, Don McLean


The water is rising, we must learn to swim…


I posted some new class notes on planar graphs. Naturally they contain typos etc, but hopefully they would be useful for somebody out there (or not). Anyway, they are available at the bottom of this page. The notes currently cover (i) planarity checking, (ii) grid embedding, (iii) circle packing theorem, and (iv) planar separator.


Dark times

Once you have eliminated all candidates, whoever survive would be king. That is my conclusion from reading a book on the war of the roses. A positive conclusion is how rarely democracy elects incompetent people to be head of states, while the war of the roses was caused to a large extent by having several incompetent kings. Henry VI was an infant when he became a king and was never competent. Other turns to the worst were caused by kings dying in inconvenient times. Which is another important feature of democracy – the ability to withstand a change of head of state without much turbulence

As this long and complicated sequence of battles and intrigues in a civil war unfolded, one can only wonder what the regular people thought – as all of this struggle involved only the ruling class. They lived and died just like their rulers.

The book is “The Wars of the Roses: The Fall of the Plantagenets and the Rise of the Tudors” by Dan Jones. I recommend it if you like reading history books.


Conflict-Free Coloring: The movie

There is a cute video on YouTube on conflict free coloring. See here… 


Quote from Les Misérables

One day he arrived at Senez, which is an ancient episcopal city. He was mounted on an ass. His purse, which was very dry at that moment, did not permit him any other equipage. The mayor of the town came to receive him at the gate of the town, and watched him dismount from his ass, with scandalized eyes. Some of the citizens were laughing around him. “Monsieur the Mayor,” said the Bishop, “and Messieurs Citizens, I perceive that I shock you. You think it very arrogant in a poor priest to ride an animal which was used by Jesus Christ. I have done so from necessity, I assure you, and not from vanity.”


Happy holidays 



Testing geogebra applet thingy


Discrete Geometry and ConvexityBÁRÁNY 70Budapest, June 19-23, 2017

​Discrete Geometry and Convexity

Budapest, June 19-23, 2017



UIUC CS: hiring teaching faculty 

More info here


11/28: Abstract deadline for chopped meat stuffed into membranous casing

The abstract deadline for SoCG 2017 is coming up: abstracts (at most 300 words). The submission itself is due on December 5.

May the seasoning be with you!


Quote from The Sellout

And I mean ‘nigger’ with the hard r.”

“Why, thank you, white man.”

“And do you know why there aren’t any more niggers?”

“No, sir. I don’t.”

“Because white people are the new niggers. We’re just too full of ourselves to realize it.”

“The ‘new niggers,’ you say?”

“That’s right, both me and you—niggers to the last. Disenfranchised equals ready to fight back against the motherfucking system.”

“Except that you’ll get half the jail time.”


Quote from The Sellout

Daddy told his jokes the same way he’d ordered pizza, written poetry, and written his doctoral thesis—in APA format. Following the standards of the American Psychological Association, he’d toddle onstage and open up with the oral equivalent of a Title Page. Stating his name and the title of the joke. Yes, his jokes had titles. “This joke is called ‘Racial and Religious Differences in Drinking Establishment Patronage.’” Then he’d deliver the Abstract of the joke. So instead of simply saying, “A rabbi, a priest, and a black guy walk into a bar,” he’d say, “The subjects of this joke are three males, two of whom are clergymen, one of the Jewish faith, the other an ordained Catholic minister. The religion of the African-American respondent is undetermined, as is his educational level. The setting for the joke is a licensed establishment where alcohol is served. No, wait. It’s a plane. I’m sorry, my mistake. They are going parachuting.” Finally, he’d clear his throat, stand too close to the mike, and deliver what he liked to call “The Main Body” of the joke. Comedy is war. When a comedian’s routine works, they’ve killed; if the bits fall flat, they refer to it as dying. My father didn’t die onstage. He martyred himself for that other unrecognized completely unfunny black man who, just as there must be extraterrestrial life, is out there somewhere. I’ve seen self-immolations that were funnier than my father’s routine, but there were no gongs to ring or oversized canes with which to pull him offstage. He’d just ignore the booing and segue from the punch line to the Conclusion. The Results of the joke were a smattering of coughing. A chorus of vocalized disapproval and a plethora of yawning found to be significant. He’d end with the joke’s Reference Section:

“Jolson, Al (1918). ‘Sambo and Mammy Cleared for Takeoff on Runaway 5,’ Ziegfeld Follies.

“Williams, Bert (1917). ‘If Niggers Could Fly,’ The Circuitous Chitterling Tour.

“The Unknown Minstrel (circa 1899). ‘Dem Vaudeville Peckerwoods Sho’ Am Stealing My Shit,’ The Semi-Freemason Hall, Cleveland, Ohio.

“And don’t forget to tip your waitress.”


Quote from The Sellout

“I tried to read this book, Huckleberry Finn, to my grandchildren, but I couldn’t get past page six because the book is fraught with the ‘n-word.’ And although they are the deepest-thinking, combat-ready eight- and ten-year-olds I know, I knew my babies weren’t ready to comprehend Huckleberry Finn on its own merits. That’s why I took the liberty to rewrite Mark Twain’s masterpiece. Where the repugnant ‘n-word’ occurs, I replaced it with ‘warrior’ and the word ‘slave’ with ‘dark-skinned volunteer.’”


UIUC CS is hiring this year in crypto

UIUC CS department is hiring this year in crypto. This is for a security-focused slot with interest in crypto people (both theoretical and applied). See here. Apply now while supply lasts!


Quote from East of Eden

Then the hard, dry Spaniards came exploring through, greedy and realistic, and their greed was for gold or God. They collected souls as they collected jewels. They gathered mountains and valleys, rivers and whole horizons, the way a man might now gain title to building lots. These tough, dried-up men moved restlessly up the coast and down. Some of them stayed on grants as large as principalities, given to them by Spanish kings who had not the faintest idea of the gift.


Subset sum made faster

Konstantinos and Chao have a new version of their subset sum paper on the arxiv.  They speed up  the classical subset sum algorithm by a factor of sqrt(n)  using clever divide and conquer strategy.  This version is reasonably well written and is quite elegant. A nice paper!


“I do not understand why the British government needs until October to decide whether to send the divorce letter to Brussels,” Jean-Claude Juncker, the president of the European Commission, told German television.



We shall never stay

Whatever the cost may be, we shall leave on the beaches, we shall leave on the landing grounds, we shall leave in the fields and in the streets, we shall leave in the hills; we shall never stay, and even if, which I do not for a moment believe, this Island or a large part of it were bored and without internet connection, then our Empire beyond the seas, armed and guarded by the British Fleet, would carry on the leaving, until, in God’s good time, the New World, with all its power and might, steps forth to the rescue and the liberation of the old.


Quote from The Norman Conquest

Naturally everyone answered in the affirmative, shouting out in their respective tongues, but, unfortunately, says Poitiers, the guards outside the church thought that this loud clamour was some sort of last-minute English treachery, and responded by setting fire to the nearby houses.