Thank you for joining the American Civil Liberties Union. Your gift will help us continue the fight for our basic civil liberties. Below is your donation information.

Ready to do more?

Invite your friends to join in standing up for freedom with the ACLU

Contact Information

Name: Suresh Venkat

Address: xxxx -xxxxx

Email Address: sureshv@gmail.com

Ruminations on computational geometry, algorithms, theoretical computer science and life

## Thursday, September 28, 2006

### Four legs good, two legs bad...

## Wednesday, September 27, 2006

### "Who are you ? How did you get in my house ?"

### A new voting scheme

- How do you tell if your vote was counted
- How might you get proof that you voted
- How can this be concealed from (a) someone trying to coerce you (b) someone trying to find out your vote or tamper with it (c) from you !

Here's the idea: suppose you have to vote on one of two candidates Alice and Bob. You vote three times, once on each of three ballots. If you prefer Alice, you vote for her on two of the three ballots, and vote for Bob on the remaining ballot. As a receipt, you take back a copy of one of the three ballots you used. The three ballots are separated and cast individually as separate ballots into the counting box.

The neat idea here is that each candidate gets n + C votes, where C is the number of people who voted for them. So it's still easy to determine winners, and because the single receipt ballot could have come from any combination of votes, the true intention of the voter cannot be determined from their receipt. There is some heuristic reasoning about the possibility of tampering and where the main weaknesses lie.

An important side effect of the fact that you can't determine a vote from a receipt is that vote selling is not possible: how will you prove to the vote buyer that you voted as they asked ?

(From comp.risks via Adam Buchsbaum)

## Monday, September 25, 2006

### Mathematics as blood sport

You have to wonder: when you lay down a mathematical challenge, do you throw a quill at the feet of your rival ?In 1530, Niccolo Tartaglia (1500-1557) received two problems in cubic equations from Zuanne da Coi and announced that he could solve them. He was soon challenged by Fiore, which led to a famous contest between the two. Each contestant had to put up a certain amount of money and to propose a number of problems for his rival to solve. Whoever solved more problems within 30 days would get all the money.

Tartaglia received questions in the form

x^{3}+mx=n, for which he had worked out a general method. Fiore received questions in the formx^{3}+mx^{2}=n, which proved to be too difficult for him to solve, and Tartaglia won the contest.Later, Tartaglia was persuaded by Gerolamo Cardano (1501-1576) to reveal his secret for solving cubic equations. Tartaglia did so only on the condition that Cardano would never reveal it. A few years later, Cardano learned about Ferro's prior work and broke the promise by publishing Tartaglia's method in his book

Ars Magna(1545) with credit given to Tartaglia. This led to another competition between Tartaglia and Cardano, for which the latter did not show up but was represented by his student Lodovico Ferrari (1522-1565). Ferrari did better than Tartaglia in the competition, and Tartaglia lost both his prestige and income.

## Thursday, September 21, 2006

### Turingistan

Let's try a thought experiment, shall we? You're the unreconstructed Algorithm skeptic. Fresh from splitting your playlist, Alice, naturally, is the advocate. One day, she comes to you with a twinkle in her eye and a question on her mind: “What are the benefits of the central law of mechanics?” After a quick trip to Wikipedia to reactivate your high school physics neurons and dust off the cobwebs around them, you reply that F=ma does a decent job of modeling the motion of an apple as it is about to crash on Newton's head: “What's not to like about that?” “Oh, nothing,” retorts Alice, “except that algorithms can be faithful modelers, too; they're great for conducting simulations and making predictions.” Pouncing for the kill, she adds: “By the way, to be of any use, your vaunted formulas will first need to be converted into algorithms.” TouchÃ©.Much fun. Go read.

## Wednesday, September 20, 2006

### The magic of √2

The problem is as follows:

You live on a street where the houses are numbered 1,2, 3, etc.. You notice that the sum of house numbers prior to yours equals the sum of house numbers after yours. What is your house number, and how many houses are there on the street ? Your answer should be in the 30sSome quick algebra on n, the number of houses, and k, your house address, reveals that the numbers satisfying this condition yield a square triangular number. Namely, n and k must satisfy the equation

^{2}

It turns out that numbers satisfying this equation can be derived from solutions to Pell's equation:

^{2}- 2 y

^{2}= 1

where x, y are integers. Pell's equation actually gives good rational approximations to √2, in the form x/y, where x, y are solutions. What's more, if x/y is a convergent in the continued fraction of √2, then x

^{2}y

^{2}is a square triangular number (i.e can be written as n(n+1)/2 or k

^{2}).

There's also a general form of the solution, that I first found (courtesy David Applegate) in the Hardy/Wright book on number theory. The "trick" here is to realize that the appropriate way to solve this is over the field of numbers of the form a + b√2.

It's rather satisfying that a simple extra credit problem for a 7th grade math class can yield such nuggets.

### STOC 2007 Deadline

## Sunday, September 17, 2006

### Looming submission deadlines.

The aim of the ALENEX workshop is to provide a forum for presentation of original research in the implementation and experimental evaluation of algorithms and data structures.If you use Google Calendar, click to add the deadline to your calendar.

Another deadline that's coming up even sooner is for the Fall Workshop on Computational Geometry, the annual math-conference-style event for geometers. This year it's in Smith College on Nov 10-11, and is being run by Ileana Streinu. One of the special events this year is a 3D Printing demo by Joe O'Rourke. The deadline is Sep 22, and it should already be in your calendar by now, but if not, click here .

p.s if you want to create buttons like above for your event, here's the link.

## Thursday, September 14, 2006

### Implementing geometric algorithms.

Apart from being surprised that he didn't have problems with precision (how DO you tell if both endpoints of a line segment are identical), I sympathize with his plight. As anyone who's ever implemented a geometric algorithm will tell you, it's much harder than it seems, and to an extent, the idealized algorithms geometers design can be hard to implement. CGAL and LEDA have made life a lot easier, but robustness and exact computation are still important (if highly uncool) areas of computational geometry.

## Wednesday, September 13, 2006

### Matrix wizardry

vec(AXB) = (BThis identity is your best friend if you're doing any kind of matrix calculus. To know more about it, and all you might ever want to know about Kronecker products, the vec() operator, and matrix calculus, check out The Matrix Cookbook, a 50+ page reference guide for all things matrix and calculus.^{T}⊗ A) vec(X)

p.s the reason the identity is so handy is that it allows you to get the variable matrix X out from in between A and B.

### New textbooks in theoryCS...

The not-so-latest addition to this list is a new book on complexity theory by Sanjeev Arora and Boaz Barak. For a long time now, Papadimitriou's book has been the definitive text in this area, but it has begun showing its age, especially with all the new developments in complexity theory. The Arora/Barak book is not yet published, but has been placed online for comments.

The magic of Papadimitriou's book was in making complexity classes spring to life as the denizens of the Zoo that they really are. Complexity theory can be a dry topic if not imbued with a sense of direction and purpose, helping us understand the WHY of how these classes came to be. If my cursory scanning of the Arora/Barak book indicates anything, it is that this new book is a worthy successor.

The two books cover similar material in the foundational sections; where I think the new book takes off is in its coverage of the more "modern" aspects of complexity theory: the profound results on pseudorandomness, hardness and cryptograpy, interactive proofs and approximations, natural proofs, communication complexity and lower bound methods, and even quantum computing.

## Thursday, September 07, 2006

### The Indian grad student experience, and more...

Unless you've hung around Indian grad students, you have no idea of the kind of organizational skills that we can muster up when it comes to helping fellow Indian students acclimatize. I recall being picked up at SFO by a "senior" grad student and driven to Stanford, and supplied with all kinds of useful information when I got there, (including copies of all the variations of the driving tests the California DMV uses!). Apparently, things have become much more sophisticated: check out this description of the Indian student organization at NC State (and yes, I do own a copy of The Inscrutable Americans; the letter Gopal writes to his father at the beginning of the book is priceless).

The other article could have easily been written about my parents, and their general bewilderment at the kind of work I do (I remember the first time I went to work in shorts while my father was visiting, and how scandalized he was) . It's hilarious: do check it out.

## Wednesday, September 06, 2006

### Data hosting on the web

It's a cool idea: although there are doohickeys you can get to sync your palm/outlook/PC addressbook with a phone, they are usually vendor specific. This is more general, and is aligned with the whole "store your data on the web" philosophy that's all the rage nowadays (mail, calendars, online spreadsheets, ...)

Privacy of course is the issue, especially with contact info, a gold mine of real telephone numbers and often email addresses. ZYB of course makes all the right noises about privacy, but ultimately you have to trust them.

Why must that be ? It can't be that hard to store data encrypted, and decrypt on the fly only when a user provides a pass-phrase ? The problem with SMS specifically is that the user might have to type the pass phrase out in the open, but maybe there's an IPsec equivalent of SMS out there ? And even if there isn't, wouldn't server-side encryption obviate the need to trust a private entity ?

Given how ubiquitous crypto has become, I think I'd need to be convinced why obvious schemes like this can't be used before handing over data to an entity that I have to "trust".

p.s another point that came up in discussion was the lifetime of such a company. What's the guarantee they won't go belly up in a year and sell your data, or worse, lose it ?

### SODA results trickling in...

Here's our (accepted) paper.

Update: 135 papers accepted, with some caveats. There were 4 merges, and with two papers, I believe that there will be two separate papers in the (already extra-large) proceedings, but only one talk. The rationale for this escapes me. Effectively there will be 137 papers in the proceedings though. This translates to a 36% acceptance rate.

Update II: The list of accepted papers is here.