ROSE 1995

What I remember from the first computer-related conference I attended.

IMO 2014 problem 1

This is an exercise proposed by Timothy Gowers: Write down all you think of while trying to solve a math problem.

Some Random Code Metrics

How compressible is source code? What is the average size of a file? The answers to these and other useless questions are born from too much caffeine.

The projects:

• Ant: A build system used by many Java projects, which is itself written in Java.
• CPython: The reference Python implementation, written in C.
• Frama-C: Analyzers of C programs, written themselves mostly in OCaml.
• FreeBoogie: A project of mine written in Java.
• GHC: The most used Haskell compiler, written in Haskell.
• jEdit: A nice source code editor, written in Java.
• Linux: An operating system macro-kernel, written in C.
• OCaml: Compiler, standard library, and related tools for the language OCaml, written in OCaml.
• SGB: A library for handling graphs and a few example algorithms written by Knuth in CWEB.

Methodology. Get the repo, spend $\le 1$ min choosing a subset of files that look like "the source", run a few quick commands in the shell, don't check the results. That's so you know how much you can trust what follows. Nevertheless, it's likely I got the orders of magnitude right.

Project size contest. The most common measure for a project's size is the number of lines of code. This comes with plenty of caveats. In any case, if we define "lines of code" to be "number of '\n' characters in the files that Radu happened to choose as the 'source'" then here are the results:

1. Linux: 9.1 million
2. GHC: 460 thousand
3. CPython: 450 thousand
4. OCaml: 260 thousand
5. Ant: 200 thousand
6. jEdit: 160 thousand
7. Frama-C: 126 thousand
8. SGB: 19 thousand
9. FreeBoogie: 8 thousand

There's an alternative measure that I like much better and that is not used much: the compressed size of the source code. Why do I like it? Because it should make a good proxy for the information content in the source code. For example, it doesn't matter much if coders use space indentation or tab indentation, long lines or short line, etc. There are plenty of caveats here too. For example, it is likely that the true information content (say, Kolmogorov complexity) is much lower, and that would be apparent if compressers would exploit the structure of the language in which the code is written.

Anyway, here is the bzip2 size of the projects.

1. Linux: 45 MB
2. GHC: 4.3 MB
3. CPython: 2.0 MB
4. OCaml: 1.2 MB
5. Ant: 930 kB
6. Frama-C: 735 kB
7. jEdit: 690 kB
8. SGB: 190 kB
9. FreeBoogie: 50 kB

File size contest. All these projects are broken up into files, which roughly correspond to modules or abstraction boundaries. The idea is that you should be able to focus on the internals of one file at a time without needing to know too much about the other files. And that is true of the compiler too, not only of you. Or, at least, that's one way to look at it.

So, lines per file contest:

1. CPython: 860
2. Linux: 680
3. SGB: 580
4. OCaml: 330
5. jEdit: 330
6. Frama-C. 300
7. GHC: 280
8. Ant: 260
9. FreeBoogie: 140

And compressed bytes per file contest:

1. SGB: 5900 B
2. CPython: 3700 B
3. Linux: 3300 B
4. GHC: 2600 B
5. Frama-C: 1700 B
6. OCaml: 1500 B
7. jEdit: 1400 B
8. Ant: 1200 B
9. FreeBoogie: 780 B

Information density. So, which project should I read if I want to get most per byte? And which one can be read on the bus without missing much? Well, here's information per character (where information is "measured" as earlier: compressed size, so these are basically inverses of compression ratios).

1. SGB: 0.25
2. GHC: 0.21
3. FreeBoogie: 0.19
4. Linux: 0.18
5. Frama-C: 0.16
6. jEdit: 0.16
7. CPython: 0.15
8. OCaml: 0.14
9. Ant: 0.14

Looks like GHC is almost as incompressible as the code Knuth writes.

People and Conferences ≥2000

Mini Me

Picasaweb Cameras

Which photo cameras make cool pictures?

I took a sample of 100 featured pictures from Picasa.

• 59 Canon
• 23 Nikon
• 18 others

Out of the Canon pictures, 27 where taken by EOS 5D Mark II, 8 where taken by various flavors of EOS DIGITAL REBEL, and 24 by other Canons.

Green Tree

Morning Schedule

This is my toothbrush hamiltonian path. What is yours?

Overflow

How do you use StackOverflow and MathOverflow?

I sometimes find answers on StackOverflow while googling for technical problems. For example, yesterday I wanted to know what is a good way to center code typeset with the LaTeX package listings. I didn't find out, so I'm stuck with nesting four environments: figure, center, tabular, lstlisting. Instead, I found someone asking on StackOverflow how to top-align two listings that go on the same row of a tabular environment. There were a few overly complicated answers, so I added mine (\lstset{boxpos=t}). Notice that it's more of a coincidence that StackOverflow got involved—I never planned to answer a question there. In fact, whenever I feel like helping random people and I go to StackOverflow or MathOverflow and click on "Unanswered" I end up sad because I never know how to answer any question.

So, do you use these websites? If yes, then how do you interact with them?

PS: In other news, expect this blog to be quiet until next year. I'm suppose to write a dissertation. Wish me luck.

My most beautiful result

A Good Companion

A short "review" for the The Princeton Companion to Mathematics.

The Princeton Companion to Mathematics Sample Entry: Fermat's Last Theorem Podcast interview with editor Timothy Gowers

Saturday I found a bookshop that I like. It has four floors: basement (bargains), ground (fiction), first (humanistic subjects), second (scientific subjects). This is contrast to the usual fiction and fiction bargains, plus some nude pictures counting as "art".

I stayed on the second floor for five minutes before deciding to buy The Companion. It is remarkable that it is expensive: 80 euro. It is also remarkable that within those five minutes two other people decided to buy it.

Compressed preface. The book leans towards examples rather than formalism. The core is a set of chapters on branches of mathematics that are being developed actively by today's researchers, such as, arithmetic geometry, numerical analysis, and theoretical computer science. Other parts worth mentioning are the concept index (useful for when you are too ashamed to admit you are completely lost in someone's argument) and the set of biographies of mathematicians. I'll let the other goodies surprise you.

My opinion after one hour. Contributors were chosen by expertise and expository skill so I was surprised to not see Knuth. I guess he's getting old and needs to finish his book. The typesetting uses Palatino fonts and is really well done. (Even the annoyingly small parentheses that Terence Tao uses have been fixed and now have the proper size. :p) OK, now let's get to less trivial things! The book is awesome! It's something I would have absolutely loved to have when I was in high-school and it's something that I will use as a bed-time reading for a while. It is very different in flavour from Knuth's books, though. It covers a lot of breadth and intuition but does not go into depth. That is intended, since in-depth study is fairly easy to carry on now that most scientific articles are available online. The big picture, however, can be acquired only by attending conferences, and few are lucky enough to be able to do it.

PS: It's a "review" and not a review because a proper review is done after you read the whole book. That won't happen any time soon.

Facebook Politics

It's interesting how otherwise smart people get worked up by irrational arguments, usually involving politics or religion. A colleague of mine was flooding my Facebook recently with basically this argument:

Treaty T is bad because:

• It is written by crooks in city F (F stands for "far away")
• It gives more power to people in city F and takes it away from people in city C (C stands for "close by" or "capital", your choice). Voters know more about the people in city C.

Now, if you didn't spot yet why this is insanely illogic, let me help.

First, let us make clear the assumptions:

• People in city F are crooks.
• We (voters) don't know people in city F well enough for an informed vote but we do know people in city C well enough for an informed vote.

This begs the question:

How do you know some people are "crooks" if you don't know enough about them?

The assumptions are inconsistent. That should be enough to make any logician puke. But let's assume only one of them is false.

So, first we assume that people in city F are crooks. So what? It doesn't follow in any way that treaty T is bad. A treaty is good or bad depending on what it contains, not depending on who wrote it.

Now let's assume they may be crooks but we don't know for sure because we don't know enough about them. How is that an argument against the treaty T?? Since people get their information through television, radio, and Internet the distance is completely irrelevant. Of course, it may be that media (who pushes information onto the sheepish voters) makes a bad choice in selecting what is important. That may very well be, but that's an argument against the media, not against the treaty. If the media would suddenly decide to only talk about the private life of Paris Hilton, does that mean that we can't vote for anyone else because we don't know enough about them? No, it means that the media is fucked up.

To make it clear, I am not arguing for the treaty for the simple reason that I did not read it. Before I read it I do not feel competent enough to preach to others how they should vote. However, I would prefer to see a little less fanaticism and a little more reason in my "inbox".

PS: Since I spent enough time on this spamming issue, be advised I will not read any comment on this post. Feel free to comment if you need to vent.

carnival 56

It seems the Carnival of Mathematics is trying to get back to life. Here's my modest help: a link.

Startups and the Crisis

Short reviews of a few websites.

For the past few months I've been told there's an economic crisis. I've also been told about a few startups. I would have thought that in hard times people are less inclined to risk. Can anyone explain me why the opposite seems to hold? While you think about that, I'll list the sites:

TaskWriter is a site for keeping track of what you need to do. Once you go to the website you see a "please wait while I'm loading" sign and while waiting you can read that you should use this site because it's the fastest. Now, that may sound ironic, and it is. Still, once the login box appears it gets much quicker. Registering is hassle-free. Once you get in you see that the main functionality of the website is to keep track of TODO lists where items are one line long. The obvious concern is: "Do I want my TODO list on some random website?" I guess the answer depends on whether you have something to hide.

EasyTrack is a site for Romanian companies that have many cars and want to track them. Why Romanian? Probably because maps are rented and it's expensive to rent good maps for everywhere. Why track the cars? To optimize costs. I hear that giving your employees cars as a perk may be costlier than it sounds. It's probably easier to abuse than a free lunch, anyway.

Balaurul (The dragon) is a search engine for jobs… in Romania. Now I finally see some correlation with the economic crisis: More people must be looking for jobs. I wonder if similar search engines are already successful in other countries. The business model is a little too Google for my taste: simple web design, attract ads. Usually cool stuff is different.

Disclaimer: TaskWriter and EasyTrack are the startups of two of my friends from college. I also met two of the three people that started Balaurul.

Others: My brother-in-law is starting a software development company, after being CTO for a long time in a company that provides software solutions for restaurants and hotels. Finally, three of my students will work for themselves for a while.

I hope many of these will be successful. I really do. All the people involved are high quality. Which makes me wonder what would happen if they would all work together. This must be a key ingredient in making a successful business: Getting many good people to work together. I wonder how you do that.

Interactive proofs

After a series of ego-enhancing posts it's time to get back to something better. I've read on the bus a popular paper by László Lovász. It must be shared.

Why read this. You could go ahead an read the paper I link to. Or you could continue reading this. This post contains the same ideas, is shorter, and is targeted to a (good) working programmer.

Factoring. Can you factor the integer 15? It's 3\times5. OK, that was easy. But I bet you'll find it harder to factor 2458520708919619073142040881007027206573813634042770527212029117113260478602067483 even if I tell you that it has exactly two prime factors. No one knows how to factor numbers efficiently. Yet, if I tell you that one factor is 6348726349827463298746322987643379 you can probably quickly verify that this factor is prime and figure out the other prime factor (by division). You can now even come up with a similar problem yourself, after you observe that primes are dense.

Electronic envelope. Lovász considers a scenario involving two people playing chess, Alice and Bob. It gets late and they must interrupt the game when Alice is about to announce her move. She doesn't want Bob to think about his move all night. So she wants to tell Bob her move now but put it in an envelope that Bob will be able to open only in the morning when she gives him the key. The solution is simple: Encode the move as a four digit number, find a big prime that begins with those digits, multiply it by an even bigger prime, and tell Bob the answer. Then Bob, in principle, could factor the number and look at the first four digits of the smaller prime. Fortunately, that's too much work for one night.

Hamiltonian cycle. Finding a Hamiltonian cycle in a graph is another hard problem, and we'll use it to illustrate even more magic.

Never tell your password. Really. Not even to a server to which you want to prove that you know the password. Suppose your password is a permutation of the first 1000 nonnegative integers. If two numbers are adjacent in your permutation then add the pair to an edge list. Then add more edges to the list to get a description of a bigger graph, in which your password describes a Hamiltonian cycle. Then your job is to convince the server that you know a Hamiltonian cycle in the graph (which both you and the server know) without leaking any information. Here's how it works. You choose a random permutation and apply it to your first 1000 nonnegative integers. You write down a shuffled an edge list that uses these relabeled nodes but otherwise describes the same reference graph and append at the end the permutation. You encode each edge as a big prime and also the permutation. You multiply all these big primes by other random even bigger primes and you send the resulting list to the server. Then the server asks, with equal probability, one of: (1) can you give me all the keys? or (2) can you tell me which edges are in the Hamiltonian cycle and give me the keys to those? When you answer the server will see either (1) the whole graph given in a relabeled form and the permutation describing the relabeling or (2) a cycle given using some unknown relabeling, which presumably would be a Hamiltonian cycle in the whole graph. Of course, you may get lucky even if you don't know a Hamiltonian cycle. But if you repeat this process 100 times and you can consistently answer the server's questions then, well, you just proved interactively and with zero-knowledge leaking that you know the password!

Edit. Replaced "Hamiltonian path" by "Hamiltonian cycle".

A bit of history

This my statement of research interests that I wrote in 2005 to get a PhD position in Dublin, with some minor subsequent editing. Those of you thinking about writing such a thing might find it useful.

Statement of Research Interests

The taste for formal methods (in a broad sense) was instilled in me by working on translators for languages equipped with formal semantics and by reading Dijkstra's notes. It was refined by learning functional languages from places like Didier Remy's lectures on OCaml.

But my background/history should be relevant too. I will start in chronological order with facts that have little to do with this particular position but that, I think, help you form a better idea about me.

My first computer was built from parts by my father, Corneliu Grigore, when I was 6 years old. It was based on Intel 8080 and came with a BASIC interpreter. It was a very pleasant experience for me to see that a machine made of metal and plastic can understand a rudimentary language and obey commands like DRAW 10, 10, 30. That is when I first got acquainted with loops.

When I was about 12 years old my father brought me two books: "Pascal" and "C++". He said that these are much better programming languages than BASIC and that I should probably start with Pascal because it is easier. So I read the book. Pascal still is the only language about which I have read a whole book but never wrote a line of code! I did not have a computer with a Pascal compiler. Then I read the C++ book and, when I was close to the end, I finally got a computer with Turbo C++.

If you are already getting bored be assured: there is only one more story from the (very) early days.

This story shows how I fell in love with simplicity. One day my father (yes, him again) showed me a problem he had at work. It was a real problem but in simple terms he had an adjacency matrix in an Excel spreadsheet and wanted all-pairs shortest paths so he could optimize a telecom network. In about 2 days I learned enough Visual Basic (for Applications) to write a solution to this problem. It was a backtracking algorithm (please don't say "yuck" -- I haven't read any book on algorithms at that point). It worked. A few months later there was a problem: my father wanted to do the same thing for 40 nodes instead of 20 but the program did not work anymore. First he thought that maybe there is some hidden 20 constant that he forgot to change so he asked me to take a look. I discovered that the program actually worked, only extremely slowly. I have spent a week trying to find a fast enough solution (I was about 15 years old). I have failed. In the process I even acquired a strong belief that it cannot be done. But my father knew better than to give up. A week later he gave me book by Tannenbaum and said: "Look at this section. It describes something called Dijkstra's algorithm and I think it might help." I took the book, with distrust, and read that section. I was flabbergasted! How could I have missed something so simple and beautiful and obviously correct for one whole week? After a few hours of coding the program worked flawlessly.

It is a story that I remember vividly because it taught me many lessons and influenced me a lot more than many formal lectures I have attended. I have learned that you should do your research when you try to solve a problem. As Newton put it: "If I have seen further it is by standing on ye shoulders of Giants." I have learned not to give up so quickly when trying to solve a problem. More often than not, what you need is a different mindset. Finally I have learned that the good solution is often much simpler than you suspect. So when you try to solve a problem, try to do simple things.

That's quite enough background on my early days. What have I done in college? I have a BSc degree in electrical engineering, my specialization being Telecommunication Networks.

I have used the computer as a tool for better learning. For example, to understand what was thought in the analog ICs lecture I experimented with various circuits by simulating them with SPICE. This kind of experimentation was useful for other lectures as well: Signal Processing, Computer Architectures, etc. I have used a wide range of tools: MathCAD, MATLAB, Mathematica, pure C, C++.

During a one month scholarship in Darmstadt I have developed, with a colleague, my first real program. The requirements were: "Write a program that we can use in a lab to teach the graph algorithms in this book. The students should be able to visualize the algorithms. You don't need to implement all algorithms, but design the program such that new ones are easy to add." We thought about two approaches. One was to define an interface (abstract base class actually — it was C++) and use the Adapter pattern. Why use an adapter? Well for each algorithm we usually had two components: one that talked in terms of "red nodes", "edge with tag 2", etc. and another that talked in terms of the problem, e.g. "source node", "destination node". That made it easier to reuse implementations of various algorithms — because those implementations knew nothing about GUI concepts. This is what we have actually implemented. It took two weeks. The other approach was seducing but, since this was our first real project, we were afraid that one month won't be enough for us to finish it. The idea was to design a language in which it is easy to describe various graph algorithms, while including information about how they should be represented. And then we could have structured the GUI as an interpreter.

Another adventure during college was a set of two completely unrelated papers I have presented at some "student conferences". One was about using mathematical methods from transmission lines theory to the study of quantum tunnelling and the other one was an extension of the network optimization problem about which I have already talked.

The first incident that made me like programming (the one with Dijkstra's algorithm) was also a lesson in humility. The second incident that made me like programming was a boost to my self-confidence.

Shortly after I have presented the network optimization paper, with practically no time to prepare, I have participated in the local phase of the ACM ICPC. I found out about its existence a week before and I was curious to see what kind of problems are given. Traditionally in my university, only CS (and no EE) student participated, so no colleague of mine could give me any details. I was very happy that after that phase and a few more tests I was selected to represent the university in the regional phase. After that I started to participate regularly in TopCoder and it is an entertaining experience. I have also started to populate my library with more CS-related books. As a result I have acquired The Art of Computer Programming, Programming Pearls, The Practice of Programming, Introduction to Algorithms, A Course in Combinatorics and other similar books that are a lot of fun to read.

My diploma thesis is written in Romanian. It begins by presenting theoretical concepts behind a fractal-like model of network traffic. Then it introduces a parameter (Hurst) that intuitively quantifies the burstiness of the traffic. I then present some standard estimation methods for this parameter. My idea was to implement a program that uses various methods to estimate this parameter in real time by watching the computer's network card. It turned out that the volume of computation required by the standard methods was to high to do anything in real-time. That's probably one of the reasons why at that time the real-time estimation was done only with specialized hardware (the other reason being that standard network cards aren't great when it comes to time precision). So what I ended up doing was a modification of one of the standard methods that allowed the real time estimation at the cost of some accuracy.

Finally, another good experience from college was being a teaching assistant for two courses: Data Communications and Networking Software. I was in charge with the laboratory sessions. For the Data Communication course I presented low level things about computer networks (e.g., data level protocols). The laboratory for the Networking Software course was actually an introduction to Java. The students were already in the 5th year of study but the lab is introductory because there isn't much programming going on in the EE department.

Since 2003 I work for Nobug Consulting. I was involved in three major projects: s2x, vfe, and e2vera — all of them translators.

On the s2x translator the team had two members (Valentin Gheorghita and me). The tool we wrote (4 months) constructs Verilog and AXE checkers from PSL properties. The most interesting aspect of this project was the fact that it was driven by theory. We started the construction of our algorithms from the formal semantics in the standard. The conciseness and clarity of those rules made me want to find out more about programming languages and the use of formal methods. The result was a high-quality program written much faster than management expected. Another result is a case-study paper.

The Verilog Front-End (vfe) was developed by me for two products of IBM Haifa Research Lab: Rulebase and FoCs. It was an interesting project from a software engineering point of view. I was very much pleased when the author of the requirements document wrote me at the end of the contract: "I am sure that IBM will use it for many years, and it is surely the best piece of software in our group from the point of view of software engineering." Apart from applying common sense, I have used design patterns extensively, I have commented the code thoroughly, I have used tools to compute software metrics like cyclomatic complexity and comments density to pinpoint places that need my attention. And I followed a process very close to what I describe on my blog, except the review part (since I was working alone).

The project on which I work now, e2vera, is a translator between to major languages used in hardware verification. Both of them are roughly the size of Java. The team had 8 members until recently (when two left). The code has a good quality, but lower than what I've seen on previous projects, probably because some of the members are novice coders. The fun part on s2x was the algorithmic part, the fun part on vfe was software engineering; here I have tried to enjoy functional languages by developing many helper tools in OCaml. For example I developed a small prototype to check if my algorithm for detecting translatable temporal expressions really works. To feed this prototype I have wrote a small tool that crawls a directory for `e' code and extracts (and anonymize) all temporal expressions it finds. Another small OCaml script computes cyclomatic complexity of functions. And so on. Not all auxiliary tools were developed in OCaml. I have also wrote a code generator (inspired by something similar that I've done on a smaller scale for VFE) that writes C++ code for the AST data structures starting from a succinct representation of the abstract grammar and a few templates. This mechanism is also used to automatically generate part of the visiting infrastructure. In fact I wrote this tool because when I joined the project the team had a parser and a big document describing about 200 AST classes that they were planning to write by hand! That document was written in good style, though, and we used it as input for my code generator.

In the last few paragraphs I'd like to say a bit more about what I do in my free time.

Recently I decided that it would be good for me to get involved into open source, so I started a project, for which I did not have much time lately (we released a beta version of e2vera recently). But it is an interesting project. First of all, if you write open source you know that others will see your code. This makes you try to be on your best behavior and this increases software's quality: it is more readable, more maintainable, etc. Second it is a good opportunity to practice using functional programming seriously. Functional programming is very important for the different, simpler mindset that it forces onto you. Reading code like the one in Chris Okasaki's Pure Functional Data Structures is sure to give you a new perspective on programming (at least if you came from the imperative realm). And third, it is a good way to practice coding more complex algorithms and data structure than any TopCoder could ever ask for (because of time constraints). Since it is a search application, performance is especially important. Advanced data structures are a must.

Other things that I enjoy: reading from TAOCP in the morning, solving puzzles from IBM, communicating over the Internet with people I don't know. In fact I think that browsing through mail archives can give you a good idea of various things that I've done in my free time at various times.

What I expect from a PhD program is a challenging and supportive environment. I want people to feed me with problems ("hey, I'm trying to do this, I've found this related literature; do you know some other results that might help me or maybe you have an idea about how to proceed?"). And I want people to which I can go with the same kind of questions when I am stuck.

I also like to program. Programming is a creative and very much enjoyable activity. So I want my PhD to involve some programming.

With respect,
Radu GRIGORE

P ≠ NP?

According to a dream that just ended it can be solved by applying Solomon's criterion to reduce it to Sauron's problem.

People

Happy Christmas 2007

source

British Telecom Ireland customer service

I moved in a new house recently. The owners had a BT phone and `broadband' (that is, ADSL). They left us two forms, one saying that we are taking over the line and the other asking what exactly is the service we want. I filled those saying that we only want Internet with 1Mbps download speed and sent the forms thru post to BT. Three days later the phone can be used only for inbound calls and the Internet doesn't work. (Doesn't work means that the router fails the PPPoE authentication. Note that I said router, not ADSL modem.)

So I call them. After waiting for five minutes someone answers but she doesn't seem to speak to me but with some colleague. After I say "Hi, hello, do you hear me" for another half a minute she eventually answers “Ah, so you where saying that there is a problem with the bill.” “Actually, you just answered so I didn't tell you my problem.” “Oh, sorry.” Then the line went silent for a few seconds. Later, the same voice. “Hello, how can I help you?” I explain that I moved into a house, I filled in a form saying that I take over the line and I want to check if everything is OK. “What is your phone number?” “I don't know it.” “What is your account number?” “I don't know that one either.” “Sorry, but we can't discuss any further details until you provide either the phone number or the account number.”

Good. I go thru my email, find the phone number (remember that I can't make phone calls so I can't just call my mobile) and call back a few hours later. This time I do not wait at all before someone answers. “Hello, what is your phone number?” I tell her the phone number. “What is your customer ID?” I explain that I'm not yet a customer and actually I'm calling to see if they received my form saying that I take over the line and hence became a customer. (Remember that the first BT representative said that I need the phone or account number, no mention of any customer ID. Otherwise I might have tried to contact the house owner.) “Sorry, you really need the customer ID.” “I don't think I need. In fact, I think I don't need your services at all. Bye.”

I wonder what other number they would ask for if I would insist to give them money. Competition is good.