Personal Statement

My name is Joshua Cook, I am a PhD student studying complexity theory at the university of Texas at Austin under Dana Moshkovitz. If you wanted to see what I look like, you came to the right place (as of this writing)! Though if you just wanted my contact information, that's fine too.

If you are actually interested in any of my work, I'm glad you're here. I make children's books, and research in complexity theory. This is my "professional" website, so I'll mostly use it to keep contact information and list my publications, or any other miscellaneous research, or academic things. My more adult focused, non-research stuff will stay at Quackack.com. But my kid friendly content will be at StemForestBooks.com.

Contact Info

• Email - Username: jac22855, Domain: utexas.edu
• Office - GDC 4.438A

Publications

• Time and Space Efficient Deterministic Decoders.

  We show that there exists codes that can be deterministically decoded in subpolynomial space and almost linear time. This was known to be true for locally decodable codes using randomized decoders, but it wasn't clear if this should be doable deterministically. In fact, Gronemeier showed non-adaptive decoders can't be time and space efficient, and we suspected these results could be extended to adaptive decoders, but they cannot.

  We actually show that all of the standard locally correctable codes have time and space efficient decoders. This corrector works by itertively correcting the input until it is successfully decoded. This approach gives a non-uniform, black box decoder for any locally correctable code, but we also give a time and space efficient uniform decoder for Reed-Muller codes using a new curve sampler.

• Explicit Time and Space Efficient Encoders Exist Only With Random Access, in CCC 2024.

  We show an explicit family of codes that can be encoded by a deterministic, uniform encoder in subpolynomial space and almost linear time. Bazzi and Mitter conjectured that any good code encoded by a time T space S algorithm required that S T ≥ n². Interestingly, an earlier, non-explicit code, the repeat-accumulate code, with random puncturing also runs in subpolynomial space and almost linear time. Before this work it seemingly hadn't been noted that the repeat-accumulate codes disprove the Bazzi and Mitter conjecture. At least Ryan Williams knew these repeat accumulate codes were time and space efficient, although he seemed unaware of Bazzi and Mitter's conjecture.

  One of our main motivations for studying this problem was to encode the output of low space algorithms in error correcting codes. The standard, black box way to do this reduces to a model we call sequential like access. We show that encoders with sequential like access to their input cannot be both time and space efficient. Specifically, for any good code, an encoder running in time T and space S with sequential like access to it's input requires T S² ≥ n². Further we show this is tight. This shows that even in this more restricted setting, Bazzi and Mitter's conjecture is not true, but that there is a non-trivial time and space lower bound.

  Our sequential model to access the input is essentially a multiheaded Turing machine where the heads can jump to the location of other heads. If one thinks of these heads as storing the state of an algorithm, moving forward as simulating the algorithm, and jumps as copying the state of the algorithm, we get our reduction from accessing the output of small space algorithms to the sequential model. This is a much more powerful model of computation than the streaming model.

• Efficient Interactive Proofs for Non-Deterministic Bounded Space, in RANDOM 2023 (RANDOM 2023). Presentation, Short (RANDOM 2023).

  We give interactive protocols for nondeterministic, space S time T algorithms where the verifier is only a factor log(S) slower than those for deterministic algorithms. We also apply this result to alternating algorithms giving interactive protocols for log(T) alternations that have the same verifier time as 1. This uses an idea from Goldreich and Rothblum to use Razborov-Smolenski in interactive proofs, with various improvements.

  Further, our protocols have somewhat efficient provers. This gives us doubly efficient protocols for the same families of circuits as GKR since an alternating algorithm is a circuit. But for unbounded fan-in circuits, our protocols have faster verifiers than GKR, although slower provers. We note our doubly efficient protocols don't apply to as general of languages as RRR.

• More Verifier Efficient Interactive Protocols For Bounded Space, in Foundations of Software Technology and Theoretical Computer Science 2022 (FSTTCS 2022). Presentation, Short (For FSTTCS).

  We refine interactive protocols for space bounded computation to get a more efficient verifier. The protocol is very similar to one by Thaler, but with a better arithmetization and with special cases for nondeterministic and randomized algorithms. The protocol is based on an efficient sum check protocol for matrix exponentiation.

  Shamir's main protocol is significantly slower than our protocol, requiring a complex conditioning process. But Shamir also includes a more optimized version of his protocol for logarithmic space, given two way access to a randomness tape. This is interesting on its own right, as logarithmic space with only one way access to randomness is in P, but also achieves better parameters, nearly matching our own. But Shamir's proof does not work well for sublinear space, and does not provide an efficient prover.

• Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE, in RANDOM 2023 (RANDOM 2023). Presention, 2022 (For Research Preparation Exam), 2023 (RANDOM 2023).

  This proves two results. The first is a tighter circuit lower bound for MA with one bit of advice. Specifically there is a problem requiring super linear circuits that Arthur can verify in only slightly more time than the minimum circuit size. More generally, the untrusted advice is input oblivious. A high level take away, vaguely speaking, is that even a tiny bit of extra untrusted advice can do more than slightly less trusted advice.

  The other result, the main lemma used in this paper, is that the verifier for a PCP for a time T algorithm only requires time approximately log(T) (for T ≥ 2^n), even while making log(log(T)) queries. We suspect that this could be improved in many ways, such as using constantly many queries. But the new thing is getting fewer than log(T) queries while maintaining a quasi log(T) verifier time. This comes from closer analysis of the query function in a robust PCP so that the composed PCP does not spend too long finding the location of a symbol in the outer PCP. Another result is that the equivalence between MIP and NEXP is tight.

• Unitarization Through Approximate Basis.

  In classical programming, you often have several values you want may want to compute, depending on the input. The goal of this project was to extend this to the quantum world. In particular, we want to extend this in such a way so as to leave no entangled garbage on any input, and to disturb as few states as possible. To do this, I solve an arguably more interesting problem: The Approximate Basis. Given black box access to circuits computing n quantum states, X, construct circuits outputting an approximation of orthonormal states, Y, such that every state in X can be approximated as a superposition of states in Y. Our main result is that approximate basis can be solved for n qubit states in polynomial time with error nearly polynomially small for up to log(n)/log(log(n)) states.

  This started out as a class project with Scott Aaronson, and I thought it was a fun problem. It is non trivial because for most naive solutions for the unitarization problem, if you give the algorithm an output state as input, it fails to reset any auxiliary qubits to 0. While I found the problem fun, there aren't any clear applications.

• Size Bounds on Low Depth Circuits for Promise Majority, in Foundations of Software Technology and Theoretical Computer Science 2020 (FSTTCS 2020). Presentation Long (Draft), Short, and Video.

  We define the promise majority problem as majority promised either at most epsilon of the input bits are 1, or at most epsilon of the input bits are 0. This is often called approximate majority. We show that for any constant epsilon, a depth 3 alternating circuit requires more n^(2 + a) gates for some constant a greater than 0. This shows some limitations in efficient derandomization of AC0 circuits using PRGs with minimal circuit depth increase. As a compliment, we show more efficient AC0 circuits for computing promise majority at larger depths.

• Task and Timing: Separating Procedural and Tactical Knowledge in Student Models, in the proceedings of the 10th International Conference on Educational Data Mining (EDM 2017).

  We introduced a learner model for open ended problem domains called Ranked Knowledge Tracing (RKT), and RKT-SR, RKT Skill Recognition, which extend the technique of Bayesian Knowledge Tracing. RKT uses a hidden markov model for skills, with independence for skills, like BKT, but applies it in a setting with many ranked options using different skills. RKT uses a geometric approach where we model the player as trying the optimal option, and if they fail it, trying the next, and so on. Finally we normalize the probabilities. This worked better to predict what a student would do than other, more naive predictions, for instance just asking if a student would use the ideal option based on their knowledge of that skill alone.

  This was an early work I did as an undergrad, and has some major limitations. For instance, our parameter fitting was done by brute force, but not at a very high resolution. Still, models like this offer promise in domains with limited data, especially since the models have built in interpretability. Interpretability is very important in learner models, where we are not actually interested in accuracy, but are interested in determining student knowledge.

Artistic Interests