../

2026-10-07 TOC Scribe

$\newcommand{BS}{{0, 1}}$

Randomized Computation

So far, we’ve tried to be as deterministic as possible. We have avoided using even NDTMs as much as possible and in the event that we use them, we use the easier definition of them. Thinking about randomness can be very hard. But many problems in nature are probabilistic in nature and solutions to some problem are probabilistic in nature. Hence, it is important that we talk about them.

Probabilistic Turing Machine

A probabilistic TM is exactly the same as a regular TM except that it has two transition function $\delta_0, \delta_1$. It choose one them uniformly at each transition. This choice is independent of all previous choices.

Another equivalent view is that a TM equipped with an unbiased, read-only, read-once random coin is a PTM. It uses this random coin at each turn to pick one of the transition functions to use.

Read-only comes with a caveat. The TM can obviously write down what it had just read. This comes with a cost of time and space. So, in most practical settings, the TM will not incur this cost. Hence, we can say that the coin is read-only.

Notice that we didn’t discuss the acceptance criteria for this TM. Without it, it look pretty much identical to what we had for NDTM. Turns, out that there are varying degrees of error that you can allow this TM to have. This degree of freedom then gives several complexity classes and associated TMs.

Comparison with other TMs

  • It is pretty clear that a PTM can easily simulate a TM. We just set $\delta_0 = \delta_1 = \delta$ a PTM becomes a DTM
  • The other conversions are not so clear. Without a concrete definition of the acceptance criteria, it is not possible to do any simulation
  • A DTM, when given exponential time, can simulate a PTM by constructing a tree and enumerating all possible paths that could have been taken.

Motivating example - Polynomial Identity Testing

  • Consider the following problem of Polynomial Identity Testing
    • What the hell does that mean? We want to check if two polynomial compute the same function.
    • More specifically, we are dealing with polynomial in some implicit form like an arithmetic circuit
      • An arithmetic circuit is just like a boolean circuit but the gates that could be used are ${+, -, \times}$ and the input wire are over the field on which these operations are defined on.
      • When given two polynomials in this implicit form, how can we determine that they represent the same thing? That is the problem of Polynomial Identity testing.

$\mathsf{ZEROP}$

  • This is the set of all circuits that compute the identically zero polynomial
  • If we had a TM to compute this language then we can construct a new circuit $D = C_1 -C_2$ and check if $D \in \mathsf{ZEROP}$ to check if they are identical.

Why is this hard?

  • You may ask how is this even hard? Can’t you just simplify the expression and see if the coefficients are zero - I’m gonna stop you right there. This problem is for circuit representing polynomials. There is an isomorphism between circuit and polynomials. But, the tricky part is that very small circuit can represent enormous polynomials.

Example 1: Example

  • Consider $\prod_i^n (1 + x_i)$
  • This polynomial has a circuit size of just $2n$ but the number of terms when you expand it out is $2^n$ !!! (Not triple factorial, just exclaiming).
  • I’m showing you this to illustrate how it may not be obvious what polynomial a circuit is computing at first glance. Hence it is not as simple as just look at the coefficients bro.

Lemma 2: Schwartz-Zippel

Suppose you have some non-zero polynomial $p(a_1, \ldots, a_n)$ of total degree $d$. If you were to choose pick these $a$-s randomly, with replacement, from a finite set $S$, the probability that you pick a non-root is given by $$\Pr[p(a_1, \ldots, a_n) \ne 0]\ge 1 - \frac{d}{|S|}$$

Where we define total degree of the polynomial as the largest total degree of its monomials which is defined as the $x_1^{e_1}x_2^{e_2}\ldots x_n^{e_n} = \sum_i e_i$. This is just a fancy way of saying how $xy$ is a quadratic even if the powers of $x$ and $y$ individually aren’t 2.

This can be then extended to finite fields where the probability is given by $1 - \frac{d}{q}$ where $d$ is the degree and $q$ is the field size.

This should be intuitive given what we have studied about polynomials in high school. Suppose you have a quadratic, we know that it only have 2 solutions. The probability that you randomly pick these two solution out of all the integers is miniscule.

Randomized Algorithm for Polynomial Identity Testing

  • INPUT: A circuit $C(a_1, \ldots, a_n)$
  • OUTPUT: If $C$ computes a zero polynomial
  • ALGORITHM:
    1. Calculate the degree of the polynomial as follows: If a circuit has $m$ gates, then the maximum degree can only be $2^m$
    2. Pick an integer from $[10\cdot2^d]$
    3. Evaluate that on $C$
    4. If it is zero output 1 else output 0

Using Schwartz-Zippel you can prove that this algorithm succeeds with 90% probability.

TODO(dbk): There is a problem with this algorithm, read the Arora-Barak

Why won’t determinism work?

  • You asked in class why can’t we just have a big fixed list of polynomially many numbers that we test with? If each number has equal probability of being a non-root, then what difference does it make if they are random or fixed? We just need one non-zero result from the circuit to prove non-membership.
  • The reason that this won’t work is that this algorithm always fails on some inputs. Whereas the above algorithm always works with 90% probability, regardless of input.

TODO(dbk): the rest of the notes