The Economics of Gender Imbalance

The New York Times reports on gender imbalance on American college campuses, where women often account for as many as 55% of enrolled students. This is apparently making the few remaining men being chased by eager crowds of women, and the men hook up and cheat a lot. As explained by W. Keith Campbell, a psychology professor at the University of Georgia, which is 57 percent female: “When men have the social power, they create a man’s ideal of relationships,” which the author of the article translates as “more partners, more sex.”

Another interesting quote: “(…) the university [of North Carolina] has a high female presence in part because it does not have an engineering school.”

Meanwhile, in China lately about 54% of newborns are boys, a result presumably of selective abortions, motivated by a societal preference for male children together with the one-child policy. According to a Forbes article, this might be one of the causes of China’s extremely high savings rate, because “Wealth helps to increase a man’s competitive edge in the marriage market.”

(I found the Forbes article via a post on the excellent blog of Patrick Chovanec, a Tsinghua professor of economics. His posts on the real estate market in China and on regional differences are fascinating. Anyway, what is the mathematical mistake in his post linked above?)

People of Massachusetts

You don’t get to make fun of California any more, until November.

You Read it Here First

Last year, I wrote on the losing tactic of promoting oneself by disparaging the competitors, using a parable attributed to Silvio Micali.

This week a Dilbert cartoon covers the same ground.

Outrage of the day

While searching for the origin of the expression “biggest and baddest” (long story — by the way, I wasn’t able to find it), I came across the following books:

• For Boys Only: The Biggest, Baddest Book Ever
• For Girls Only: Everything Great About Being A Girl

The titles seem already the imagined setup of a Simpsons episode in which Lisa is riled up against corporate sexism. (Remember the episode with the Malibu Stacy doll that says “math is hard, let’s go shopping,” which was based on a real Barbie doll?) The contents do not disappoint.

The biggest and baddest book (the table of contents can be read on Amazon) is all, more or less, encouraging interest in science, engineering, and even math: there are dinosaurs, DNA, how a cell phone works, how an MP3 player works, what is the biggest bridge, what is the weirdest dinosaur, what is the fastest production car, and so on, including math-based card tricks.

The girls book is mostly about make-up, manicure, ponies (no, really, there are two sections on horses and one on ponies!), and superstition. The book includes a tarot card, and it dwells on astrology, palm reading, and miscellaneous fortune telling.

What is most galling, however, is the review of the girls book on the National Geographic blog for kids. Not only it is a positive review, but it has excerpts such as

“It is also a JUST for girls book because it talks about girl stuff which is really fun. (…) Did you know that if you are dreaming about a door than there are opportunities ahead? (…) Another chapter that stuck out to me was Palmistry. The book told you which line on your hand is your lifeline and what it meant. It said that since my lifeline was long and curved that I will have a long and healthy life!”

This is on the website of the National Geographic, one of the largest non-profit scientific and educational institutions in the world.

p.s. To be fair, the girls book has a section on “overcoming math phobia,” a section describing the difference between astrology and astronomy, and a section on “women in technology,” which includes a reference to Ada Lovelace and from which I learned that actress Hedy Lamarr (whom I knew as the first actress to appear nude in a mainstream movie) co-invented a technique for information transmission wherein the frequency of transmission is continuously varied (requiring more bandwidth but improving throughput).

Happiness is a blank page

For a while (through grad schools and for several years afterward) I took notes and wrote calculations on loose printer paper. In theory, I would collect the notes into folders, or maybe even punch holes and collect them into binders; realistically, I would always lose them.

Then I thought I would start using notebooks. I went to the corner Walgreens wanting to buy a notebook which would be spiral-bound and with blank pages. Spiral-bound because it always stays open flat and it’s easy to tear off pages, and with blank pages because I cannot write math on ruled paper. It turns out that this was an extravagant demand: all notebooks were ruled. I searched some more, to the same conclusion, and then started using “sketchbooks,” which have plain paper and spiral binding, but have heavy, rough, paper meant for drawing.

Then, one day, hanging out in Japantown waiting for a movie to start at the Kabuki theater during a film festival, I found my dream notebook at the Kinokuniya stationery store. Spiral (actually, “double ring”) bound, with thin, smooth and very white paper, and a beautiful cover design. I bought one, and went to the theater, but it was still too early and we had to stand in line for a while. So I took out the notebook and started thinking about the problem I was working on at the time. And right then and there, I had the main idea in the analysis of one of the algorithms in what later became my paper on approximation algorithms for unique games.

So, I kept buying them, until Kinokuniya stopped carrying them, and now there is nearly no trace of them of the internet. (If you want to try look it up yourselves, it’s the “Expedient” notebook made by Kyokuto ltd., in China.)

I thought I was being a little “peculiar” in being so difficult about what to write on, until I talked about it to other theoreticians, and then I found out that there are many people who, in fact, like to write on unmarked paper and can’t understand why the option is so hard to find in America.

As a happy ending, I was out of town for New Year’s Eve, and I happened into a Muji store. It turns out Muji sells plain-paper notebooks with double-ring binding, and while they don’t look as neat as the Expedient ones, they are just fine, and cheap, and now I have four of them, on which I hope to prove lots of new theorems this coming Winter and Spring quarters. Wish me luck!

Does This Fact Have a Name?

Does the following fact have a name?

Theorem 1 Suppose are a countable collection of 0/1 random variables over a probability space such that for every integer and bits the event

is measurable.

Suppose that

Then

Proof: Intuitively, we want to say that by linearity of expectation we have and so by Markov’s inequality

Just to make sure that this can be made rigorous, let’s belabor the proof step by step, doing everything completely from first principles.

Small-bias Distributions and DNFs

Two of my favorite challenges in unconditional derandomization are to find logarithmic-seed pseudorandom generators which are good against:

1. log-space randomized algorithms
2. , that is, constant depth circuits of polynomial size

Regarding the first challenge, the best known pseudorandom generator remains Nisan’s, from 1990, which requires a seed of bits. Maddeningly, even if we look at width-3 oblivious branching programs, that is, non-uniform algorithms that use only bits of memory, nobody knows how to beat Nisan’s generator.

Regarding the second challenge, Nisan showed in 1988 that for every there is a pseudorandom generator of seed length against depth- circuits of size . The simplest case is that of depth-2 circuits, or, without loss of generality, of disjunctive-normal-form (DNF) formulas. When specialized to DNF formulas, Nisan’s generator has seed length , but better constructions are known in this case.

Luby, Velickovic and Wigderson improved the seed length to in 1993. Bazzi’s celebrated proof of the depth-2 case of the Linian-Nisan conjecture implies that a -wise independent distribution “-fools” every -term DNF, by which we mean that for every such DNF formula and every such distribution we have

where is the uniform distribution over assignments. This leads to a pseudorandom generator that -fools -variable, -term DNF formulas and whose seed length is , which is when are polynomially related.

In a new paper with Anindya De, Omid Etesami, and Madhur Tulsiani, we show that an -variable, -term DNF can be -fooled by a generator of seed length , which is when are polynomially related.

Our approach is similar to the one in Razborov’s proof of Bazzi’s result, but we use small-bias distribution instead of -wise independent distributions

On the Importance of Fast Encryption

The CNN reports that Iraqi insurgents have been able to see the video feeds from the cameras of the remote-control planes (“drones”) that are used by American forces to gather intelligence and for targeted strikes.

How did the Iraqi insurgents manage to break the encryption used by the American military? That was easy: the video feed is sent in the clear from (some of) the drones. And with what sophisticated eavesdropping devices did the Iraqi insurgents manage to capture the video signal? With standard satellite dishes, and with a Russian program originally written to watch satellite TV channels for free.

Well, thanks God this incredible oversight has been exposed, so that it can be fixed.

“We have known about this for years.” Military sources told CNN. In fact, during the 2003 invasion, the Iraqi army was able to see the feeds from the drones, and hence locate and destroy some of them.

And what exactly was anybody thinking? “Encryption was found to slow the real-time link.” The military source told CNN: “The encryption therefore was removed from many feeds.”

Women In Theory 2

I received from Tal Rabin an announcement of the Second Women in Theory Workshop, which will take place at Princeton on June 19-23, 2010.

To apply please go [here]

The format will be similar to the WIT 2008 workshop.

Here is a video about the 2008 workshop:

Overheard in San Francisco II

“Oh my God, this changes everything!”

[Woman standing next to me at the Bi Rite meat counter, after a butcher put a newly arrived pork belly in the display case. Emphasis in the original.]