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
Thursday, September 28, 2006
Four legs good, two legs bad...
Not that it will do me much good when the Komitat comes to round up all foreigners, but:
Wednesday, September 27, 2006
A new voting scheme
Ron Rivest has just put out a voting scheme that is remarkable for its simplicity. It addresses the following questions:
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)
- 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
I for one am glad that we have left the challenge era of mathematics far behind us. From Wikipedia's entry on the cubic equation:
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 x3 + mx = n, for which he had worked out a general method. Fiore received questions in the form x3 + mx2 = 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
Bernard Chazelle has updated what has been called 'The IPod essay'. An excerpt:
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
Bill Gasarch has an entertaining dialogue on √2 in the latest issue of SIGACT News (which also has an interesting variant of art-gallery problems in the Geometry column). It's a remarkable coincidence, because I was just about to post an entry about a 7th grade classroom problem that revolves around properties of √2). Unlike T, T, F, S, E, this problem actually does have some really nice math behind it.
The problem is as follows:
It turns out that numbers satisfying this equation can be derived from solutions to Pell's equation:
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 x2y2 is a square triangular number (i.e can be written as n(n+1)/2 or k2).
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.
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
n(n+1)/2 = k2
It turns out that numbers satisfying this equation can be derived from solutions to Pell's equation:
x2 - 2 y2 = 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 x2y2 is a square triangular number (i.e can be written as n(n+1)/2 or k2).
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.
Sunday, September 17, 2006
Looming submission deadlines.
Apropos of my post on implementing geometric algorithms, it seems like a good time to mention the upcoming ALENEX deadline.
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.
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.
Over at bit-player, Brian Hayes has a tale of woe about implementing a geometric algorithm. Not even a complicated one at that, merely an algorithm to check if two line segments intersect. His story is the usual one: general position is a fiction thought up by sadistic geometers (but of course !), and even the simplest of ideas needs many special cases to take of degenerate data.
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.
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
While we're on the topic of books,
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.
vec(AXB) = (BT ⊗ A) vec(X)This 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.
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...
There appears to be a outpouring of new theoryCS textbooks. I had mentioned the Mitzenmacher/Upfal book on probability and randomized algorithms some time ago. Recently, Jon Kleinberg and Éva Tardos published Algorithm Design, the book with THE MOST elaborate real-world exercises I have seen. Sanjoy Dasgupta, Christos Papadimitriou and Umesh Vazirani have another algorithms text coming out as well.
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.
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...
I occasionally read the Chronicle of Higher Education: I guess it's de rigeur for my academic colleagues. It's often too stuffy for me, but this issue has two articles that are real gems (and had me nodding my head in agreement paragraph after paragraph).
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.
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
I recently lost my cellphone, and all my contacts with it. I got a new phone (off ebay, no less) and cingular sent me a SIM card so I could preserve my number. But my contacts were all gone. Now I hear about a new service called ZYB.com that will maintain a web backup of your contacts. The idea is that they collect your contact info (via SMS) and store it, and you can retrieve it (again via SMS) on any phone that allows for text messaging.
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 ?
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...
The full list should be available soon. Unusually, no information about accepts/submits was provided in the author notification.
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.
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.
Subscribe to:
Posts (Atom)