Asked why his charge failed, General Pickett replied: “I’ve always thought the Yankees had something to do with it.” en.wikipedia.org/wiki/Pickett%2…

# Sariel

## June 15, 2015

SoCG 2015 proceeding available online – free & beautiful formatting (much better than previous years). drops.dagstuhl.de/portals/extern…

# SoCG 2015 Proceedings…

Are now available online for free, well before the conference.

The formatting is much nicer than the ACM formatting, and the usual formatting used in theory conferences proceedings. Yet another reason to move away from ACM/IEEE.

# The polygonal porcupine and the crazy eyes

# Sariel

## May 25, 2015

Enabling tracking protection on firefox speeds up browsing: news.slashdot.org/story/15/05/25…

and here is how to enable it:

support.mozilla.org/en-US/kb/track…

# Sariel

## May 5, 2015

Kent shootings, roughly 45 years ago. en.wikipedia.org/wiki/Kent_Stat…

# Sariel

## May 5, 2015

A wild ride for one Illinois computer science student from high school dropout to graduation engineering.illinois.edu/news/article/1…

# Sariel

## April 20, 2015

Congratulations professor Raichel sarielhp.org/blog/?p=8868

# Congratulations professor Raichel

My soon to be ex-student Ben Raichel is joining the CS department in UT Dallas.

# Sariel

## April 18, 2015

T-Shirt weather, sunny, green. Unwhining about spring time.

# The latest referee report I got…

The results in this paper are known and obvious, on a new strange problem that the authors define but nobody cares about. Thus, one must conclude that the authors wrote the paper just because they like the clicking sounds made by the keyboard as they typed their paper. Also, all the words used in the paper can be found in a dictionary, so there is nothing new in this paper.

[I did rephrase the report a bit, and I am happy I helped making the conference more selective. Mark me as being amused.]

# Sariel

## April 11, 2015

Money-ball in the NBA…

nytimes.com/2015/04/12/mag…

# Set cover via increasing weights

Somebody asked this on Theory stack exchange and then deleted the question after I answered it (I assume it is a standard homework problem). Since I liked the problem, here is the question and answer.

Given a set system \((S,F)\) with \(n = |S|\) elements, and \(m=|F|\) sets, consider the algorithm that starts with all the elements having weight \(1\). At every iteration, the algorithm picks the heaviest set (taking into account the weight of all the elements – not only the uncovered ones as in the standard greedy algorithm). Next, the algorithm doubles the weight of all the uncovered elements. Question: What is the approximation quality of this algorithm?

The answer:

The trick is to divide the weight of the covered elements in every iterations instead of multiplying the weight of the uncovered elements. Clearly, up to a scaling by a factor of two, the two operations are equivalent, and in particular this preserve the relative order of the sets. Observe, that an uncovered element has weight \(1\) till it is covered for the first time. In particular, let \(W_0 = |n|\), and let \(W_i\) be the total weight of \(S\) in the beginning of the \(i\)th iteration. Let \(x_i\) be the weight of the set picked in the \(i\)th iteration, and observe that \(x_i \geq W_i/k\), where \(k\) is the number of sets in the optimal solution. Furthermore, \(W_{i+1} \leq W_i – x_{i}/2 \leq (1-1/2k) W_i\), as the weight of the elements of the set covered in the \(i\)th iteration get their weight halved. We conclude that \(W_{O(k \log n)} <1\), which implies that all the elements are covered in the end of the \(O( k \log n)\) iteration. Thus, this is \(O( \log n)\) approximation.

# Sariel

## April 9, 2015

Spend hours making your spam filter better, and then when you want spam to test it, no spam arrives.

# Sariel

## April 5, 2015

A cute brain teaser… io9.com/this-puzzle-is…

# Sariel

## April 1, 2015

Fracking joice! wonkette.com/581472/nebrask…

# Sariel

## April 1, 2015

gscholar-bibtex extension for emacs works well. melpa.org/?utm_source=dl…

# Sariel

## March 31, 2015

My book is now available for “free” on the internet. They did a good job scanning the book in color… bookzz.org/book/2327006/f…

# Sariel

## March 30, 2015

“Thank you for scheduling your payment.”

“No, no, thank you for taking my money!”

# Sariel

## March 16, 2015

More on Jirka Matousek. kam.mff.cuni.cz/Matousek-obitu…

# Sariel

## March 12, 2015

Terry Pratchett had died. bbc.com/news/entertain…

# Sad news

Jirka Matousek had died yesterday (Monday, March 9, 2015) after a long illness at age 52. Today would have been his birthday. Not only was Jirka an amazing researcher, but he had written several important books, from his wonderful book on discrepancy, to his equally great book on discrete geometry, to his book on the Borsuk-Ulam theorem, and his (coauthored) introductory book on discrete math. See his webpage for more information about his books and papers.

I feel inadequate to summarize Jirka’s research. From his work on partitions trees, discrepancy, embeddings, topology, linear-programming, derandomization, cuttings, approximation algorithms, discrete geometry and much much more.

Quoting from the email I got with this sad news: “He will further live with us through our memories and in his excellent books and papers.”

May he rest in peace.

# Sariel

## March 9, 2015

There should be an expression describing the undertaking of bounding a constant till it can no longer breath, and it is ready to serve.

# Sariel

## March 4, 2015

2+2=5. Mostly because of rounding errors.

# Sariel

## March 3, 2015

Weather app I use is going through hard times. Says Saturday weather is going to be dreary. Too depressed to to discuss Sunday weather.

# Sariel

## February 27, 2015

DHS funding and the singularity… sarielhp.org/blog/?p=8807

# The singularity is coming…

So the house extended DHS funding by one week. Previously, the funding was for a year, I assume. So, the funding period just shrank by a factor of (roughly) 50. Next week they are going to extend the funding by 3.3 hours, then followed by funding the DHS for 4 minutes, then the DHS would be funded by 5 seconds, and after that, for all practical purposes, we are going to hit the singularity on this piece of legislation.

Get all the homeland security you can get now, before it hits the singularity…

I just have to wonder where all the grownups are.

The article…

# Sariel

## February 21, 2015

Beckett quotes over snow pictures from Boston. Surprisingly effective. mbecketta.tumblr.com

# Sariel

## February 19, 2015

YOFDO = You only freeze to death once (it is -18C here now).

# Sariel

## February 18, 2015

I want a recount of the temperature…