### UPP

**B**ounded **P**robabilistic **P**olynomial time (BPP)
is the class of all languages L for which some
randomized Turing machine M has the following property:
for each input x, if x is in L, then the probability
that M(x) accepts is >= 2/3
and if x is not in L, then the probability that
M(x) accepts is <= 1/3.
The numbers 2/3 and 1/3 are not special.
What *is* special is that these 2 numbers
are a positive distance from one another.
I think that this is where the *Bounded*
part of BPP comes from: the probability of error
is bounded below by some positive real.

So what if we erased the bounded requirement of BPP?
Let 0 < p < 1 be a real and define **U**nbounded
**P**robabilistic **P**olynomial time of p (UPP(p)) to be the
class of languages for which there exists a randomized
Turing machine M with the following property:
for each input x, if x is in L, then the probability
that M(x) accepts is > p
and if x is not in L, then the probability that
M(x) accepts is < p.

The following essay (pdf)
explores these classes of languages.
The major result is that they are all the same independent of p!

### Dual Vector Space

Let V be a vector space over a field F.
The dual V* of V is the vector space of F-linear
homomorphisms from V to F.
Usually V* is isomorphic to V, each element
representing an inner product with some fixed vector in V.
But if V has infinite dimension, this may not be the case!
The following essay
(pdf) presents
a good example of this phenomenon.
### CDF Bounds

Let X be a random variable and suppose that we wish
to bound P(X<=a) by P(Y<=a) for all a where Y is a random variable
with a simpler CDF.
We may be tempted to choose parameters for Y so that
E(X)=E(Y) to get a good bound, but as the following
essay (pdf) shows,
this is not possible.
### Dimension of R^N

Let V be the infinite dimensional R-vector space of all
maps from the natural numbers, N, to R.
The dimension of V is not the cardinality of N.
To give some idea of why this is, notice
that the countable set of tuples B={e1,e2,...}
where ei has a 1 in the ith position and 0's elsewhere
does not span R^N, as it can only generate
tuples with finitely many nonzero components.
The following essay
(pdf)
finds the actual dimension.
### Infinite Matrices

What are the basic properties of infinite matrices?
What does the eigenspace look like.
This
(pdf) explores a few such questions,
though it asks more questions than it answers.
### What is Security?

This short essay explores
just what is meant by "system A is secure".
### Isoperimetric Problem

Suppose we wish to find a subset S of the Boolean cube 2^n
of size m so as to minimize the size of the boundary
of S, i.e. the number of Hamming distance 1 neighbors of S.
This can be done by putting S into a Hamming ball.
The proof is quite hard and I could not find a complete
version of it anywhere, so I wrote
my own (pdf).
It should also be noted that to minimize the number of
boundary edges, S should be put into a cube.
### Nonmeasurable Sets

Let X be a sample space.
A probability measure can be defined on P(X) provided
X is countable, but if X is a continuum,
then we may run into contradictions unless we
restrict the probability measure.
This
essay (pdf)
gives an example of a nonmeasurable set.
### Self Reducibility of NPC Languages

All languages in NPC are self reducible, as this
short essay
(pdf) shows.
### Extension of Minimax to Infinite Matrices

Consider a zero-sum game between players row and column
with m x n payoff matrix A, so that if row chooses i and
column chooses j, then column pays A(i,j) to row.
Von Neumann's theorem states that for m,n finite,
the maximum, over all mixed strategies p for player row,
of the minimum, over all mixed strategies q for player column,
of the expected payoff is the same as
the minimum, over all mixed strategies q for player column,
of the maximum, over all mixed strategies p for player row,
of the expected payoff.
But what happens when m,n may be infinite?
If both are infinite, then the max min may not equal the min max,
but if at least 1 is infinite and A is bounded, then
the max min does equal the min max,
as the following
essay (pdf) proves.

### Probability Counterexample

If you were worried about your house being destroyed,
would you rather hear news that
there was a tornado,
hear news that there was a flood,
or hear news that there was a tornado or a flood?
One might think that surely one of the first
2 options is better than the third one.
Wouldn't it be better to pick the natural disaster,
especially given that you might know that
your house is resistant to flooding
(because you live on a hill)
or resistant to tornados
(because you live in an underground bunker)?
Oddly, the probabilities might work out so that
the best news to hear is
"there was a tornado or a flood",
as this
essay
(pdf) shows.
### k-Universal Family

A set of n random variables is *k-universal* iff
each subset of k of them has the
same distribution as k independent and uniform (over some domain)
random variables.
Constructing such families over small probability spaces
has important applications, especially in the derandomization
of algorithms.
The following
essay
(pdf)
gives one such construction.
### Natural Proofs

All lower bound proofs take the form
"function family f has property C and no family with
property C lies in the complexity class Lambda".
Also most have the property that whether f has property
C is easily checkable given the truth table of f
and that a random function has nonnegligible probability
of having property C.
Such "natural" proofs cannot provide nontrivial lower bounds
unless there are no strong pseudo-random generators.
The following
essay (pdf)
gives all the necessary definitions, a major result with proof,
and much discussion of this idea.
The original paper by Razborov and Rudich leaves certain
ideas ambiguous and the proof is missing a major step.
Part of the goal of this essay is to cover the holes.
As a bonus, the essay also includes a definition and proof of
useful properties of a nice new notation for
"ultimately" and "infinitely often" quantification over
the natural numbers.

### Hard Input Distribution

There is a single input distribution D on which
no algorithm solving an NP-complete problem runs
in polytime, unless P=NP, as this short
essay
(pdf) shows.
But D is almost certainly not efficiently sampleable.
This shows that average case hardness needs to be
defined in terms of efficiently sampleable
distributions only, since arbitrary distributions
can easily diagonalize against a class of algorithms.
### CSP Duality

We show in this
essay
(pdf)
a reduction from (a,b)-Constraint
Satisfaction Problem (CSP) of size (n,m)
to (b,a)-CSP of size (m, O(m^a)) and taking time O(m^a).
### Complexity of FSAs

In this essay
(pdf)
we show a few simple facts about finite state automata.
(1) For a given NFA N, a minimal equivalent DFA D may have
exponentially many more states.
(2) A shortest string rejected by an NFA may be of length
exponential in the size of the NFA.
Of course a shortest string accepted must be of linear size.
### Finding Interesting Palindromes

We show that it is possible to decide whether a given
dictionary can generate a palindrome in this
essay
(pdf).
It is not clear whether this can be done efficiently.
As a bonus, we show how to efficiently decide whether
a given sentence is generable from a given dictionary.
### Solving the 15-Puzzle

The 15-puzzle is played on a 4x4 matrix
containing labeled tiles and a single blank.
A move is to interchange the blank with an adjacent tile and
the goal is to order the tiles.
In this
essay
(pdf)
we give necessary and sufficient conditions for solvability
and show how to compute this in linear time.
We also give an algorithm to solve the game using a number
of moves that achieves the average case minimum number of moves
to within a constant factor.
### Jacob's Ladder

Jacob's ladder is a toy constructed from n blocks linked
so that block i is always adjacent to block i+1.
By holding it up by block 1, letting the rest hang down,
and rotating block 1 by pi, you can flip all of the blocks
in a cascading motion.
But you can also create certain graphs with a Jacob's ladder
toy.
This essay
(pdf)
classifies exactly which graphs can be so constructed.
### Nim

The classic game of somewhat unknown origins is fully
analyzed here
(pdf) in terms
of computational complexity and game length.
### Carry Lookahead Adder

The ripple carry addition method requires
Theta(n) depth and size for bounded fanin circuits.
By contrast, carry lookahead addition requires
Theta(lg n) depth and Theta(n^2) size,
as this
essay
(pdf) shows.
### Robots Take Over the World

This essay
(pdf)
shows one of the ridiculous things that can happen if P=NP,
namely that we can construct efficient mistake-bounded learners.
Also proved in the essay are that NP witnesses can
be efficiently sampled uniformly at random given an NP oracle
and that BPP is in Sigma_2.
### Relativization Fallacy

Beginning students of complexity theory often think that
for complexity classes A,B,C,
A <= B implies A^C <= B^C.
When they are told that this is not valid, they seem not to
believe it at first; and who can blame them?
It seems plausible, and
usually mathematical notation is context insensitive.
Further compounding the problem is the lack of handy counterexamples.
This essay
(pdf)
gives a compelling counterexample.
### Small Space = No Space

A very small amount of space is computationally useless
because one cannot even compute how much space one has
to work with.
In this essay
(pdf) we show
that SPACE(lg lg lg n) = SPACE(0) = the regular languages.
### 2-TQBF is in P

In 1979 Plass, Aspval, Tarjan showed that 2-TQBF is in linear time,
but it's pretty hard to find online, and anyway I showed it's in P
independently here
(pdf).