### Projects aplenty

Thursday, May 26th, 2011*When ambitious students ask me for projects to work on, I usually kick myself for not having a list of favorite open problems that I can simply point them to. Sure, half a year ago I listed some of my favorite open problems in quantum complexity theory—but what can I give the majority of students who are more classically-inclined? The following haphazard list is my attempt at an answer. Some of the “problems” are open-ended or ill-defined, some are actually implementation projects, some are no doubt trivial or solved, others are no doubt hopelessly difficult, and a couple are shamelessly filched from MathOverflow or CS Theory StackExchange. Almost all are missing motivation and context. Without further apologies…*

1. Create a zoo of cryptographic primitives (one-way functions, one-way permutations, pseudorandom generators, etc.) and the relationships between them, paralleling the Complexity Zoo.

2. Build a public library of 3SAT instances, with as few variables and clauses as possible, that would have noteworthy consequences if solved. (For example, instances encoding the RSA factoring challenges.) Investigate the performance of the best current SAT-solvers on this library.

3. Find an explicit n (the smaller the better) for which you can prove that the value of BB(n) (the n^{th} Busy Beaver number) is independent of ZF set theory. More generally, find a way to enumerate the proofs of ZF set theory, which requires a shorter or simpler program than the “obvious” proof-enumerating program.

4. Call a cellular automaton “physically universal” if any polynomial-time transformation on any subset of n bits can be implemented by choosing a suitable initial configuration of the surrounding poly(n) bits. (Note that my definition is potentially more inclusive than Janzing’s.) Find interesting examples of cellular automata that you can prove are or are not physically universal.

5. Prove explicit lower bounds on the number of arithmetic operations needed to compute the permanents and determinants of 3×3 and 4×4 matrices. In the 4×4 case, can you obtain a separation between the permanent and the determinant?

6. Are there proofs with (say) n^{2} symbols, in a proof system of your choice, for which (a) there exist proofs of the same statements with n symbols, but (b) finding the shorter proofs is computationally intractable?

7. Call a set of k-by-k unitary matrices U_{1},…,U_{k} “linear-optics universal,” if for any n, any n-by-n unitary matrix U, and any ε>0, it’s possible to approximate U to within error ε by applying some finite set of U_{i}‘s to various ordered lists of k of the n indices. Give necessary and sufficient conditions for a set of unitaries to be linear-optics universal.

8. How hard is it to sample a (nearly) uniformly-random n-by-n invertible matrix over GF(2)? Clearly it can be done in matrix multiplication time, but can we give evidence that it can’t be done in less?

9. Is “collinearity logic” in NP? In other words: given a collection of n points in the Euclidean plane, together with a list of triples of points that should be collinear and a list of triples that should *not* be collinear, is the problem of deciding whether the requirements are consistent in NP? (It follows from known results about the existential theory of reals that this problem is in PSPACE; I thank Peter Shor for that observation.)

10. Given a weighted bipartite graph, is there a polynomial-time algorithm to decide whether or not there are two perfect matchings with the same weight?

11. Give nontrivial examples of problems that are complete for PromiseBPP. Could approximating the permanent of a nonnegative matrix be an example of such a problem? Alternatively, can that problem be solved in randomized NC?

12. Given an explicit description of a Boolean circuit C of size (say) n^{3}, and promised there exists a circuit of size (say) n^{2} that computes almost the same function as C, how hard is it to find the smaller approximating circuit? Can we give cryptographic evidence that this problem is hard? What additional assumptions about C make the problem easy (ideally, easy for reasons that require looking at the structure of C, rather than just treating it as a black box)?

13. What is the randomized one-way communication complexity of the Group Membership Problem (in which, given a finite group G known to both players, Alice knows a subgroup H≤G, Bob knows an element x of G, and Alice’s goal is to send Bob a short message that enables him to decide whether x is in H)?

14. Study the lower bounds on Manifestly-Orthogonal Tree Size in my paper Multilinear Formulas and Skepticism of Quantum Computing. In particular, do these lower bounds evade the Razborov-Rudich natural proofs barrier?

15. Prove an oracle separation between BPP and P^{BPNC}. (Likewise, prove an oracle separation between BQP and BPP^{BQNC}.)

16. Are there plausible pseudorandom functions computable by ACC^{0} circuits?

17. Prove a strong anti-concentration theorem for the permanent of a matrix of iid Gaussian entries.

18. Given the truth table of a Boolean function f:{0,1}^{n}*{0,1}^{m}→{0,1}, are there efficient algorithms to compute (or approximate) the randomized and quantum one-way communication complexities of f?

19. Classify the possible sets of classical reversible gates acting on bits, by the sets of transformations that they generate. (I.e., what is the analogue of Post’s lattice in this setting?) As a warmup, classify the possible sets of classical reversible gates that act linearly over GF(2) (like the NOT and CNOT gates).

20. Do there exist probability distributions D_{1},D_{2} over n-bit strings such that (D_{1}^{2}+D_{2}^{2})/2 (an equal mixture of two independent samples from D_{1} and two independent samples from D_{2}) is efficiently samplable, even though D_{1} and D_{2} themselves are *not* efficiently samplable? (This is closely-related to a beautiful question posed by Daniel Roy, of whether the de Finetti Theorem has a “polynomial-time analogue.”)

21. Is BB(n) (the n^{th} Busy Beaver number) odd infinitely often? Is it decidable whether BB(n) is odd?

22. Show there are tasks that Turing machines with (d+1)-dimensional tapes can solve polynomially faster than Turing machines with d-dimensional tapes.

23. Extend my results from A Counterexample to the Generalized Linial-Nisan Conjecture to show that Σ_{2}P^{A} ≠ Π_{2}P^{A} with probability 1, relative to a random oracle A.

24. Given a function f:[N]→[N], which is promised to be either one-to-one or two-to-one, what’s the optimal MA-protocol for proving f is one-to-one (i.e., what’s the optimal tradeoff between the size of the witness and the number of queries needed to verify it)?