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 do comics, 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. Quackack.com will hold most of my non research related things.
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.
Outside of my research, I do web comics at quackack.com. Think somewhere between xkcd and smbc with a bunch of complexity theory thrown in.
I also occasionally make children's books or shirt designs, and other random things. If you are interested in any of that, they are linked from quackack.com, and I will update there more regularly.
Wow, really? You want to know something else about me? Well, why not give you my life story?
I was born and raised in a small town in Missouri until I 11, when I moved to North Carolina. I was held back a grade as a child due to speech issues (mostly severe stuttering). I was home schooled from the second grade until I got my GED at 17.
My academic career began in earnest at a local community college called Sandhills Community College. There I got an associates degree in simulation and game design before transferring to NC State. While at Sandhills, I made several android apps under "cryospeedindustries". I haven't maintained these, so they are currently unavailable on the google play store unfortunately. I also interned at a small start up game company called SOF studios.
At NC State, I doubled majored in computer science and mathematics. While at NC State, I did competitive programming for fun and did research under Collin Lynch in intelligent tutoring systems. I also interned with Amazon, who offered me a job.
I worked at Amazon for 2 years in SCOT: Supply Chain Optimization Technology. In particular, our team was SandOP: Sales and Operations Planning. I created software that helped Amazon Fulfillment Centers plan for its labor. While at Amazon, I got free time to work on other projects. I got to take some classes at UT Austin, started making comics, and did internal events like making a quantum computing capture the flag category at a company wide security conference.
And finally, I was accepted into UT Austin's PhD program researching under Dana Moshkovitz researching complexity theory and pseudorandomness.
I like bouldering, virtual reality, and computer hardware. I'm passionate about criminal justice reform and anti-racism. Cinnamon is my favorite spice, I can put both of my legs behind my head, I'm not sure what else you want from me. Gender: cat.
If you are reading this, why? I asked you to stop. I told you, my life's story, other interesting things about me, gave you my contact information and links to my work and my comics. What more do you want from me?
Still here? Okay, maybe you'll leave after a joke? Two Jaguars walk into a bar. All the customers freak out, but the bar owner says to calm down, they have the cash. All of the customers freeze not knowing what to do, but the Jaguars just go up to the bar and drop a bloody wallet. The bar owner takes the wallet and gives the two Jaguars steak. At this point one of the customers turns around and exits the bar. One of the Jaguars watches intently as he does. 1 hour later, the Jaguars return with another wallet.
There, did that scare you off? No? Well was it funny? Okay, eventually I have to stop writing. I'm very busy and can't waste it on stuff like this. And yet you still read! The nerve. If I am being honest, I am quite upset with you. Just reading and reading after I asked you to leave.
Okay, maybe a story will make you leave? One person walks into a bar. The waiter asks
Segmentation fault (core dumped)
You read through that whole story and you are still here? But I prepared such a long, intricate, procedurally generated story. It is clear that I won't outlast you. So to that I say, good day. I hope you got some enjoyment out of this. I'm leaving.
Goodbye.
That didn't work? Okay, fine. You actually win. This is definitely, really the end. Yep. I definitely didn't put any more hidden text in this web page. No sir. I wouldn't do that.
Okay, well if you want to see more, here I am in three different realities. One where I am single, one where I am married to a ball of hair, and one when I'm married to my beautiful wife.