July 04, 2008

Friday Math Movie - The Quadratic Formula Video

A few weeks back we had Hector the Droid teaching us about quadratic formula.

Here’s another effort at tarting up what is normally a very dry topic in school.

Loading Flash movie…

July 03, 2008

A Prime time

I was called upon to escort a patient that had presented in A&E to a hospital out of area recently.

Li’s Preprint

Yesterday, everyone was all atwitter over a new preprint by Xian-Jin Li containing a purported proof the Riemann Hypothesis. The optics of it looked good (Li is clearly not a crank), but Terry Tao has identified an apparent error.

More at Not Even Wrong.

The First Teaching Post

Okay, all you math fans...I put up my first teaching post.  If you're a teacher, you'll recognize the need for a good explanation.  So very, very, very (did I mention VERY?) many students get this wrong.  I'm open to suggestions on improving my style for this project, so please comment (praise or suggestions) here if you feel the urge.

Will Smith movie star

LOS ANGELES - The biggest star on the planet is sucking his thumb. 'Damn,' Will Smith says on the set of 'Hancock,' trying to shake the pain of a thumbnail that split in two as he was thrown through a mock ...

Segerberg in Calgary 2008/09

Krister Segerberg will be visiting the Philosophy Department at the University of Calgary during the 2008/09 academic year as Killam Visiting Scholar. He'll be teaching two courses, an intro to modal logic course in the Fall and an advanced course in the Winter term. There will also be a little two day workshop, most likely in January, with him, Aldo Antonelli, and Nuel Belnap.

Tenure-Track Job in Logic at Calgary!

My department is advertising for a junor position in logic. Please apply or tell me if you know of any promising candidates. If you need more information, you can contact Ali Kazmi (contact details below) or me, of course. We also have a recruitment page. Salient details missing from the ad: teaching load is 2-2, instruction is in English.
The Department of Philosophy at the University of Calgary invites applications for a tenure‐track position at the rank of Assistant Professor beginning July 1, 2009. A PhD or equivalent is required. The Department is seeking candidates who are able to teach a range of courses in logic, from elementary formal logic to the advanced levels, including the meta‐theory of first‐order logic, undecidability, incompleteness, and non‐classical logics. The area of specialization for this position is Logic or a related field of study.

Teaching duties include undergraduate and graduate instruction as well as graduate supervision. Complete dossiers, including a curriculum vitae, at least three confidential letters of reference, post‐graduate transcripts, a recent sample of writing, and evidence of teaching effectiveness may be sent to:

Merlette Schnell
Department of Philosophy
University of Calgary
2500 University Drive NW
Calgary, Alberta T2N 1N4
Canada
schnell@ucalgary.ca

The Selection Committee will begin to assess applications after NOVEMBER 21, 2008.

Applications will be accepted until the position is filled. All qualified candidates are encouraged to apply; however, Canadian citizens and permanent residents of Canada will be given priority. The University of Calgary respects, appreciates, and encourages diversity. Specific inquiries about this position may be directed to:

Ali Kazmi, Head
Department of Philosophy
University of Calgary
(403) 220‐5535
akazmi@ucalgary.ca

The Great Procrastinators

A chemist earlier this week called computer scientists famous procrastinators with our uncanny ability to put off to tomorrow what we could have done today. I'd feel insulted except that he's absolutely right. For those who disagree, aren't you supposed to be working on your SODA papers now?

Why is procrastination seemingly part of our culture? Much has to come from our deadline-driven conference and grant system. If deadlines motivate us highly then not having a specific deadline for a task (say writing or refereeing a journal paper) tends to push that task down to later when we'd rather be doing something else like research.

Sometimes people take it to the extreme: One time someone decided to skip a workshop months in the future because a STOC deadline was at the end of the same week. I convinced that person to sign up for the workshop by tricking them into thinking the deadline was one week earlier. Maybe I lied but wasn't everyone better off for it?

And then, of course, as computer scientists we are always on a computer with access to the web, the great distractor. It's just too easy to catch some videos, catching the latest political news, reading and writing email and blogs…OK, back to work for me.

Enjoy the 4th everyone and we'll be back on Monday.

July 02, 2008

The IntMath Newsletter - 2 Jul 2008

In this Newsletter

1. IntMath future development - survey results
2. Math tip - Solving math word problems
3. From the math blog
4. Some brain math


1. IntMath future development - survey results

Thank you to all those who completed the survey on future IntMath developments (which I mentioned in the last IntMath Newsletter).

The survey showed there is strong interest in each of the following:

  • A forum for help on homework. Also, several teachers asked for a teachers’ forum.
  • Video lessons on various math topics, and also on how to use computer algebra systems.
  • e-Books on various math topics, including math anxiety.

There were some great suggestions that you gave in the written part of the survey and I will progressively develop the best ideas over the coming months.

Thanks again for your input!


2. Math tip - Solving math word problems

Most students struggle when they are asked to solve word problems. There is a good reason for this — your brain is super-busy while figuring out such problems.

This tip became a bit long for this Newsletter so I made it into a separate article. Check it out here:

Math Problem Solving and Brain Activity


3. From the math blog

1) Fractal Science Kit
Fractals are beautiful mathematical art objects. This article describes a tool for creating them.

2) Google gadgets - cool extras for your website
Google Gadgets allow you to easily add fun stuff to your Website or blog, including math games.

3) Friday Math Movie - Math Test Anxiety
This strange anime illustrates one student’s nightmares about math tests. Warning - it’s very strange and may be disturbing for some viewers.


4. Some brain math

To finish, I thought I’d tell you some interesting facts about the brain.

  • The human brain has 100 billion neurons, each linked to as many as 10,000 neurons
  • The brain is 60% fat
  • The brain can handle about one billion instructions per second
  • The brain weighs 2% of total body weight, it needs 15% of the body’s blood, consumes 20% of total body oxygen, and requires 25% of total body glucose (sugar)
  • The brain uses up 1.5 calories per minute during crossword puzzle-solving

[Source]

Summary: You have a remarkable organ between your ears. Look after it well.

Until next time.

Finite-variable hierarchy conjecture

It seems that Ben Rossman has resolved another long-standing open problem in finite model theory: finite-variable hierarchy conjecture. Loosely speaking, the conjecture is that over ordered graphs first-order logic with k+1 variable is more powerful than first-order logic with k variable. The problem is nicely summarized in Anuj Dawar's survey. Ben has shown that this hierarchy is strict. What was previously known is that (over ordered graphs) first-order logic with 3 variables is strictly more expressive than first-order logic with 2 variables, but it was not known whether first-order logic with 3 variables is less expressive than first-order logic with k variables, for every k > 3. Worse yet, it wasn't even known whether this hierarchy is strict. See Anuj Dawar's survey for further details.

I believe this is the third big open problems that Ben has resolved in this decade. Go Ben!

Math problem solving and brain activity

I believe that solving math problems is a very important issue. Mathematics is more than just “doing algebra”. If we know how to solve a real-world problems, then we’ll have a powerful and important ability, and best of all we’ll see why we are doing all this math.

Let’s say you have a math problem that is in sentence form. Most people struggle with word problems and one reason is that math word problem solving uses many parts of the brain.

Here are some tips on how to attack math problem solving — and I have included an indication of what goes on in the brain during each step. Here is a diagram of the brain so you can follow along. The front of the brain is on the right of the diagram.

brain
Image source.

a. Read over the whole problem: Understand the whole question first and take special note of the what?, when?, which?, how many? parts of the question, usually at the end.

The areas of the brain that you use for this portion of the math problem are the very back of the brain (your occipital lobe) where you process what you see. You also use the language areas of your brain (a large portion of the left hemisphere, surrounding your left ear).

b. Write down or draw what the question tells you: By listing the information in the question, it helps you to sift through what you already know and it reminds you of the math that might be involved. Once again your left brain is involved in the writing part, in particular Broca’s Area and Wernecke’s Area, which are above your left ear.

If there is any geometry involved (or graphs, or moving objects, or any other visual element) in the question, draw the situation. For drawing, you use the areas towards the rear top of your brain (the parietal lobes), the area at the top of your head (the sensorimotor region) and the back of your brain (vision).

c. What do they want? Is the quesion asking for a speed, or a time, or a length, or a position, or a cost? Many students answer a word problem by giving an answer that is not what the question actually asked. In the real world, will your boss be impressed if you give a time answer when they actually asked for a cost?

At this point, it is good to estimate the answer and to write down that estimate for checking later. Estimation involves non-language areas of the brain (while exact arithmetic involves language areas).

So far in our math problem solving, we have a good idea what the question has told us and we know what we need to find. We also have an approximation for our answer.

d. Identify the math required: Now you need to make a decision about the math. Will it involve algebra? Or maybe trigonometry? Or logarithms? Maybe it will involve differentiation or perhaps integration? This is where you see the need to actually learn the formulas in each section of math that you study, and not rely 100% on formula sheets. The best way to recognize the math that you need to use, is to know that math in the first place.

This step uses the higher-order thinking areas at the front of the brain (the frontal lobes) and the memory areas of the brain (which tend to be all over).

e. Do the math: Now we need to churn through the algebra (or whatever) to get our answer. Assign variables to the known and unknown quantities in the question. In the brain, this step involves the frontal lobes and the area behind and above the ears.

Your answer must include units (if there are units in the question).

f. Check, check and check: Firstly, check if your answer is close to your estimate. If not, it’s back to the drawing board.

Next, read over the question again and check that you have actually found what the question was asking for.

Finally, check all the algebra and arithmetic steps.

Phew! We are done.

Now don’t be scared about all the brain activity involved in math problem solving. It’s like most human abilities — the more you do it, the easier it becomes and the brain can begin to relax.

George Polya contributed greatly to our understanding of how to solve math word problems. You can see a summary of his approach from his 1957 book “How to Solve It” at G. Polya: How to Solve It.

A NEW Blog in Town-kdphd

(***SORELLE*** requested and approved this message, though I wrote it.)

There is a new theory blogger on the scene and as you read that sentence you may be wondering `oh, who is he?' That would be the wrong question.

Check out kdphd.blogspot.com a new blog by a ***SORELLE*** a female theorist. Her first blog is a short intro to herself. The second one is about a women-in-computing workshop she went to.

What will ***SORELLE*** blog about in the future? She says it will be women's issues (a term she doesn't like- perhaps she'll blog about what to replace it with), computer science, grad school, politics, the politics of computer science grad school, and whatever else comes up. She is multi-dimensional and so I assume her blog will be too.

She is a Comp Geometry student from The University of Maryland. I am happy to say I have had no influence on her whatsoever. She is her own women.

Why is her name ***SORELLE*** ? Because I was once asking people what their stage names would be if they had one. Sorelle is one of those people like MADONNA and CHER and others celebs that have one word names. Hence she will always be ***SORELLE*** to me. Actually, I don't know her last name.

A pointer to her blog can now be found on our blog under `Sorelle'. (Lance is not big on asterisks and capital letters.)

July 01, 2008

Day Two of Eurostrings 2008

Another day, another cup of soup and a sandwich for lunch. Today it was ham soup and a pineapple sandwich (my Dutch and my taste buds are not good enough to understand what the other ingredients were). This morning we had a review lecture on the pure spinor formalism by Nathan Berkovits. If you want to learn this formalism, why not start with the reviews here (and here [or the blog article here]

Eurostrings 2008

The tram door closed viciously on Pierre Vanhove's rucksack and off it tootled away from Centraal Station (the tram, not the rucksack). My travelling companions were all on board, and only I was left behind with the rest of the amputated tram queue. The man behind me in the queue said "welcome to Amsterdam" in friendly English. We struck up a conversation and he asked what kind of conference I

NSF and CACM

I received two "Dear Colleague" letters over the weekend. Jennette Wing, current head of the Computer & Information Science & Engineering directorate at NSF, describes the restructuring of CISE including a new Algorithmic Foundations program, of interest to many readers of this blog. Many program solicitations have already been posted with deadlines much earlier than in previous years.

Moshe Vardi tells us that we all ought to join the ACM, partly to help support the main computer science society, but also because now you will receive the new redesigned Communications of the ACM under Vardi's editorialship.

ACM serves two very different communities, academic computer scientists and practicing computer professionals. The flagship magazine, CACM, has to cater to both groups to succeed. The old CACM mostly had articles around some common topic written by academics, aimed at practitioners and not fitting the needs of either group.

So how is the new CACM? The first redesigned issue (July) just came out and is available online. It hasn't reached the full vision but does give a taste with some opinionated pieces on topics from XML to quantum computing. It also has interviews with Donald Knuth and the Turing award winners.

Definitely an improvement but I didn't find any articles that truly excited me. If CACM hopes to become the "first magazine I want to read each month," it will have to take more risks, producing articles that give new perspectives to up and coming topics in computer science and lead the field instead of just reporting on it.

June 30, 2008

A Rademacher comparison theorem?

Given Rademacher variables \epsilon_j , what can we say about
 \mathbb{E} \sup_{c > a_j \geq 0} \left|\sum_{i=1}^n \epsilon_j a_j \right| versus \mathbb{E} \sup_{c >a_j \geq 0} \sum_{i=1}^n \epsilon_j a_j ?

Anything?

Restructuring logicomp

I'm thinking of restructuring my blogs. I've recently found that things have changed a lot since I started my break a year or so ago: Lance has retired from blogging, Andy D has started his new cool blog, and Luca Aceto has his blog. Ah ... also I'm having a lot of difficulty deciphering blogger's word verification mechanism.

Unfortunately, I've become really rusty with HTML and will have to start getting used to it again. Shocked with what a long break can do to one's dexterity ;) Anyway, I'll put all the new links some time soon.

The Special Issue Debate

A commenter requested a written post on the special issue debate (our podcast already has it but he or she and others may have a hard time accessing our words of ... wisdom(?)). Here are all the opinions that I heard at the meeting and later. I do not attribute them since we are not yet at the point where making a good point at a meeting is something to put on your resume.
  1. Background: The special issue for CCC (and most theory conferences) had been JCSS (Journal of Computer and Systems Sciences) for many years. When prices began going up many theory conferences switched to non-commercial publishers, some affiliated with societies like SICOMP. CCC went from JCSS to CC (Computational Complexity) which is owned by Springer, a commercial publisher. Laci Babai has been running Theory of Computing: An Open Access Journal and he wants us to switch to his journal or to have some kind of rotating system. von zur Gathen who is the editor of CC wants us to stay at CC. The steering committee wants to DECIDE and STAY with someone for the next 5 years so we don't have to keep having this debate.
  2. The goals of a commercial publishers are at odds with the goals of the community. We want our work out there and available. In particular we want out work to be available free online or at a cheap price on line. They want to make money. Therefore we should switch to a non-commercial publisher, as many other theory conferences already have.
  3. The distinction between commercial and non-commercial is silly. There are some non-commercial publishers that are not very good (IEEE was brought up). Nobody seemed to be able to bring up the other kind of counter example- a commercial publisher that was very good. von zur Gathen says that CC is reasonably priced but he admits that Springer does overprice other journals.
  4. CC is not free online. However, if we go with them they will put the special issue free on line after a year. And they will (as they did this year) provide us with free copies of the journal at CCC. Should we threaten every year to get more and more out of them? One participant told von zur Gathen directly: You make the entire journal free online 6 months after it appears and I will vote for CC.
  5. There is something about paper that feels more permenent then just being online. Formats change but paper lasts forever. Then again, Google Caching also lasts forever.
  6. Does Theory of Computing: An Open Access Journal have sound financial backing? Laci claims that even if Univ of Chicago blew up tommorow the journal would keep going. However, the journal has not set up the proper paperwork to accept donations.
  7. Will Springer raise the price of CC? So far they have not and they regard it as a prestige journal so they are willing to break even. Will this last forever? But even in its current state, there are schools that do not have access to it, while all people have access to TOC:AOAJ.
  8. ACM has a new journal Transactions on Computation Theory. This would seem to be a good place to have the special issue. Non -commercial, sound business model, ACM support. But it has not produced a single issue yet. The editor, Lance Fortnow, said he is not seeking the special issue. Since this is an election year it is not clear what that means.
  9. The Special Issue of CCC is 1/4 of CC's issues. We are making them prestigous, not vice versa.
  10. Rotating seems complicated; however, if we can just have on the CCC website to click here or there to get that years special issue, that could be okay.
  11. When the editors raise prices we don't like it. But when the lower them or agree to put things online, thats a bribe. They can't win. Well- if they just put EVERYTHING online and cheap then we will stop complaining and threatening. If they can't find a way to do that and make a profit they should not be in the business.
  12. There should be a special issue to honor the good papers and also (and this is a topic for another day) make sure that conf papers get into journals- our field has been bad about that.
  13. At the meeting there was a ranked vote: You could vote CC, TOC:AOAJ, write in (likely Transactions), or to rotate. If you voted rotate then you had to say which journals. (E.g., Every year that is a Fiboacci Prime, we got to CC, Fib non-prime TOC:AOAJ, all else: TRANS.) The results of the vote will be posted online.
  14. Laci gave his presentation on overheads.

Ideals in Banach algebras

I came across the following statement while reading Murphy’s book (Theorem 1.3.1): “If I is a proper ideal in a Banach algebra, then \overline{I} is also proper.”

Quick recap: a Banach algebra is a Banach space with a multiplication operation, such that the norm is submultiplicative (\|ab\| \leq \|a\|\|b\|). A prototypical (non-abelian) finite dimensional Banach space is that of all n\times n matrices with the spectral norm, and a prototypical (abelian) infinite dimensional Banach space is that of all continuous functions on \R with the sup norm. An ideal is a vector subspace that ‘absorbs’ under multiplication: if a is in the space and b is in the ideal, both ab and ba are in the ideal. A proper ideal is one strictly contained in the ambient space.

This statement caught my eye because it gives a way in which ideals topologically differ from vector subspaces. It is easy to come up with examples of proper subspaces whose closures are the entire space; e.g. take the set of differentiable functions in the above infinite dimensional Banach space: every continuous function on \R is the uniform limit of differentiable functions, so the closure of this subspace is the space itself. It’s harder for me to come up with ideals nontrivially exemplifying the above statement.

The question is: exactly how does one use the multiplicative closure property of ideals to prove the above?

June 29, 2008

Fractal Science Kit

I heard from the creator of Fractal Science Kit during the week.

He wrote:

I have just released the Fractal Science Kit 1.0 and thought you might be interested in taking a look. The Fractal Science Kit provides an interactive programming environment with windows for viewing the fractal image, modifying the properties that define the fractal, examining the data behind the fractal, and viewing/editing the programs, macros (inline functions/methods), and color gradients, used by the Fractal Science Kit to produce the final image.

The programming language you use to develop your programs, supports a complete set of control structures including if statements, while loops, for loops, switch statements, inline functions/methods, arrays, and user defined objects. The complex data type is the fundamental variable type, and arithmetic operators and functions handle complex operands/arguments. A rich set of built-in functions/methods are included, and you can develop your own library of functions/methods for use throughout the application.

During the development of the application, I developed 100s of sample programs to illustrate how the application can be used to generate many different types of fractals including: Mandelbrot, Julia, Convergent, Newton, Orbit Traps, Sierpinski Triangle, IFS, Strange Attractors, Rep-N Tiles, Symmetric Icons, Apollonian Gasket, Circle Inversion, Schottky Group, Kleinian Group, L-System and many more.

For additional details visit Fractal Science Kit. The web site contains a complete description of the product and provides the full documentation, galleries, and tutorials.

I had a play with the software and found it to be more sophisticated than the other fractal generators I have come across. Here’s one of the first fractals I created. I love the swirls of white.

fractal

For those who are not sure what fractals have got to do with mathematics, check out Fractals and complex numbers.

That link again: Fractal Science Kit

June 28, 2008

A blessed man's formula for holey containers

I love the way derivatives of types tell you about holes in containers. It works the other way too and holes can give insight into derivatives.

Suppose S and T are containers so that S(X) and T(X) are containers of elements of type X. Then S(T(X)) is an S-container of T-containers of X's. If we draw S as a square (rectangle actually) and T as a triangle then we can draw a picture of an example of such a thing:


Taking the nth derivative of a type gives the type with (an ordered sequence of) n holes. Here's that previous container with 3 holes made in it:

As the holes have an ordering I've numbered them from 1 to 3.

An S-container of T-containers with holes is essentially an S-container containing both ordinary T-containers, and some T-containers with holes. If we excise the T-containers with holes, we're left with an S-container containing just T-containers, and some holes. Here's a picture of that:

But there are a couple of problems with that. Once we've excised the holey sub T-containers we don't know which S-holes to plug them back into and we don't know how to reconstruct the original numbering of the holes. We need to keep a tiny bit more information. That's the set I wrote down: {{1,3},{2}}. Call each element of this set a block. I've written the elements of the blocks in ascending order and I've written the blocks in ascending order of their lowest elements. The first block corresponds to hole 1 in the S-container and the second block corresponds to hole 2. Similarly, we write the elements of the blocks into the holes in the T-containers. And that allows us to reconstruct the original ST-container.

Think about the general case. We make n holes in an ST-container. So up to n of the T-containers acquire holes. Let's say it's m holes. We can think of the S-container having m holes and these holes being filled by T-containers with b1, b2,...,bm holes where the sum of the bi is n. We're essentially just partitioning the original n holes {1,2,...,n} into m sets. So each ST-container with n holes gives a partition of {1,...,n}, an S-container with n holes, and m T-containers where the ith has bi holes. Writing containers with n holes as nth derivatives we get
dn(F(G(X))/dXn = sum over each partition P of {1,...,n} of d|P|F/dG|P| times the product over each block B in P of d|B|F/dX|B|

Note that the equality above isn't just a numerical equality, it's an isomorphism of types. In fact, it's the type version of the 'combinatorial form' of the Faà di Bruno formula. Although that wikipedia page describes the formula as 'forbidding', if I've done my job right then I think the above picture make it seem almost trivial. I find it much easier to think of this version of the chain rule in terms of holes.

And the explanation for the title of this post: in 1988 Pope John Paul II beatified Faà di Bruno.

Google gadgets - cool extras for your website

Google Gadgets allows Webmasters (and bloggers) to include cool interactive stuff on a Web page.

You just find the gadget you want, copy its code, and drop it into your Web page (or blog post - but make sure you are editing the HTML and not using the WYSIWYG editor or it will mess up).

Here are some of the more mathematical gadgets that I found…

The date and time is taken from your computer’s system settings.

Here’s a nice geometric clock:

In June, the sun is directly overhead the equator, so there is 12 hours of day and 12 hours of night. In September, the sun has “moved” to sit over the Tropic of Cancer, where the equinox (equal day, equal night will occur.) In December, it is once again over the equator, and then in March, it is overhead the Tropic of Capricorn in the southern hemisphere.

Here is some simple arithmetic practice.

Sudoku, anyone?

And here’s some pictures from NASA to round up the collection:

That link again: Google Gadgets.

Pharell?

Tonight’s been an insomniac night, just checking out a bunch of blogs. Feeding the addiction :)

Anyhoo, in the background, I’ve been youtubing various people. For the first time I listened to some of Pharell’s stuff: I’ve been a fan of his forever, because he demonstrably doesn’t think that to be successful in the music business you have to conform to the Jay-Z, Lil’ Wayne, Soulja Boy, etc. stereotypes. He’s being him, doing him, and it’s working for him, same as his bff Kanye.

But I’d never heard his music before; here’s a little sample:


If someone had played these for me, I would have thought the first two were parodies; the third is OK, but can Gwen Stefani have some more lines? On to someone else…

Update: I think in the first two songs he was trying to get the same offbeat feel as when he’s part of NERD; I like what I’ve seen of their stuff. Here’s a good one:

Wells on Mathematical Language

Charles Wells, author (with Michael Barr) of Toposes, Triples, and Theories, now has a blog, gyre and gimble, devoted to how mathematicians use language.

He notes that the idea of completed infinity, which mathematicians take for granted, is still not well-liked outside of mathematics. The tone of the Wikipedia page on the subject (which consists mainly of quotes) tends towards the negative, for example.

June 27, 2008

Friday Math Movie - Math Test Anxiety

This week’s movie, Math Test Anxiety is a weird Japanese anime.

The video cleverly captures the nightmare that many students experience in the days before a mathematics test. Note how the stress manifests itself in the student’s rejection of his mother’s kindness.

Some of this movie is disturbing. It’s not pretty or fun.

You have been warned.

Loading Flash movie…

Complexity Conference Wrap

In the second half of our podcast (22:34, 20.6 MB), Bill and I talk about the debate over special issues at the business meeting between Joachim van zur Gathen, editor-in-chief of Computational Complexity (a Springer journal that serves as the current home of the conference's special issue) and László Babai, editor-in-chief of Theory of Computing (an open-access electronic journal). Watch this space for the results of the vote taken after the debate.

Bill and I also talk about Richard Beigel's report on the not-too-bad state of theory funding. An important warning: Regular theory proposals will have a fall deadine, well before the deadlines over the previous few years.

Evan Golub set up a Flickr group for pictures from the conference and uploaded some he took from the business meeting. Feel free to upload your own pictures from the conference.

I really enjoyed the conference for several reasons. For the first time since 1995 I didn't attend the conference steering committee dinner or have any other major responsibilities. I did serve on the PC and hosted the first session, but pretty much I could just relax and enjoy this meeting. Also for the first time since Amherst in 2004 we had the conference by ourselves on an American college campus allowing a very relaxed atmosphere. I really had a chance to talk over some neat research problems and catch up with old friends including a very large presence of former Chicago students. No new theorems for me this week but plenty of neat problems to think about.

Now I go home, switch hats, and get ready for the upcoming Electronic Commerce Conference in Chicago.

See you all at next year's Complexity Conference in Paris!

June 26, 2008

On being local on the local org comm.

Comments on being on the local arrangements committee for CCC 2008.
  1. The local arrangements comm. was a joint effort with Richard Chang and Marius Zimand. Always good to have people checking each other.
  2. Lisa and Allison from the Conference and Visitor Services did alot of the nitty-gritty work like reserving rooms, buses, setting up websites, and being around. They have my sincerest thanks. The two student volunteers, Martin and Nicholas, were also helpful.
  3. Pierre McKenzie (Steering Committee Chair) and Paul Beame (Program committee chair) made alot of the decisions. This was Great!.
  4. Before, during, and after the conference I kept wondering is there something I should be doing?. The wondering was tiring, so if I fell asleep during your talk, thats why.
  5. There were many decisions that had to be made. Where on campus to have it? What layout should the room have? Bagels at Breakfast? What should go in the tote bag? What should be the logo on the tote bag? On the name badges? What hotels to use? What time should the shuttle bus be? What time should the business meeting be? Some were important. Some were not. but it drove me nuts and it never seemed to end.
  6. The hardest thing was making up the budget. It has to be based on how many people we think will come. Past attendence is some guide, but hard to say how good. (We got 81 which was good.)
  7. I got to go to the steering committee meeting this year and last year. I saw the corridors of powers! Alot of thoughtful (i.e. long) discussions on alot of issues- major and minor.
  8. Instead of saying `Sasha, congrads for winning the best student award!' I said `Sasha, make sure you fill out the forms to get your money!' Being local arrangements people changes your viewpoint.
  9. I am happy nothing went wrong. Before the conference I thought What if we have a loss? What if we have a profit? What if I go to jail--doing a nickel for being falsely accused of ripping of a conference..., Will the room be good?, Will the dorms be good? Will the hotels be good? and of course Will there be enough bagels?.
  10. Pierre, Paul, Lisa--Is there something I should be doing?

Two Years and Big Changes

Whew.  How are you all doing?  It's been a while, I realize.

I'm making some changes to my blogging.  I will now maintain not just one, but three blogs.  This one will be solely for more advanced and interesting mathematical content.  In particular, I plan to continue expanding the AHSMP, but I will also continue to post other mathematical content of interest.  My math posts get by far the most hits, and I didn't want to continue muddying the mathematical waters with personal content.  New blogging about teaching and my personal life will now appear on my first new blog, Math Spectrometer (so named because I'm identifying the elements of my math life—quite the geeky pun, I know;  my father the physicist will be proud).  Previous posts will not be deleted from this one, though.  Also appearing on the new blog are my "greatest hits";  namely political, personal, and teaching-related posts that have either gotten a lot of traffic or are my personal favorites.  Finally, my third blog (which I haven't started yet...UPDATE:  it's here, but under construction!) will contain a) explanations of more basic high school math concepts (most that I find online are frankly not that good) and b) links to the book chapters I will someday write that will be available for sale via print-on-demand publishing.  My experience with math textbooks so far has been somewhat disappointing;  I may be kidding myself, but I think I can do better.  The reviews of my math writing on this site have been pretty good, so we'll see how that goes.

On a different note, this week marks the 2 year anniversary of the post that put me on the blogging map.  It's the one about how .999... equals 1.  When it was picked up on the front page of Digg, I was getting many hits (over 25,000 on one day).  During that time, I was on a road trip with my wife, and we met some of her friends whom I told about the post—my jaw dropped when one of them said, "Wait, that was you?"

The post inspired over 1000 comments, many doing their best to discredit the mathematical fact, and many more trying to convince those disbelievers that I was right (a shout out to Monimonika who has kept up with almost all the naysayers:  thanks, and you're off the hook now:  see below).  It inspired several other explanatory posts and a rant or two from me (you can link to them from the main post).  I have seen many, many discussion boards on which the topic appeared, and on which the inevitable arguments broke out, many of which made attempts to settle them by linking to my post.

Perhaps most tellingly, as of today, Googling the phrase ".9 repeating equals 1" (among other phrases) lists my page as the number one hit—above Wikipedia's entry on the topic!

Occasionally, there have been people who were convinced by the arguments after initially disbelieving the facts.  More often, comments by disbelievers on discussion boards amounted to "that guy is an idiot".  They will, I'm sure, continue to argue there.  But I've made the decision that the discussion on my site is over.  I'm closing all posts in that thread to comments, and comments about it on any other thread will be deleted.

So...I hope to see you all here for more math and at one or both of my new blogs (links on the sidebar at some point soon).

June 25, 2008

A polynomial inequality (and some whining)

Arghhh!!! I have a meeting tomorrow with my advisor to discuss my progress in research over the past month or so, and I have nothing interesting to mention– partly because I haven’t spent as much time as I could have, but mostly just because I’m slow and dense. I just gave up on the two problems I’ve been looking at, since I’ve gotten nowhere on those, and am now reading his paper on the linear independence of spikes and sines so I can work on another idea he suggested. Namely, to adapt the technique used in the paper to get a bound on the expected spectral norm of a random rectangular submatrix of the Fourier matrix. I can’t get anything done on this tonight besides reading, but it looks interesting.

Question of the night: Let  p(t) = \sum_{k=0}^r c_k t^k , show that the coefficients of the polynomial p satisfy the inequality
 |c_k| \leq \frac{r^k}{k!} \max_{|t| \leq 1} |p(t)| \leq e^r \max_{|t| \leq 1} |p(t)|.

It may help to look up Markov’s inequality for polynomials (bounding the derivatives of a polynomial in terms of the Chebyshev polynomials), and try to prove that.

Numerical Rank

I spent today looking through several papers. Most of them were about finding graph sparsifiers by sampling– apparently this relates to a generalization of the sparsification problem I’ve been thinking about, where instead of looking for a sparsifier in the spectral norm, you look for one in the \infty \rightarrow 1 norm.

I snuck in a paper by Rudelson and Vershynin, to gain some familiarity with the more typical tools in this area, and came across the neat idea of the numerical rank of a matrix: r(A) = \frac{\|A\|_F^2}{\|A\|_2^2}. It’s clear that this satisfies 1/n \leq r(A) \leq \text{rank}(A), but it’s also stable in the sense that if A is close to a low rank matrix, then r(A) is also low. I’m looking forward to seeing how they use this quantity.

Some Schatten norm stuff

Recall the Schatten p-norm of a matrix A:  \|A\|_p^p = \sum \sigma_i(A)^p, where \sigma_i(A) > \sigma_{i+1}(A) are the singular values of A. They’re interesting, among other reasons, because they’re unitarily invariant. Schatten and Von Neumann came up with these while investigating matrix analogues of the finite \ell_p spaces— they’re the \ell_p norms of the vectors of singular values.

Show that \|A\|_p^p = \text{trace}(|A|^p), where |A| = (A^\star A)^{(1/2)} is the modulus of the matrix.

Note that the Schatten 2-norm (aka Frobenius norm aka Hilbert-Schmidt norm) can be easily calculated \|A\|_2^2 = \sum_{i,j} |A_{ij}|^2, and is actually induced by the inner product \langle A, B \rangle = \text{trace}(A^\star B) . When A is positive, show that \|A\|_1 is also easily calculable: \|A\|_1 = \text{trace}(A).

Can you show that Schatten p-norms have the dual norms you’d expect from analogy with the usual \ell_p norms? It’s fun :)

Can you think of any other interesting properties of the Schatten norms?

Greasemonkey hack for CiteULike article removal

One crucial feature that CiteULike lacks is the ability to remove entries en masse; the only way to remove several entries is to go to each entry’s page, click on delete, and confirm the deletion– that’s about 3 clicks per removal. Imagine if you want to remove *all* of your entries!

That was the problem I encountered as I attempted to clear my account of all the papers not related to my research, so I decided it’d be worth the time to write a little Greasemonkey script to remove all the entries. Unfortunately, in addition to being very out of practice with Javascript and the DOM, I’ve never used Greasemonkey before, so I ended up writing a two-script hack. The first script loads the first entry on my CiteULike library page, and the second script deletes any entry once its page is loaded; together they eliminate entries one by one until none are left. Inelegant, but much more inefficient than doing it by hand.

Here’s the code for the two scripts– just remember to retask them to point to your citeulike account, and to DISABLE under Greasemonkey or delete them after you’re done.

// ==UserScript==
// @name           First citeulike article
// @namespace      http://tangentspace.net
// @description    Loads first citeulike article
// @include        http://www.citeulike.org/user/swiftset
// ==/UserScript==
 
articlelist = document.evaluate("//div[@class='list']", 
document, null, XPathResult.UNORDERED_NODE_SNAPSHOT_TYPE, 
null).snapshotItem(0);
 
allarticles = document.evaluate("//a[@class='title']", 
articlelist, null, XPathResult.ORDERED_NODE_SNAPSHOT_TYPE, 
null);
 
document.location.href = allarticles.snapshotItem(0).href;
// ==UserScript==
// @name           Delete Citeulike Article on load
// @namespace      http://tangentspace.net
// @description    deletes any citeulike article on load of the article info page
// @include        http://www.citeulike.org/user/swiftset/article/*
// ==/UserScript==
 
allhidden = document.evaluate("//input[@name='user_article_id']", 
document, null, XPathResult.UNORDERED_NODE_SNAPSHOT_TYPE, 
null);
anelem = allhidden.snapshotItem(0);
 
document.location.href="http://www.citeulike.org/delete?user_article_id="
+anelem.value+"&"+"from=%2fuser%2fswiftset";

In which a feminist confuses transsexuals with transgendered and hates them both

Occasionally I come across so-called feminist blog entries that strike me as particularly vile. Today, one of the articles in the latest Carnival of the Feminists linked directly into the blindered underworld of ‘feminists’ who ascribe everything to twisted male sexuality and the desire for dominance.

In this case, the nominal topic is transgenderism, but it quickly devolves into an attack solely on transwomen:

When transgendered folks get through the final stage of transitioning and reach “the end”, all that gender fluidity goes right out the window and solidifies into the crusty crud on the bottom of my boots.

Since you do not need a penis to pick up a hammer, since you do not need a vagina to vaccuum, or validate virility, vanquish vasselage, or *oh my!* vounch for volition, there is also no corresponding need to switch out body parts in order to express what is basically described as internal character, unless the purpose is merely to commodify one’s personality as a dainty girl might wear pink or a goth craves black. The genitalia have been reduced to the status of wardrobe accessory.

And since these folks insist they’re not swapping out genitalia for masturbatory fetish purposes, there too is no need to accessorize oneself with the preferred genitalia of their romantic partner unless they’re also prepared to reverse the surgery again, when they meet someone new who wants yet different genitals to play with.

So many things are wrong with this post, starting with the fact that she confuses transgenderism with transsexualism. One would think you’d take the time to familiarize oneself with the difference before you start spewing vitriol. There’s just too much to shake my head at to even begin deconstructing her ‘arguments’.

Question: RightStart, Singapore, or Math Mammoth?

I was asked this kind of curriculum question recently, and I thought I'd post it here too in case there are others who will get helped...

I am torn between using Right Start, Singapore, or Math Mammoth with my daughter who is just starting her schooling journey. Do you have any insight to share that might help?

Yes. If you are torn, try Singapore with Math Mammoth (if you can afford both). I've heard from people who use both and say they go well together, because Singapore is somewhat lacking in practice exercises.

There are lots of folks who use two curricula for math. You would basically use one of them as your "spine" that you go by, and then for each topic, check the corresponding lesson in the other, if it has good explanations or problems. You wouldn't do all problems in both.

Then, if you like RightStart, buy their math games book (but not the whole curriculum), which allows you to incorporate their games into your math lessons here and there.

Podcasting from the Conference

Bill and I revived the Complexitycast by talking about the Complexity Conference. The discussion ran long so we will post the podcasts in parts. In Part I (18:33, 16.9MB) we talk about the award winning papers: and the beginning of the business meeting including future Complexity Conferences in Paris (July 7-10, 2009) and Cambridge, Massachusetts co-located with STOC in 2010.

Nilpotent Infinitesimals II

This is a follow-up to this post.

Nilpotent infinitesimals allow you to define objects like the “double point”, which is the solution set of x2 = 0 on the line. Intuitively, the double point is the point x = 0, plus another point infinitesimally close to it. We can mimic this in nonstandard analysis by considering the solution set to x(x-h) = 0, where h is an infinitesimal. This has the property that if you evaluate any differentiable f at h, you get

f(h) = f(0) + f’(h) + o(h),

which also holds for nilpotent infinitesimals if you drop the o(h) term. (Here, a nonstandard number k is o(h) if k/h is infinitesimal.)

We can follow the same route to define the intersection of two double lines in the plane as the solution set to x(x-h) = 0 and y(y-k) = 0 where h and k are infinitesimals. In this case, we get a subtle difference from the nilpotent infinitesimal definition as the solution set for x2 = 0 and y2 = 0. In nonstandard analysis, xy is necessarily o(h) and o(k). If we neglect lower-order terms, we get the additional equation xy = 0 which is not satisfied by the intersection of two double lines defined using nilpotent infinitesimals. So seemingly we can’t simulate the intersection of two double lines using nonstandard analysis.

(Reasonably, you might think that maybe the nilpotent infinitesimal definition is just wrong, and that the intersection of two double lines really does morally satisfy the equation xy = 0. Just counting points, the intersection of two double lines should be some sort of quadruple point. For an ordinary set of n points, the ring of all differentiable functions from a set of four points to the real line is a vector space of dimension n. Nilpotent infinitesimals preserve this property: the ring of differentiable functions on the intersection of two double lines is a vector space of dimension 4, spanned by 1, x, y, xy. The nonstandard simulation by neglecting lower-order terms gives you a vector space of only dimension 3, spanned by 1, x, y.)

Complex Cobordism and the Stable Homotopy of Spheres

Doug Ravenal has made the latest version of his book Complex Cobordism and the Stable Homotopy of Spheres available online.

June 24, 2008

Rihanna

Shhh! Don’t tell anyone … I’m a Rihanna fan. I used to think she can’t sing, but I’m steadily losing that conviction– her voice still isn’t the greatest, but maybe she’s been taking lessons, or I’m being brainwashed by the media saturation.

At any rate, my stanness is not predicated on her singing talents: I still can’t listen to most of her songs unless they’re accompanied by the video (or should I say, unless they accompany a video? :) ). Mostly, it’s that I’m so damn proud of her; what other international stars do we Barbadians have claim to? The other part is that she is the sexiest high profile female musician I can think of, and she manages to stay on the right side of the thin line between sexy and trashy. A lot of her attractiveness is her incredible body, but her accent adds a final je ne sais quoi.

Actually, I guess I do know why her accent is so attractive: she comes across as laidback and approachable, the Barbadian girl-next-door.

Non-standard analysis in economics

I see, via Yet Another Sheep, that nonstandard analysis has spread to mathematical economics. Robert Anderson has a book manuscript available, Infinitesimal Methods in Mathematical Economics which explains how to apply nonstandard analysis to approximate economies with large numbers of agents. The main technique is Loeb measures, which is something that I plan on writing a post on, once I actually know anything about them.

June 23, 2008

Seven Dirty Words

In memory of the great George Carlin, we present the seven dirty words you cannot say at the Complexity Conference.
  1. Constants
  2. Algorithm
  3. Application
  4. Heuristic
  5. Competitive
  6. Implementation
  7. Wolfram

June 22, 2008

ACM Awards Banquet

With the kids at camp, after Iron Man, my wife and I hopped a plane to San Francisco. Did some wine tasting, saw some opera, played tourist (even riding the cable cars) all leading up to the ACM Awards Banquet on Saturday night.

While the ACM sponsors many conferences, there is no annual conference that covers our whole field. In non-FCRC years, they hold their awards ceremony at a nice hotel in San Francisco attended mostly by ACM officers and award winners. I was there as a new ACM Fellow to receive a certificate and the Fellow pin and have a rare chance to wear a tuxedo to a computer science event.

The highlight of the evening was, of course, the Turing award. The consulate general of France read a letter from the Ambassador congratulating Joseph Sifakis, the first French winner of the award. No such messages from the US for the two American co-winners, Edmund Clarke and Allen Emerson. But actually Daphne Koller netted the most prize money as the sole winner of the ACM-Infosys Foundation Award.

Many theorists among the award winners including Shafi Goldwasser as the Athena Lecturer (the lecture itself to be given at FOCS or STOC), Sergey Yekhanin (not present) winning the doctoral dissertation award and several other theory fellows. I also liked seeing the young people, including the ACM Programming Competition winners from St. Petersburg (Russia) and David Christopher Williams-King of Edmonton, the high school winner of the CS division of the Intel International Science and Engineering Fairl. Another highlight: David Harel describing how he co-won the Software System Award without writing a line of code.

This morning I hopped a plane across the country just in time to catch the end of the reception for the Computational Complexity Conference at the University of Maryland. On the plane I read the first redesigned CACM under Moshe Vardi's direction passed out at the banquet. More on the the Complexity Conference and the new CACM coming soon.

Singapore math - some research on its strengths

There is some interesting research from the American Institutes for Research on the Singapore math system.

The 2005 study “What the United States Can Learn From Singapore’s World-Class Mathematics System (and what Singapore can learn from the United States)” is a detailed investigation into what are the most likely reasons that Singapore does so well in international competitions like the TIMSS.

A summary:

Singapore Strengths
Framework: The study indicates there is a correlation between focused frameworks such as those used in Singapore and good test performance. Singapore offers an alternative mathematics framework for lower-performing students that covers all the mathematics topics in the regular framework, but at a slower pace and with greater repetition, and with support from expert teachers.
Textbooks: Singapore’s textbooks build deep understanding of mathematical concepts while traditional U.S. textbooks rarely get beyond definitions and formulas.
Teaching: Singaporean elementary school teachers are required to demonstrate mathematics skills superior to those of their U.S. counterparts before they begin paid college training to become a teacher. They receive a high level of professional development training (100 hours) each year.
Assessment: Singapore uses more challenging tests and utilizes a value-added approach that rewards schools for individual student progress over time.

This is a diagram representing the Singapore math framework they are referring to:

Singapore math framework

The summary goes on to list the US strengths.

U.S. Strengths: Although the U.S. mathematics program is weaker than Singapore’s in most respects, the U.S. system is stronger than Singapore’s in some areas. The U.S. frameworks give greater emphasis than Singapore’s to developing important 21st century mathematical skills such as representation, reasoning, making connections, and communication. The frameworks and textbooks also place greater emphasis on applied mathematics, including statistics and probability.

Go here for the complete paper (PDF).

A search of the AIR site for “Singapore” brings up several other interesting comparisons.

The 2007 TIMSS results are due in December 2008. With the changes in Singapore education since the 2003 TIMSS (Teach Less, Learn More and a shift to more collaborative and learner-centred approaches), it will be interesting to see if Singapore is still at the top of the heap.

BTW, you can test yourself on some of the TIMMS math questions up to grade 12 level. Good luck!

June 21, 2008

Dimensions movie

Jos Leys emailed me to let me know about Dimensions, a computer-generated movie illustrating dimensions 2, 3, and 4. The trailer is here. The whole movie can be downloaded for free at dimensions-math.org. (It is also available on DVD.)

The movie was rendered using POV-Ray, and is joint work of Jos, Etienne Ghys, and Aurélien Alvarez.

Update. John Armstrong has downloaded and watched the whole movie, and has posted a lengthy review.

Sustainability - a view from Nigeria

At the end of each fortnightly IntMath Newsletter, I sign it with “Please use your education for peace and sustainability.”

One of my readers from Nigeria, Claytus, replied and asked:

Talking about peace and sustainability, what exactly do u mean by sustainability and sustainability of what?

I replied to him:

Hi Claytus

Thanks for your question. Sustainability means treating the Earth like it should be treated - not cutting down trees faster than they can grow, not taking too many fish out of the sea faster than they can reproduce, not polluting the air with overpriced gasoline, and so on.

His response:

Thanks for responding. But are u taking into account the growth in population on global scale? Especially in the third world gov’ts and organisations prohibit the people from logging without providing alternative. Some how I agree with you but the realities at hand are frightening.

His reply got my attention, especially the “realities at hand are frightening” part. Yes, it’s all very well for developed countries to pontificate about sustainability because in many cases, it could just mean turning off the air conditioner or walking to work. But in developing countries, it’s about day to day survival.

I replied:

Hi Claytus

Thanks for your reply.

Yes, global population pressures are a huge issue and that’s why I have the population counter on the front page of Interactive Mathematics.

Please tell me more about what alternatives you think governments should provide when they ban logging. What happens in Nigeria? What should happen?

His answer:

Thanks. I think gov’ts should invest heavily on solar energy research. The investment needs to be honest and unbiased in the sense that they should not just give contracts to companies they have substantial interest in. Bearing in mind the enormous power global cooperations have, gov’ts should provide adequate security for the researchers and their families. They should also provide them with enough funds so that they will not look elsewhere. The research output should be made accessible and affordable to the common population especially in the third world.

And that’s a great answer.

Thanks, Claytus and thanks for giving me permission to use our conversation. All the best to you.

June 20, 2008

Karp Wins Kyoto Prize!

Fast breaking news: Karp wins the Kyoto Prize! See here
  1. Certainly deserved!
  2. Lets all congraduate him (hmmm- this may clog up his email.)
  3. Lets hope this gives some attention to computer science theory.
  4. Quoting from here about the philosophy of the prize it says Those worthy of the Kyoto will be people who have,as we at Kyocera, worked humbly and devotedly, sparing no effort to seek perfection in their chosen professions. Interesting- seems like you need to be a nice person as well as a brilliant scientist. As such, again, Karp deserves it.
  5. Its worth 50 million yen. 1 yen is 0.00942 dollars. So this is 471,000 dollars.

See you at CCC 2008!

Can still register for CCC08: Register here.

  1. BILL: Lance, maybe we should have an Anonymous Guest Blogger for CCC 2008 since I am one of the local organizers (along with Richard Chang and Maruis Zimand), hence anything I write might be biased, and we want someone who is free to complain about not having enough Bagels.

    LANCE: I can be a non-anoymous non-guest blogger. I have no problem complaining that there are not enough Bagels.
  2. After the conference is over I will blog about it from the point of view of one of the local organizers.
  3. HOPE TO SEE YOU THERE! If you don't know what I look like see this picture

How Much Time Do We Spend in the Bathroom?

I was wondering about the odds of having an open bathroom when you needed one, and it's very obvious that 2 bathrooms among 4 people is def. better than 1 bathroom among 2 people.

But I'd like to calculate some numbers for x people among y bathrooms. What's the longest you might have to wait? What are the chances a bathroom being open?

But to do this, I'll actually need some data.

Can anyone join me in recording their bathroom usage for a week? Just how long you spent, what you were doing (my reasoning for this data is that someone could urinate while you were showering, and there needs to be a little air time immediately after a defecation usually, for example), and what day it was on?

Thanks!

June 19, 2008

Friday Math Movie - How To Use the Quadratic Formula by Hector the Battle Droid

This week’s math movie is fun.

The title says it all…

Loading Flash movie…

A vision for collaborative mathematics platforms

Based on the extensive discussion at the Secret Blogging Seminar on tools for long-distance collaborations, Scott Morrison writes an introduction to source control with subversion for research collaborators.

In this post, Scott also offers, quite magnanimously, to setup and host subversion repositories for any mathematician who happens to want to start collaborating using subversion.

Which, to my mind, immediately prompts the question: why stop there? I’ve had ideas about setting up a free and easy to use platform for modern communication in the mathematical community before; but they were along the lines of duplicating wordpress.com’s efforts; which isn’t really something that pays off on your efforts. Reading this, though, raised a new idea.

Why not setup a server - preferably with a university data center as backing - which dispenses free platforms with the following contents:

  • Source control. Preferably option on subversion, git, mercurial - or some such selection of modern and wide-spread systems.
  • Wiki, Blog, Ticket system - a wordpress installation, with LaTeX, and a Trac installation connected to the source control system in use would do quite well.
  • Heavy access control: one of the worries I hear pronounced often is that running a blog with your mathematical ideas display the ideas to the world before you get to publish them, thus risking you getting scooped on your research. This worry would be, to some extent, ameliorated by serving things optionally over https, by having a decent and robust access control system, and by having draconian privacy statements for the site administration.
  • LaTeX compile farm - why not set this thing up so that it can build your papers for you? That way we really end up building the mathematician’s sourceforge!

So, I guess this post is a call for volunteer implementers. I’ll launch the ideas in the fora I have access to - I’m headed for a faculty retreat tomorrow discussing a research project which seems to include Web2.0 for research communication as a topic, and will see if I can propose the ideas there; and it’s just the thing to discuss with the workgroup Information und Kommunikation of the DMV too. But just because I’m looking for people who want to run this in no way implies anyone reading this shouldn’t.

Guest Post on App of Ramsey to Constraint Satisfaction

(Complexity Conference next week! Register Here)

(Guest Post by Manuel Bodirsky on a paper of his that applies Ramsey Theory.)

In a recent paper we apply the so-called product Ramsey theorem to classify the computational complexity of a large class of constraint satisfaction problems.

A *temporal constraint language* is a relational structure Γ with a first-order definition in (Q,), the linear order of the rational numbers. The problem CSP(Γ) is the following computational problem. Input: A *primitive positive* first-order sentence, that is, a first-order sentence that is built from existential quantifiers and conjunction, but without universal quantification, disjunction, and negation. Question: Is the given sentence true in Γ?

In our paper we show that such a problem is NP-complete unless Γ is from one out of nice classes where the problem can be solved in polynomial time.

The statement of the product Ramsey theorem that we use is as follows: for all positive integers d, r, m, and k > m, there is a positive integer R such that for all sets S1,...,Sd of size at least R and an arbitrary coloring of the [m]d subgrids of S1 × ... × Sd with r colors, there exists a [k]d subgrid of S1 × ... × Sd such that all [m]d subgrids of the [k]d subgrid have the same color. (A [k]d-subgrid of S1 × ... × Sd is a subset of S1 × ... × Sd of the form S1' × ... × Sd', where Si' is a k-element subset of Si.)

Review of Top Math Sites

HomeSchool.com recently released their Homeschool.com’s Top 100 Educational Web Sites of 2008. There were 7 math sites included in the Top 100.

What makes a Top Math Web Site? I’ve had a closer look at the 7 sites that were selected.

My comparison of the sites considers several factors:

  • What is the Content?
  • What Grade levels is the site aimed at?
  • Is there real-world context for the math?
  • Who is behind the site?
  • What does the site sell?
  • What are the top keywords for the site’s home page?
  • Does the site have valid HTML?
  • Does the site have valid CSS?
  • How popular is the site?

Of course, I have kept in mind the needs of home-schoolers in my comparison.

The table was too wide for this post, so I presented it on a separate page.

Go to the Review of Top Math Sites. I hope you find it interesting.

June 18, 2008

In my day...

Can still register for CCC08: Register here.

(A reader emailed me the website and asked me to Blog on it.)

According to this, Math Exams in England have gotten much easier since 1951. The article also points to the exams the exams themselves so you can judge for yourself.
    The later exams look easier to me but not that much easier as to be a concern. The earlier ones had proofs, but the later ones had some concepts not on the earlier ones.
  1. Every generation tends to think that life has gotten easier since they were a kid.
    1. When I was a kid I we had to go to the library and copy articles! We didn't have your fancy websites and printers. And to get to the library we had to walk 5 miles in the snow, uphill, both ways. And we wore cardboard boxes on our feet for shoes.
    2. You had cardboard boxes!
    3. You had feet!
  2. Also, each generation thinks that the way they did things is the way things should be done Young people today don't learn how to use a Slide Rule. Wimps!
  3. But never mind what I think. What do you think?

FRA-Lagen och falska positiver

Jag har varit en god medborgare. Jag har börjat emaila politiker. Anledningen är gårdagens debatt och dagens återremittering av FRA-Lagen.

Kärnan i mitt email, efter en personaliserad inledning där jag återknyter till vardera riksdagsledamots insats i debatten, är följande argumentation.

Tanken med signalspaningen är att analysera trafikmönster, läsa innehåll,
och hitta allmänna mönster. Dock är inga av dessa metoder 100%
tillförlitliga, och det man vill hitta är väldigt ovanliga företeelser.

Problemen härvid är framför allt:
1) mönster är väldigt lätta att dölja. Det finns många och relativt
välkända metoder att bygga upp sina kommunikationer så att trafikanalys
blir i det närmaste värdelöst: man kan se till att alltid skicka massa
data åt alla möjliga håll, och därvid skicka mycket skräpdata, så att
när det väl skickas värdefull data så är det ingen skillnad i
trafikflödet.
2) kryptering är lätt att använda. Det finns många mjukvarupaket för att
kryptera all möjlig elektronisk kommunikation. Vi använder det för
bankärenden, för företagsintern kommunikation, och det är lätt att
använda för privata ändamål. Därigenom kan den som vill gömma sig
väldigt lätt göra all sin kommunikation oläsbar.
3) imperfekta metoder kommer dränka övervakaren i falska anklagelser.
Den internationellt kände säkerhetsexperten Bruce Schneier har
diskuterat det här fenomenet utförligt i sitt nyhetsbrev. En av de
bästa genomgångarna jag känner till finns här:
http://www.schneier.com/blog/archives/2006/03/data_mining_for.html

Kontentan av den artikeln är att även en väldigt låg förekomst av
falska positiver ger ohyggligt många falsklarm om datamängden är stor,
och mängden sanna positiver väldigt liten. Just terrorismbekämpning är
Schneier’s kardinalexempel: och han argumenterar med trovärdiga
uppskattningar att även en absurt låg sannolikhet för falsklarm -
0.00001% - kommer generera många tusen falsklarm per dag med ett
automatiserat kommunikationsövervakningssystem.

Med andra ord, inte bara är FRA-lagen ett ohyggligt djupt intrång i den
personliga integriteten och friheten. Det finns heller ingen möjlighet för
de angivna ändamålen att någonsin faktiskt infrias.

MvH,
Mikael Vejdemo Johansson
Matematiker

Jag räknar visserligen inte med att det hjälper, men det är ingen ursäkt för att inte försöka.

Brouwer Fixed Point Theorem

One idiosyncratic interest of mine is mathematical economics. I was looking through Volume 2 of the Handbook of Mathematical Economics when I spotted a paper by Scarf called “The Computation of Equilibrium Prices: An Exposition”. The real subject of the paper is an incredibly clear exposition of how to find fixed points of maps of the unit n-cube to itself. The Brouwer Fixed Point Theorem promises that at least one fixed point exists. I knew that there was a combinatorial approach based on Sperner’s lemma, but it had always struck me as rather technical. Not so; Scarf gives a straightforward algorithm for finding the fixed point. Sperner’s lemma is just the result that dictates that the algorithm terminates.

The proof is stated for an n-simplex, which is the n-dimensional analogue of a triangle. The algorithm works by cutting up the simplex into smaller simplices, and identifying which of the smaller simplices contains a fixed point. It then repeats, trapping the fixed point in smaller and smaller simplices until it eventually converges. What’s interesting is that the test for whether a particular simplex contains a fixed point is fantastically crude; it amounts to just checking a simple condition on the map at the vertices. (The condition is not satisfied for every simplex containing a fixed point, and in fact the algorithm will miss some fixed points. At least one fixed point will satisfy the condition, though.)

The article does everything from scratch. Brouwer’s theorem is derived as a consequence of the algorithm. It is simple enough that it could easily be included in an undergraduate analysis textbook. The whole article is so simple that it makes me wonder if there is an elementary combinatorial subject lurking under the intimidating algebra of modern-day homology theory. An interesting test case is if a constructive version of the Lefschetz fixed point theorem. (Lefschetz’ original proof was apparently combinatorial, but extremely difficult to follow. I doubt it was constructive.)

Here is two artists’ take on the Brouwer fixed point theorem.

Update. Commenter Mio spotted this elementary introduction to the topic on Herb Scarf’s web page. Poking around some more, I found the original article I mentioned above here.