You are currently browsing the category archive for the 'teaching' category.
This week I have been at the IPAM workshop on expander graphs, scheduled so that we could spend Valentine’s day attending lectures, thus symbolically demonstrating our love for math.
My talk was on the problem of checking whether a given hypergraph is an expander, focusing on the expansion property that is known as “quasirandomness.”
Because of the workshop, my Complexity class took a one-week break.
Last week, we talked about one of my favorite “elementary” results in complexity theory: approximate counting with an NP oracle.
Suppose that someone comes up with a polynomial time algorithm for SAT and proves that P=NP; then we know that a number of awesome consequences would follow (and some frightening ones, such as the impossibility of cryptography). We would still, however, not be able to solve combinatorial counting problems such as: given a graph, how many proper 3-colorings does it have, if any?
If the number of colorings is 
Interestingly enough, however, we can approximately count solutions to any NP problem in probabilistic polynomial time, given an oracle for SAT. The idea is cleverly simple. Read the rest of this entry »
After a hiatus of almost four year, the graduate computational complexity course returns to Berkeley.
To get started, I proved Cook’s non-deterministic hierarchy theorem, a 1970s result with a beautifully clever proof, which I first learned from Sanjeev Arora. (And that is not very well known.)
Though the full result is more general, say we want to prove that there is a language in NP that cannot be solved by non-deterministic Turing machines in time 
(If one does not want to talk about non-deterministic Turing machines, the same proof will apply to other quantitative restrictions on NP, such as bounding the length of the witness and the running time of the verification.)
In the deterministic case, where we want to find a language in P not solvable in time 
It’s easy to see that 
We could try the same with NP, and define 
Here is Cook’s argument. Define the function 
where
is a non-deterministic Turing machine and
is a sequence of
- There is a
, and
of running time
;
of running time
.
Now let’s see that 
- If there is, we can compute
and deterministically simulate all computations of
up to running time
. This takes time
which is polynomial in
- Otherwise, we non-deterministically simulate
for up to
steps. (And reject after time-out.)
In either case, we are correctly deciding the language.
Finally, suppose that 
Choose 
Now we can see that 
Back in August, Boaz Barak and Moses Charikar organized a two-day course on additive combinatorics for computer scientists in Princeton. Boaz and Avi Wigderson spoke on sum-product theorems and their applications, and I spoke on techniques in the proofs of Szemeredi’s theorem and their applications. As an Australian model might say, that’s interesting!
Videos of the talks are now online. The quality of the audio and video is quite good, you’ll have to decide for yourself on the quality of the lectures. The schedule of the event was grueling, and in my last two lectures (on Gowers uniformity and applications) I am not very lucid. In earlier lectures, however, I am merely sleep deprived — I can be seen falling asleep in front of the board a few times. Boaz’s and Avi’s lectures, however, are flawless.
In CS70, the Berkeley freshman/sophomore class on discrete mathematics and probability for computer scientists, we conclude the section on probability with a class on how to lie with statistics. The idea is not to teach the students how to lie, but rather how not to be lied to. The lecture focuses on the correlation versus causation fallacy and on Simpson’s paradox.
My favorite way of explaining the correlation versus causation fallacy is to note that there is a high correlation between being sick and having visited a health care professional in the recent past. Hence we should prevent people from seeing doctors in order to make people healthier. Some HMOs in the US are already following this approach.
Today, a post in a New York Times science blog tells the story of a gross misuse of statistics in a Dutch trial that has now become a high-profile case. In the Dutch case two other, and common, fallacies have come up. One is, roughly speaking, neglecting to take a union bound. This is the fallacy of saying ‘I just saw the license plate California 3TDA614, what are the chances of that!’ The other is the computation of probabilities by making unwarranted independence assumptions.
Feynman has written eloquently about both, but I don’t have the references at hand. In particular, when he wrote on his Space Shuttle investigation committee work, he remarked that official documents had given exceedingly low probabilities of a major accident (of the order of one millionth per flight or less), even though past events have shown this probability to be more of the order of 1%. The low number was obtained by summing the probabilities of various scenarios, and the probability of each scenario was obtained by multiplying estimates for the probabilities that the various things that had to go wrong for that scenario to occur would indeed go wrong.
Christos Papadimitriou has the most delightful story on this fallacy. He mentioned in a lecture the Faloutsos-Faloutsos-Faloutsos paper on power law distributions in the Internet graph. One student remarked, wow, what are the chances of all the authors of a paper being called Faloutsos!
My new hero is the student in a class of mine who sent me the following email:
There is always a student who shows up 10 minutes late to each of the (…) lectures, carrying a box of takeout food. He proceeds to noisily eat it while you lecture. This is highly distracting [as well as disturbing; this guy doesn't know how to use chopsticks], especially for those of us who chose to follow the rules. Please take some action as to inform students that eating in class is disrespectful not only to you, but distracting to other students who are trying to take notes. Thanks.
See, eating noisily during class is annoying enough. But not knowing how to use chopsticks? That’s disturbing!
Andy is teaching an undergraduate algorithms class that combines three regular courses: the discrete math and probability course, the algorithms course, and the computability courses. (CS70, CS170 and CS172 in Berkeley-speak.) To make things more interesting, he teaches the course in English. When a foreign visitor is here, Andy always invites him or her to talk about something, anything, in the class for one 45-minutes period. (Classes are 45-minutes periods followed by 5 minutes of break.) Yesterday was my turn.
As usual, things are done in style. I meet Su Chang in her office, and she walks me downstairs, where Andy’s driver is ready to drive us to the building where the lecture is. There, Su Chang walks me up to the classroom. We get there just while a military march is playing to mark the end of a period. For people who are used to hang out with celebrities, this would be no big deal, but being with a person who has an entourage is really amazing to me. Andy is there and he has just finished teaching (the class is two periods).
When another march plays in the loudspeaker, Andy introduces me to the 100-plus students “This is professor Luca Trevisan, from the University of California at Berkeley.”
“Ooh” the whole class goes, when Andy says “Berkeley.” This is quite unexpected: people in America hardly know that there is a university in Berkeley. But then, I realize, these are third year computer science students in the top engineering school in China. Applying to graduate school in the US must be very much on their mind, so it’s no wonder that they have researched American schools and they have come across Berkeley. In any case, it is surprising that students who have Andy as a professor can be impressed by anything.
I have decided to give a lecture on zero knowledge, motivating it with a password protocol problem, and I talk about quadratic residuosity instead of graph isomorphism. The students appear to genuinely understand and enjoy the class, and the march rings the moment I finish the proof that there is a simulator.
Andy invites me for lunch, “We are going to Pizza Hut.” “Oh no!” I say, before I can catch myself. Andy is unfazed by my rudeness and asks me what I would like. “Something Chinese?” I suggest assuming we would go to one of the Chinese fast food places around campus. Instead, we go to the Fancy Place of Tuesday night, where Andy orders a veritable feast.
Hoeteck is meeting a high school friend from Singapore who is in Beijing for business, and I spend the afternoon visiting the Beijing University campus. People say that Tsinghua is the MIT of China, and Beijing University is the Harvard. Famous for its Humanities department, Beijing University has a beautiful campus with a lake in the center, elegant buildings, and better-dressed students.
The evening turns more adventurous than usual, and I end up doing many new things, such as dining at a Chinese fast food place, taking the subway, seeing a working-class Beijing apartment, and joining a gathering made mostly of middle-aged Western expats parading around their young Chinese dates (I pay $5 for a Heineken; dinner for two was $4). I am not judging, because as president Bush’s favorite philospher said, “Judge not etc. etc.” and I, for one, don’t like to be judged. But next time people tell me about post-colonialism and white privilege (we use such words a lot in San Francisco), I promise I won’t roll my eyes. Berkeley’s star power is put in its more proper place. “What do you do in America?” “I am a professor at Berkeley” “Bay-kay-lee?” “That’s right.” “Is it an egineering school?” (them fighting words!) “No” “And what are you doing here” “I am lecturing at Chin-hoo-uh” “Qinghua? WOW!”.
Recent Comments