[Lowerbounds, Upperbounds]

One of my favorite keyboard shortcuts in PowerPoint is Shift-F3. It rotates the capitalization of the current word among lowercased, Capitalized and UPPERCASED. Note that you do not have to select the word, and the cursor does not have to be at the beginning of the word either(*).

But the title of this post clearly said Emacs, didn’t it? Well, since I missed this feature in Emacs, I just implemented it in a pinch and bound it to Shift-F3. The code is in this page in EmacsWiki. I have only tested it on GNU Emacs, and so I can only hope that it works in XEmacs.

(*) Actually, you rarely have to select a word in PowerPoint in order to format it. Commands like Bold Ctrl-B and Italic Ctrl-I will act on the current word when there is no selection. Also, similar behavior is in fact present in all Office applications. I just picked PowerPoint.

Date: Tuesday November 6th, 2007
Place: NSH 3305
Time: 3PM - 4PM

Title: Assessment-centered instruction: Using assessment to support educational effectiveness

Dr. Anne Fay, Director of Assessments
Eberly Center for Teaching Excellence & The Office of Technology for Education (OTE)

Abstract:

Research in the learning sciences has changed our view of education from a teacher-centered to a learner-centered perspective. Designing our instructional practices with the learner at the center changes significantly how we teach, what we teach, and where and when learning takes place. Fundamental to this learner-centered view is the role of assessment, whereby assessment and instruction are tightly interwoven and interdependent activities, and assessment is no longer an afterthought in the instructional cycle. In fact, in a learner-centered approach, that is, thinking in terms of how students learn and what we want them to know and be able to do, assessment should guide our instructional practices, and not the other way around. In this talk I will explore how our new understanding of learning can be used to change and expand our instructional practices and change how we think about and engage in assessment activities. I will present examples of instructional innovations and assessment practices to illustrate how integrating assessment of student learning into our instructional practices can make teaching and learning more effective and efficient.

Friday November 9th, 2007
WEH 7220
3:30pm

Algebrization: A New Barrier in Complexity Theory

Scott Aaronson (MIT)

Any proof of P!=NP will have to overcome two barriers: relativization and natural proofs. Yet over the last decade, we have seen circuit lower bounds (for example, that PP does not have linear-size circuits) that overcome both barriers simultaneously. So the question arises of whether there is a third barrier to progress on the central questions in complexity theory.

In this talk we present such a barrier, which we call “algebraic relativization” or “algebrization.” The idea is that, when we relativize some complexity class inclusion, we should give the simulating machine access not only to an oracle A, but also to the low-degree extension of A over a finite field or ring.

We systematically go through basic results and open problems in complexity theory to delineate the power of the new algebrization barrier. We first show that all known non-relativizing results — both inclusions such as IP=PSPACE and MIP=NEXP, and separations such as MA-EXP not in P/poly — do indeed algebrize. We next show that most open problems — including P versus NP, P versus BPP, and NEXP versus P/poly — will require non-algebrizing techniques, of which we currently have not a single example. In some cases algebrization seems to explain exactly why progress stopped where it did: for example, why we have superlinear circuit lower bounds for PromiseMA but not for NP.

We also exhibit a surprising connection between algebrization and communication complexity. Using this connection, we give an MA-protocol for the Inner Product function with O(sqrt(n) log(n)) communication (essentially matching a lower bound of Klauck), and describe a pure communication complexity conjecture whose truth would imply P!=NP.

Joint work with Avi Wigderson.

2007-11-06, 3:30pm in Wean 5409
Projection Pursuit, Gaussian Scale Mixtures, and the EM Algorithm
Sanjoy Dasgupta
University of California - San Diego

The EM algorithm for fitting Gaussian mixture models is one of the most widely-used clustering methods. Yet, surprisingly little is known about its behavior. Under what conditions does it converge to a good local optimum? What are good ways to initialize it, and to merge/remove intermediate clusters? Such questions are difficult to answer with the mathematical tools that have traditionally been applied to EM.

I will describe an alternative way of analyzing EM: by a probabilistic analysis. This reveals, first of all, that many common methods of initializing EM produce highly suboptimal results even in ideal clustering scenarios. On the other hand, I’ll show that a particular variant of EM will provably recover a near-optimal clustering, provided that the clusters are adequately separated and that their distributions are of a certain fairly general form.

The type of cluster distributions allowed is motivated by a new result in projection pursuit, along the lines of the (somewhat mistaken) folklore that “almost all projections of high-dimensional data look Gaussian”.

Specifically, I’ll show that for any D-dimensional distribution with finite second moments, there is a precise sense in which almost all of its linear projections into d < D dimensions look like a scale-mixture of spherical Gaussians (concentric spherical Gaussians with the same center).

The extent of this effect depends upon the ratio of d to D, and upon the “eccentricity” of the high-dimensional distribution.

Now that we know how to precompile the preamble to cut down the running time of latex, here is a tool that furthers the goal of saving time in the document production process—latexmk.

As its name suggests, latexmk is a “make” utility for LaTeX files. In particular, it understands when a particular document requires varying number of runs to resolve all references, with a bibtex and/or makeindex throw in at the right moment in-between the runs. Recent versions even support multiple bibliographies and the like. In short, assuming no source errors, if you execute latexmk foo.tex, you will get a fully compiled foo.dvi without any manual intervention. (PDF users: add the -pdf option. nomencl(ature) and glossaries package users: see below.)

Now latexmk would be a great piece of software to recommend just for the features I have mentioned above. Indeed, over the years I have seen various Makefile solutions using the make utility, some of which are fairly sophisticated. There are also direct competitors like texify and the like. (See this article in EmacsWiki.) While I find that latexmk fits my workflow in terms of ease of use and customizability, you may also want to check out these other intelligent options too. They all beat the “latex, latex, bibtex, latex, latex” batch script.

But latexmk is better than that—it has support for continuous/automatic compilation: if you run latexmk -pvc main.tex, then whenever it detects that one of the dependent source files of main.tex has been changed—be that a TeX, bib, an included graphics, or any file you declare to be a source, latexmk will automatically recompile it for you. That means you don’t need to start the compilation manually after changes and an oven-fresh dvi/pdf will be delivered to your previewer as soon as it is ready.

Finally, here are some notes on latexmk:

• You really want the latest version, even though the version number may say “beta”. The script is very mature. Also note that MiKTeX ships with latexmk.exe, which is a wrapper to call Perl on TEXROOT\scripts\latexmk\perl\latexmk.pl

, which is the script you want to replace.

• You can set up your .latexmkrc to override defaults or even define new dependencies. Below I have attached some interesting bits of my .latexmkrc just for an example. For instance, you can avoid launching a previewer even though you are using the -pvc option, and you can support the nomencl package and the like by declaring a custom dependency. And since this is a Perl script, you can use any Perl constructs. You can read the documentation for more possibilities.
  

  $latex = 'latex -src-specials -parse-first-line -c-style-errors';
$pdflatex = 'pdf' . $latex;
$dvi_previewer = 'exit'; # don't start a previewer for me
@default_files = ('main');
$clean_ext = # space separated string
join(' ', qw( fmt acn acr alg gls glo glg ist nls nlo nlg brf out pdfsync rel));
push @cus_dep_list, "nlo nls 0 nlo2nls"; # nomenclature
sub nlo2nls { system("makeindex $_[0].nlo -s nomencl.ist -o $_[0].nls -t $_[0].nlg”); }
push @cus_dep_list, “acn acr 0 acn2acr”; # glossaries and acronym hack
sub acn2acr { system(”makeindex $_[0].acn -s main.ist -o $_[0].acr -t $_[0].alg”); }
push @cus_dep_list, “glo gls 0 glo2gls”; #MiKTeX 2.6 has a broken makeglossaries.exe
sub glo2gls { system(”makeindex $_[0].glo -s main.ist -o $_[0].gls -t $_[0].glg”); }

• The -silent option suppresses the output of latex and show you only the errors in a succinct format. Here is an example transcript when I run latexmk -silent foo.tex with two planted errors.
  

  No specific requests made, so default to dvi by latex
Latexmk: Run number 1 of rule 'latex'
Latexmk: Running 'latex -src-specials -parse-first-line -c-style-errors -interaction=batchmode -c-style-errors "foo.tex"'
This is pdfTeX, Version 3.141592-1.40.4 (MiKTeX 2.6)
entering extended mode
foo.tex:3: Undefined control sequence
foo.tex:4: Undefined control sequence
Latexmk: Use the -f option to force complete processing.

Have fun with latexmk!

P.S. I should note one fine point: if you have the habit of saving your file after every single sentence, then perhaps continuous compilation can be a bit counterproductive. Emacs users can consider tuning their auto-save-timeout and auto-save-interval instead.