European Workshop on Computational Geometry.

Like CCCG and the Fall Workshop on Computational Geometry, the EWCG is a workshop where you can present results that will appear in expanded form in a conference or journal.

Submission deadline: Jan 8, 2007.
Workshop dates: Mar 19-21, 2007, Graz, Austria.

Categories:

• deadlines

On your marks, get set....

Gentlefolk, STAARRT YOUR LATEX !!!!!!!!!

Program Title:

Theoretical Foundations (TF07) Program Solicitation
Date: February 19, 2007

• Approximately 15 small awards at $60,000/year or less will be made. For example, projects by new faculty may require NSF support for only one student or for summer salary. Most small awards will go to (or preference will be given to) PI's who have not previously been a PI or coPI on an NSF award.
• Up to 55 awards will be made with an average grant size of $125,000/year for durations up to three years.
• Up to 5 awards of up to $500,000/year for well-integrated projects of larger scope are anticipated.

The STOC deadline was over ONE WHOLE HOUR ago ! Get cracking !

p.s Thanks, Chandra.

Categories:

• nsf

On writing versus blogging

I've had this blog for going on two and a half years now, and it's interesting to see how writing posts has influenced my "other" writing.

There is the obvious difference in interface. When I add citations to a paper, I almost wish I had a tool that could highlight text and add a clickable link to a reference (the emacs extension RefTeX is great, though: it makes adding citations, references and labels blindingly easy).

I structure sentences differently as well. Links in blogs are added en passant, without interrupting the text. Citations in papers have to be worked into the sentence structure carefully (that is, if you believe the maxim that a citation is not a noun). This causes no end of confusion when I write sentences in a paper; I often have to rephrase the sentence to conform to "normal" citation format. I will add though that the parenthetical style of mentioning citations makes sense with written documents, but with online hyperlinked PDF documents I would actually prefer blog-style linking. But then again, we still have paper proceedings, so there's a long way to go for that...

It's natural that a blog post is more chatty and personal, and a paper is more formal. But writing a blog has encouraged me to be less stuffy and more breezy in parts of a paper that merit it (introductions, discussion, etc). This can only be a good thing; as the famous war cry goes, 'Eschew obfuscation' !

Writing a blog also shakes out some of the ghastlier linguistic tics that infect my writing. It's actually shocking how many there are, and how easily they evade detection.

I wouldn't recommend writing a blog solely as a way of improving (or expanding) your writing skills. But it does have benefits beyond being a soapbox for one's bloviations.

Categories:

• blogs

Chernoff bounds, error correcting codes, and automata.

Andy Drucker, a first-year grad student at UCSD, has an interesting Math/CS blog. Some of the highlights are a post on showing constructive Chernoff bounds via error-correcting codes, and a love-poem to automata :).

Categories:

• blogs

Reversal in the decline of foreign students in the US

This can only be good news:

The number of new foreign students coming to the United States grew this school year, after several years of weakness that followed the terrorist attacks of 2001, according to a survey to be released today by the Institute of International Education. [..]

According to the survey, conducted by the institute and other education groups, the number of new international students at American colleges and universities increased 8 percent this fall over last, to 142,923.

Another sign of a turnaround was a sharp upturn in student visas, said Allan E. Goodman, president of the institute. Dr. Goodman said the State Department issued a record 591,050 student and exchange visas in the 12 months ending in September, a 14 percent increase over the previous year and 6 percent more than in the year leading up to the 2001 attacks.

It's not that admitting more foreign students is a good thing in and of itself; it's more that this is a useful indicator of how competitive the US is in the marketplace of "idea generation"; for decades, the US had a monopoly on the "idea factories", and in recent years, there's been growing competition from the rest of the world (especially from China), capitalizing on the panic and overreaction following 9/11.

Update (11/17): On the other hand, there's this:

The latest IEE Open Doors report finds that the number of international students enrolled in computer and information science programs in the U.S. declined in academic year 2005/2006, as it has each year since 2002/2003. This occurred even as the number of new foreign students in all programs increased between the Fall of 2004 and 2005 and as total enrollment of foreign students stabilized.

It may not be surprising that foreign student enrollment in CIS has dropped. After all, there's a national trend of dropping enrollment in computer science. The question is whether this drop is more than the overall national trends, and how different the undergraduate/graduate enrollment statistics are.

Categories:

• immigration

Voting

I am a politics junkie, which given my non-citizen status is as about as useful a pasttime as learning Klingon ("Heghlu'meH QaQ jajvam !!!!"). However, my life is deeply affected by laws passed here, and ensuring that not-completely brain-dead zombies come to power is a GOOD THING ("Hab SoSlI' Quch!"). So thanks to all of you that voted, are voting, or will be voting, and no thanks to Lance's prediction page for wasting so many hours of my life :).

Categories:

• miscellaneous

Warning labels, continued...

This could become a nice series. Luca has a "creationist"-style warning for NP-hardness in the comments, and here's another:

WARNING: The next several slides (pages) contain equations. Your soul may be crushed.

Categories:

• funny

Warning label for an NP-hardness proof

A note about the proofs: Transformation arguments can be intricate and
highly formal. Furthermore, since the polynomially-equivalent problem might
not bear any obvious intuitive relation to the voting problem, the proof might
establish computational difficulty without seeming to explain its source. In this
sense, the conclusion is more important than the argument.

From "How hard is it to control an election?", by Bartholdi, Tovey, and Trick.

Categories:

• funny

Tamper-proof voting systems

Digg is a collaborative news site, much like Slashdot, where people post articles that seem interesting and topical. Through a voting scheme, articles get "dugg", and rise to the top of the site. In fact, getting "dugg" is now an inadvertent denial-of-service attack much like being "slashdotted" used to be.

The problem is that people attempt to game the system to bump up traffic to their sites, by forming voting coalitions, making fake accounts, etc etc. Needless to say, there can often be real money (in the form of advertising) behind this, so there's a lot of incentive to cheat the system.

This is not a new problem; Google and other search engines have battled search engine optimizers for a long time now. There are companies that claim to improve your location in a Google search result (for a small fee of course). An interesting side effect of all this gamesmanship is that search engines like Google and aggregators like Digg have to keep many details of their ranking process secret. Obviously, some of this is for IP protection, but protecting against vote riggers is also a major concern. A tertiary consequence of this lack of transparency is that such sites are now vulnerable to lawsuits by disgruntled sites complaining about bias in search results; Google has had to fend off lawsuits based on some claim of bias leading to monetary damage.

The latest such problem has hit Digg, where in an attempt to block out users trying to game votes on articles they want to push, the management has managed to freeze out and frustrate some of the most prolific users. A user-driven site like Digg that has many competitors can't really afford to be annoying its most valuable contributors.

So (finally), here's the technical question. Although Arrow's theorem tells us that in general, voting schemes can always be defeated, I don't know if the result is constructive. In other words, even if there is a voting strategy that can break one of the criteria for a reasonable voting scheme, it may not be easy to find such a scheme.

So, in the spirit of RSA, is there a way of designing a voting scheme that can be published (thus addressing issues of transparency), but is computationally intractable to game ? Any cryptographers know if this has been studied ?

Categories:

• cryptography

CS beyond algorithms: Would that it were so....

From an NYT article on a new research program in "Web science":

Ben Shneiderman, a professor at the University of Maryland, said Web science was a promising idea. “Computer science is at a turning point, and it has to go beyond algorithms and understand the social dynamics of issues like trust, responsibility, empathy and privacy in this vast networked space,”

In fact I'd be happy if this were so. Alas, I spend more time encountering computer science that hasn't even discovered algorithms yet !

Categories:

• snark
• miscellaneous

The Snowblowing (or leaf raking) problem

Lifehacker asks:

Reader David wants to know the best way to rake leaves. My first thought: "Get someone else to do it." But seriously, assuming you have a square or rectangular yard, what's the most efficient raking pattern? Should you make multiple smallish piles or aim for one big one (the latter being best for running jumps, of course)? Surely there's a mathematical or engineering principle that can be applied here.

As it turns out, this year's WAFR (Workshop on the Algorithmic Foundations of Robotics) has a paper on essentially this problem (with leaves replaced by snow), by Arkin, Bender, Mitchell and Polishchuk:

We introduce the snowblower problem (SBP), a new optimization prob-
lem that is closely related to milling problems and to some material-handling prob-
lems. The objective in the SBP is to compute a short tour for the snowblower to
follow to remove all the snow from a domain (driveway, sidewalk, etc.). When a
snowblower passes over each region along the tour, it displaces snow into a nearby
region. The constraint is that if the snow is piled too high, then the snowblower
cannot clear the pile.

This is not to be confused with the Snowplow problem, a puzzle in elementary differential equations:

One day it started snowing at a heavy and steady rate. A snowplow started
out at noon, going 2 miles the first hour and 1 mile the second hour. What
time did it start snowing?

p.s Actually, it's true. The slides are more interesting...

Categories:

• puzzles

Happy Halloween, from the Turing Pumpkin.

A splendiferous carving, here. (via BB)

Categories:

• miscellaneous

Cryptography as adultery and betrayal.

xkcd is a a comic for the sophisticated geek in all of us...

Categories:

• miscellaneous

There, but for the grace of god, ...

This week's issue of the NYT Magazine has a long story on a case of scientific fraud from the University of Vermont, where a prominent researcher was sentenced to a year and a day in jail (as well as being banned from ever getting public funding) for falsifying results in dietary studies.

It seems unnecessary, (and too easy) to blame the researcher involved; the story is damning enough. What struck me though, reading though the description of how events transpired, was how banal, how mundane the fraud was, and how utterly common the driving forces were; the usual toxic mix of a desire for fame, the pressure to get money, how universities encourage people to bring in grants.

Steven Heymsfield, an obesity researcher at Merck Pharmaceuticals in New Jersey, [...] added that Poehlman’s success owed more to his business sense and charisma than to his aptitude as a scientist.

“In effect, he was a successful entrepreneur and not a brilliant thinker with revolutionary ideas,” Heymsfield wrote me via e-mail. “But deans love people who bring in money and recognition to universities, so there is Eric.”

Categories:

• culture

Computer scientists sit in a cube and program all day...

Science+Professor+Woman=Me has an interesting experience talking to a bunch of freshmen about science (emphasis mine):

...today I gave a guest lecture to a group of freshmen who all said they were not interested in science. It turns out that they had no idea what science really involves. I listed a bunch of scientific questions and asked if these were things they wanted to know. Yes! They did. So we talked about these for a while, and then they thought of more questions, and it was a very fun. We also talked about how research is done - how you come up with the questions,how you go about answering, discovering, testing. The students said they hadn't known that these were the kinds of things that scientists did. They imagined that we just worked in our labs making chemicals or looking at data on computer monitors all day. I doubt if any of them were inspired to become scientists, but I felt pretty good about changing their perceptions of science and scientists.

I wonder what would happen if we did this for CS.

Categories:

• outreach

Deadlines, manic behaviour and happiness

Much as I rant about the idiosyncratic "conference as primary publication venue" nature of computer science, there's no denying the pleasures of working down to the wire to meet a deadline. The adrenaline rush, the highs (and the post-deadline lows), and the feeling that my mind is working at 200 mph... aaah. It's like a drug habit I can't shake (which is why, inspite of vowing after each deadline never to do it again, I ... do it again. Classic addict behaviour).

It turns out that all I'm really doing is maximizing happiness. Who'da thunk it ?

When people are made to think quickly, they report feeling happier as a result. They also say they are more energetic, more creative, more powerful, and more self-assured. In short, they reported a whole set of experiences associated with being "manic."

And if your paper, written with the sweat of your fevered brow, fueled by zillions of cups of coffee, delivered by divine inspiration from the Book to your mind, gets rejected ? Just think quickly:

...the effect of thought speed was just as powerful as the effect of the content of the thoughts. In other words, the speed of people's cognitive processing was just as important as what they processed in determining their mood. Even thinking sad thoughts at a fast pace made people relatively happy.

Categories:

• culture

"We're making it less random to make it feel more random."

Maybe we should use the iPod to explain all concepts in theoretical computer science:

Steven Levy really liked Steely Dan, but so too, it seemed, did his iPod. Like a lot of people, he began to wonder about its shuffle - was the random function really random or a result of dirty tricks, blunders... or even telepathy?

Read more about it at the Guardian (HT: The Mathematics Weblog)

Categories:

• randomness

On Models For Research

In a review of Lee Smolin's new book, 'The Trouble With Physics', Sean Carroll writes:

Faculty positions and grant money are scarce commodities, and universities and funding agencies are naturally risk-averse. Under the current system, a typical researcher might spend five years in graduate school, three to six as a postdoc, and another six or seven as an assistant professor before getting tenure – with an expectation that they will write several competent papers in every one of those years. Nobody should be surprised that, apart from a few singular geniuses, the people who survive this gauntlet are more likely to be those who show technical competence within a dominant paradigm, rather than those who will take risks and pursue their idiosyncratic visions.

It's worth pointing out here that there are many different models for being a successful researcher. And when I say successful, all I mean is that you contribute interesting results to the community and your work is appreciated. Indeed, finding out what model works for you is an important part of developing your identity as a researcher.

We develop our sense of what the 'ideal' researcher looks like from people around us: the advisor, the mentor, the researcher whose papers we pore over. Invariably, some will influence us more than others, and we'll start adopting, unconsciously almost, some of their style and taste for problems and lines of attack. All of this is good, and natural. But it's important to remember that like you form your own identity as a person by drawing on influences and modifying them, you must do the same as a researcher.

It's worth pointing out because I don't know how deeply we think about models of research, and what style of work makes us happier (problem solver ? theory builder ? voluminous production ? multiple collaborations ? sitting in a room and contemplating? ). Once you find your "comfort zone", you'll be a lot more content with your work, and in all likelihood you'll produce quality work.

Categories:

• culture

Flying while brown, part II

I used to call it, 'Travelling while Asian', but let's face it: it's the brown skin that counts.

Here's the latest, from Boing Boing:

A 32-year-old man speaking Tamil and some English about a sporting rivalry was questioned at Sea-Tac Airport and missed his flight Saturday because at least one person thought he was suspicious.

[....]

The man was speaking Tamil, a language largely used in India, Sri Lanka and Singapore, on his cell phone at the departure gate and on the aircraft. An off-duty airline employee heard the conversation and informed the flight crew.

All those years I spent fending off attempts to teach me Tamil by my parents, grandparents, aunts, uncles, cousins, great-aunts and great-uncles and second cousins twice removed are now finally worth it ! I am safe !!

I wonder what will happen if I speak Hindi....

Categories:

• habeas
• corpus

Four legs good, two legs bad...

Not that it will do me much good when the Komitat comes to round up all foreigners, but:

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

Categories:

• habeas
• corpus