2017
11.25

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.)

2017
07.12

## 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 \
vpn.cites.illinois.edu


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 127.0.0.1:9052 %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.

2017
06.21

2017
06.17

## 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

2017
06.10

2017
06.01

## Some class notes on planar graphs

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.

2017
05.26

## 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.

2017
03.02

## Conflict-Free Coloring: The movie

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

2017
02.23

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.”

2016
12.30

2016
11.27

2016
11.25

## Discrete Geometry and ConvexityBÃRÃNY 70Budapest, June 19-23, 2017

â€‹Discrete Geometry and Convexity

BÃRÃNY 70
Budapest, June 19-23, 2017

http://www.renyi.hu/conferences/barany70/

2016
11.23

2016
11.23

## 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!

2016
11.16

## 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.”

2016
11.12

## 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.”

2016
11.03

## 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.’”

2016
10.27

## 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!

2016
08.06

## 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.

2016
07.05

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!

2016
06.25

## Qoute: European Leaders Tell a Dazed Britain to Get Going on â€˜Brexitâ€™

â€œ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.

2016
06.24

## 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.

2016
06.19

## 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.

2016
05.29

## Quote from Emperor of Japan: Meiji and His World, 1852â€™1912

Describing his unhappiness over the shogunateâ€™s signing treaties with barbarians, a development for which he had no excuse to offer the gods or his ancestors, he mentioned his reluctance to send Kazunomiya, the daughter of an emperor, to a part of Japan where foreigners roamed.

2016
05.02

2016
05.01

## Exciting news on the Erdos-Szekeres convex polygon…

Exciting news on the Erdos-Szekeres convex polygon problem. arxiv.org/abs/1604.08657

2016
04.26

## Sanders to declare victory and withdraw from the D…

Sanders to declare victory and withdraw from the Democratic party.

2016
04.20

2016
04.18