Parallel Programming through Dependence Analysis - Part I

 “As soon as an Analytical Engine exists, it will necessarily guide the future course of the science. Whenever any result is sought by its aid, the question will then arise — by what course of calculation can these results be arrived at by the machine in the shortest time?”

Charles Babbage (1864)

Points to Ponder

Would it not be wonderful, if we could write all our simulations as serial programs, and parallelized code (highly optimized for any given supercomputer) would be generated automatically by the compiler? Why is this not the case today? How come supercomputing centers require teams of highly trained developers to write simulations?

Introduction

Scientists around the world develop mathematical models and write simulations to understand systems in nature. In many cases, simulation performance becomes an issue either as datasets (problem size) get larger, and/or when higher accuracy is required. In order to resolve the performance issues, parallel processing resources can be utilized. Since a large number of these simulations are developed using high level tools such as Matlab, Mathematica, Octave, etc., the obvious choice for the scientist is to use the parallel processing functions provided within the tool. A case in point is the parfor function in Matlab, which executes iterations of a for-loop in parallel. However, when an automation tool fails to parallelize a for-loop, it can be hard to understand why parallelization failed, and how one might change the code to help the tool with parallelization. Continue reading

How Connected are Quantum Graphs?

Some students in my department this quarter hosted a reading group on quantum computing. Quantum computing is becoming more and more relevant and the topic attracted the participation of a diverse group of researchers. The best way to handle the scope of the topic and diversity of the participants was to invite volunteer speakers to give talks on the quantum analog of their own research area — “Quantum Circuit Lower Bounds,” “Quantum Game Theory,” and “QPSPACE” were among some of the topics. Naturally, I saw this as a great opportunity to understand more about quantum spectral graph theory. In this post I will outline some basic definitions and properties of quantum graphs, and as a follow up to my previous post on the connections between spectral geometry and graph theory, discuss isospectral properties of discrete and quantum graphs. Continue reading

Software Packages for Theoreticians by Theoreticians

Brown University’s ICERM recently hosted a workshop titled “Electrical Flows, Graph Laplacians, and Algorithms,” where top researchers convened to present and discuss their recent progress in spectral graph theory and algorithms. Richard Peng opened up the workshop with an overview talk on efficient solvers for linear systems with graph Laplacians as the coefficient matrix. He presented a thorough history of the topic and set the stage for the variety of technical talks on fast algorithms for graph sparsification, spectral clustering, computing max flow, as well as a variety of other local and approximation algorithms.

His talk (as well as many of the rest) are archived and available thanks to ICERM. I will focus on one highlight – a point that resonated with the conclusion of Richard Peng’s talk – a call for more software implementing these new, fast algorithms. In this light, I’d like to briefly discuss some of the software packages out there for spectral graph theory and the analysis of large graphs being developed by theoreticians active in the area. Continue reading

Personal Recommendation Engines

In the last decade the Internet has come to dominate how we consume information. News, entertainment, and even education, are often a click away. If you know what you want, a few typed words can lead you to the webpage you seek. But what if your search is less concrete? What if you are looking to find inspiring, new, undiscovered content to consume? You could certainly ask a friend, or you could ask a personal recommendation engine. Continue reading

The Evolution of Local Graph Partitioning

As a follow-up to my previous post on the discussion of where theory and experimentation meet in the study of large-scale networks, I would like to discuss in more detail one of the empirically best-performing algorithms which also has a sound theoretical background: spectral partitioning. In this post I will examine the history of the problem, outline some key results, and present some future ideas for the problem. Continue reading

Demystifying the Fourier magic

Over the years I have gotten used to seeing many theorems in theoretical computer science being proved using discrete Fourier analysis. The Walsh-Fourier (Hadamard) transform of Boolean functions proved to be extremely useful in virtually every subfield of theoretical computer science, including PCPs, property testing, pseudorandomness, and communication complexity. As it turns out, many seemingly hard problems can be solved by writing the Walsh-Fourier expansion and using basic theorems of harmonic analysis.

While I have gotten quite comfortable using Fourier analysis when trying to tackle a problem, and even though I developed a pretty good hunch for which cases Fourier analysis should yield nice results - I have to admit that it took me a long time to begin to unravel the Fourier magic; that is, to understand what is so special about the Walsh-Fourier basis that makes it so powerful.

For the rest of this post, I assume that the readers have some proficiency in Fourier analysis. However, in order to make this post (hopefully) a bit more accessible to readers who are new to harmonic analysis, I would like to dedicate the rest of this paragraph to stating out some basic definitions and facts regrading the Fourier transform. Say we have a real function on the hypercube $latex {f:\mathbb{Z}_2^n \rightarrow \mathbb{R}}&fg=000000$. The Walsh-Fourier expansion of $latex {f}&fg=000000$ is defined as follows:

$latex \displaystyle f(x) = \sum_{S \subseteq [n]}\hat{f}(S)\chi_S(x), \ \ \ \ \ (1)&fg=000000$

where the characters $latex {\chi_S: \mathbb{Z}_2^n \rightarrow \mathbb{R}}&fg=000000$ are defined by

$latex \displaystyle \chi_S(x_1, \ldots, x_n) = (-1)^{\sum_{i \in S} x_i} \ \ \ \ \ (2)&fg=000000$

(note that the summation in Eq. (2) is over $latex {\mathbb{Z}_2^n}&fg=000000$, and that the coefficient of each character $latex {\chi_S}&fg=000000$ is $latex {\hat{f}(S) = \langle f, \chi_S \rangle}&fg=000000$). The way I like to think of the Fourier transform is simply as a change of basis for $latex {f}&fg=000000$, wherein (hopefully) the representation of $latex {f}&fg=000000$ is simpler, and hence easier to analyse. It is also interesting to note that if $latex {f}&fg=000000$ is defined on $latex {\{-1,1\}^n}&fg=000000$ instead on $latex {\mathbb{Z}_2^n}&fg=000000$, then each character $latex {\chi_S: \{-1,1\}^n \rightarrow \mathbb{R}}&fg=000000$ is the monomial $latex {\chi_S(x) = \prod_{i \in S} x_i}&fg=000000$, thus the Fourier expansion is in fact the representation of $latex {f}&fg=000000$ as a multilinear polynomial over $latex {\mathbb{R}}&fg=000000$.

So sure, we have a relatively good understanding of how polynomials behave, and as the foregoing discussion shows, the Fourier transform is a natural way of looking at a function as a multilinear polynomial. But why specifically this base? What is so unique about the base of parities? Are there other bases which are just as effective? Here is my point of view, which I learned from Or Meir: Let $latex {\mathcal{F}}&fg=000000$ be the linear space of functions $latex {f: \mathbb{Z}_2^n\rightarrow\mathbb{R}}&fg=000000$. For every $latex {w\in\mathbb{Z}_2^n}&fg=000000$, consider the linear operator $latex {\sigma_w}&fg=000000$ that maps a function $latex {f \in \mathcal{F}}&fg=000000$ to the function $latex {f’ \in \mathcal{F}}&fg=000000$ such that $latex {f’(x) = f(x+w)}&fg=000000$. Such operators are called shift operators. It turns out that in many natural problems that appear in theoretical computer science (but also in functional analysis, Hardy spaces, the theory of abelian varieties, and the theory of symbolic dynamics) there is a fundamental, underlying need to analyze the effects that such operators have on Boolean functions. Now, a cool property of the Fourier basis (namely, the shift theorem) is the fact that it simultaneously diagonalizes all of the shift operators. Details follow.

Since we are dealing with a finite discrete domain (the Boolean hypercube), we can view the functions in $latex {\mathcal{F}}&fg=000000$ as vectors in a subspace (i.e, $latex {f\in \mathcal{F}}&fg=000000$ can be viewed as a vector $latex {v_f \in \mathbb{R}^{2^n}}&fg=000000$, where the entries of $latex {v_f}&fg=000000$ are the values of the truth table of $latex {f}&fg=000000$). Then, the shift operators are linear operations on vectors, hence they can be viewed as matrices. As we mentioned before, we wish to simplify the representation of the functions and operators that we study, in order to make them easier to analyse. The best we can hope for is to diagonalize the matrix of the operator we inspect, and this is exactly what the Fourier basis does: In the Fourier basis, all of the shift operators are diagonal matrices.

More generally, the Fourier basis diagonalizes the convolution operator, which also underlies the structure of many natural problems in the analysis of Boolean functions. To see the power of the aforementioned diagonalization, let’s look at an important corollary of it: the convolution theorem. Given functions $latex {f,g \in \mathcal{F}}&fg=000000$, their convolution $latex {f * g}&fg=000000$ is also a function in $latex {\mathcal{F}}&fg=000000$, defined by

$latex \displaystyle [f*g](x) = \sum_{y \in \mathbb{Z}_2^n}f(y)g(x-y). \ \ \ \ \ (3)&fg=000000$

The convolution theorem for $latex {\mathbb{Z}_2^n}&fg=000000$ states that the Fourier transform of the pointwise multiplication of two functions is equal to the convolution of their Fourier transforms; that is,

$latex \displaystyle \widehat{f \cdot g} = \hat{f} * \hat{g}. \ \ \ \ \ (4)&fg=000000$

The convolution theorem, as well as the other aforementioned properties of the Fourier transform, makes it very robust for the analysis of Boolean functions. Let me provide an example from my own work (joint with Omer Tamuz). We want to test whether a function $latex {f \in \mathcal{F}}&fg=000000$ is Boolean or not (i.e, whether its image is contained in a set of cardinality 2, say $latex {\{-1,1\}}&fg=000000$). A simple, though crucial, observation is that a function $latex {f \in \mathcal{F}}&fg=000000$ is Boolean if and only if the convolution of $latex {f}&fg=000000$ with itself (which sometimes referred to as the autocorrelation of $latex {f}&fg=000000$) is equal to the delta function (i.e., the function that gets 1 at 0, and gets 0 elsewhere). To see this, note that $latex {f}&fg=000000$ is Boolean if and only if $latex {f^2 = 1}&fg=000000$, apply the convolution theorem, and use the fact that the Fourier transform of the constant 1 function is the delta function. Hence, using the Fourier expansion we are able to give a characterization of Boolean functions that is efficiently testable. This is a general theme: whenever a function is “correlated with its shifted-self”, it begs for a Fourier based approach.

Last, I would like to give a brief taste of “heavier” tools in the same spirit: We can generalize the discussion on efficient representations even further. Fourier analysis is a special case of the representation theory of finite groups. This theory deals with the more general space of functions $latex {f:G\rightarrow \mathbb{C}}&fg=000000$ where $latex {G}&fg=000000$ is a finite group. It allows us to find a basis that makes the analysis of shift operators easier, even though for general groups the shift operators aren’t always diagonalizable. Another possible generalization can be done by analyzing tuples of shifts (e.g., $latex {f(x),f(x+w_1),f(x+w_2),f(x+w_1+w_2)}&fg=000000$). In many cases, such analysis cannot be done by standard Fourier analysis, and higher-order Fourier analysis is needed (for more details, see Terry Tao’s excellent survey on this topic).

Open Problems: Returning to the original question at the beginning of the post: are there other bases of functions that will work as well as the Fourier basis? Can we perhaps mimic the success of wavelets in classical harmonic analysis, and use such bases in theoretical computer science?

Brain overload and self control

Many thoughts are running through my head as I aggressively strike the ‘holy trinity’ of strokes, ‘Control-alt-delete’. This is the nightmare of every ‘heavy’ software user: hours of work are about to go down the drain. I wish I hadn’t watched the YouTube that wasted precious computation power. I wish I had a faster processor, or at least a few more Gigabytes of working memory.

As engineers, we are constantly concerned with increasing the efficiency in which our products use limited resources. But as we try to save power and time by reducing computational and memory complexity, most of us are unaware of the limited resources of our brain - the CPU that lies within our skulls.

Last week I went road tripping with a friend to San Francisco. Driving on the highway, I could easily engage in conversation, listen to music and eat – all at the same time. Going off the highway made things more complex. I found it impossible to keep the conversation while trying to find my way through the allies of Mission district. The brain has a limited budget of mental effort, and by multi-tasking I risked getting to the ‘control-alt-delete’ state of my mind.

When we buy a new computer, its hardware capabilities are stated on the box or in the manual. Using sophisticated experiments, cognitive psychologists are trying to reverse-engineer the hardware limitations of our brains, and understand what might be the consequences of over-loading it. In terms of working memory, the magical number of objects that the average human being can store is thought to be seven, plus or minus two.  Psychologists ‘load’ the brains of subjects by incentivizing them (with real money) to memorize a varying number of digits; the consequences of this mental burden on our working memory are quite surprising. In a famous 1999 experiment, a group of Stanford researchers asked college undergrads to memorize a few digits, and then walk over to the room across the hall to recall them. On the way, they encountered a food cart, where they could choose between a chocolate cake and a healthier alternative - a fruit salad. Subjects that were asked to memorize seven digits were ~50% more likely to choose the unhealthy (but tasty) cake than subjects who were asked to memorize only two digits. Similar experiments in other domains, demonstrated that when the human CPU is loaded, people tend to ‘lose control’ by making selfish choices, spending money on impulsive purchases and using sexist language.

Cognitive load ahead

CPU power requires energy, and so is the case for our mind, whose preferred fuel is the sugar glucose. Just like after physical efforts (such as moving an apartment), following extensive mental exertions (for example a long exam) we find ourselves desperately looking for sugar in order to refill our mental batteries. This is a dangerous combination for dieters, whose self-control capabilities are anyways degraded because of the mental effort. Psychologists know the process of losing self-control as a result of decreasing brain-CPU power as ‘ego depletion’.

A group of Israeli researchers examined how ego depletion might affect fatal judgments requiring extreme mental effort - decisions of prison parole boards. Turns out that the odds that a prisoner will be successfully paroled dramatically drops from almost 65% at the start of the day (after breakfast) to almost none when the board members’ sugar level plummets, before lunch. Upon returning from their break, with their mental batteries loaded, the odds that the judges will turn around their default ‘NO’ abruptly rise to 65%, and then decline again. Prisoner’s fate is dramatically influenced by the random time for which his hearing was scheduled.

How can we avoid the loss of self-control and our degrading judgment capabilities? Obviously, extending our working memory or adding another CPU core is not an option for our minds. Perhaps making sure that we eat well, sleep enough and take a short break to keep our stress levels low is a start. Understanding the limitation of our brains might help us in forgiving our friends and ourselves, for the occasional bad decisions we all make sometimes.

The Internship Hunt

Around this time of year many students look for summer internships. Some want work experience so they can land a better job after graduation. Others hope to advance their research or improve their academic qualifications. Everyone appreciates the extra cash.

I’m now in my third year as a theory PhD student. Last summer I interned at a financial company and this summer I will intern at a tech firm. Because I had worked in software a number of years before grad school, I was not looking for job experience. My motivation (besides the extra cash) was to get a taste of working on research projects in industry. Also I find that immersing myself in “real-world” problems from time to time adds breadth and perspective to my theory research.

Whatever your motivations for seeking an internship, here are some suggestions that I’ve found useful.

Start early. This is mostly common sense so I won’t belabor the point, but consider this: crunch time at the end of the semester is busy enough without having to prepare for tech interviews, crank out a programming exercise, or schedule on-site visits. What counts as early varies, so ask the places you’re interested in.

Use your network. As pointed out in Lora Oehlberg’s recent blog post, your personal network is the first place to look for job opportunities. My first internship in high school, my first job out of college, and my internship from last summer all came through personal connections. People you know who work at a company you’re interested in can help you through the process and even vouch for you. If you know people who’ve done an internship you’re thinking about, talk to them about what to expect.

Practice. I was nearly eliminated from consideration for my internship last summer because I wasn’t prepared for the first tech interview. A friend of mine in the entertainment software industry told me that whenever he goes on the job market, he expects to flub his first interview from lack of practice. I’m not suggesting you should plan to flub interviews; just know that doing well on a tech interview takes mental readiness.

How do you practice? This is where advice from your connections (see previous point) comes in handy, especially from fellow students who have gone through the process before. I’ve found that working through online programming contests or problems at Project Euler helps get me into game shape.

Be candid and upfront. It’s tempting to be cagey with potential employers about competing offers, availability for the summer, or other constraints. Don’t do this. Last spring I interviewed with two companies and got two offers. I was forthcoming about this during the process, so when I had to turn one company down, I was able to keep the door open for the future. That company offered me a position for this summer, and the recruiter specifically mentioned my candor as a factor.

Do you have ideas for successful internship hunting? Cool internship experiences you want to share? Let us know in the comments.

Welcome Theory Student Bloggers

Several new bloggers will be joining the XRDS student blog over the next few weeks, expanding its scope to theory related stuff and beyond! Welcome, and looking forward to your posts (posts tagged “Theory” will appear on the theory of computing blog aggregator).

The XRDS blog has been up and running for six months now, with posts written by and for CS students on a range of topics (security, HCI, being a post-doc in Paris to name a few…). The motivation behind the blog is similar to the one described here - to help carry the conversation for the student community, a place to share thoughts and get up to date. If you like the idea and would like to support this initiative, please add us to your blogroll.

Tomorrow – internships!

An American Post-Doc in Paris: Settling In

After finishing my dissertation in the fall, I recently moved to Paris to do a post-doc with an HCI research lab. In my first month in France, I’m finally getting the hang of things. If you’re at all interested in studying or researching abroad, here’s a bit of logistical advice to get you off the ground:

As always, networking is the best way to find a position.  Like most post-doc openings, mine was more a matter of meeting my now-boss and agreeing upon a research topic than it was applying to a job opening online.  I did ultimately apply officially online, but I was still able to check in with my contact to see how things were coming along.  And, even if you meet someone who’s not in your field, they may still be able to point you towards colleagues who need research help.

Do not underestimate bureaucracy. Perhaps it’s just a French thing, but I’ve found that there are many, many layers of bureaucracy required to settle into functional, non-tourist living in another country.  While I’ve had a lot of help from the administrative staff at my research lab, it’s still a bit overwhelming sometimes – I started keeping a flow chart to track what documentation I needed to apply for the next layer of documentation.  After getting a scientist/researcher visa at the French consulate in San Francisco (level 1), now that I’m in France I can apply for my carte de séjour (residency permit - level 2).  After I have my carte de séjour, I can apply for national health care (level 3).  And this doesn’t even include just finding a place to live – Paris is like New York, where rental agencies manage the market (and charge an additional fee for their services). They also require a hefty amount of documentation for anything beyond a 3-month “vacation” rental – bank account information, tax forms, 3 months of pay stubs, etc.  I ultimately found a short-term apartment  where I could stay while I build up the requisite paperwork and look for a long-term apartment

Don’t let language stop you.  Most major conferences are in English – which means that most research groups either already speak English, or have a vested professional interest in improving their English.  My research group is very international – France, United States, Germany, Chile, Mexico, China, Brazil – and so we communicate on our linguistic common ground, English.

Do use the opportunity to learn the language around you.  While professionally I work in English, I try to talk in French as best I can with the people around me on an everyday basis.  I was fortunate enough to have learned pretty good French in high school, and am functional enough to order food at a restaurant, explain to a salesperson that I’m looking for a powerstrip by dancing around a word I’ve not learned yet (turns out, le multiprise) and describing its functionality instead, and chit chat with the woman next to me on the métro about what I’m knitting.  I’m still looking for a proper French class, but in the meantime I’m expanding my knowledge of French by eavesdropping on my French coworkers’ lunch conversations and watching dubbed episodes of “Les Simpson” on TV with closed captioning turned on.

Do you have any advice on the nuts and bolts of doing research internationally? Any particular topics you’d like an American-post-doc-in-Paris to address? Comment!