My name is Sophus Valentin Willumsgaard.
sophus dot willumgaard at di dot ku dot dk
I am currently a PhD student at BARC (Basic Algorithms Research Copenhagen) University of Copenhagen, under the supervision of Srikanth Srinivasan.
My research interests include (quantum) error correcting codes, PCP's, algebraic complexity and tensor rank.
Publications:
In our previous paper, we gave a new proof of the PCP theorem, that only used one composition. We were then interested in whether the number of compositions could be brought down to 0. In this paper, we give another step on this way, by replacing the more abstract notion of "PCP composition" with the more basic notion of "code concatenation". This can still be seen as a composition step, but it is much simpler than the "PCP composition", and can just be seen as a simple encoding of a simple PCP protocol. This then gives a simple PCP protocol for 3-coloring with the correct parameters, where we can write up how the Prover and verifier works, and which oracles are used within only two pages.
While the code concatenation gives a simpler protocol, it does make the analysis more hairy. The reader is instructed to focus on understanding how the protocol works first, before reading any of the analysis of the low-degree test and proofs in the appendix. With the help of ChatGPT, I created a small demonstration of how the algorithm works for the prover and verifier for a small graph, which is a good starting point.
All known proofs of the PCP theorem rely on multiple "composition" steps, where PCPs over large alphabets are turned into PCPs over much smaller alphabets at a (relatively) small price in the soundness error of the PCP. In this work, we present the first PCP construction using just one composition step. The key ingredient, missing in previous work and finally supplied in this paper, is a basic PCP (of Proximity) of size 2nε, for any ε > 0, that makes Oε(1) queries. At the core of our new construction is a new class of alternatives to "sum-check" protocols, which are able to handle more general subsets than grids. Our new protocols use Macaulay basis to extend previously known protocols to these new settings with surprising ease. In doing so, they highlight why these theories from algebra may be of further use in complexity theory.
The paper's length is mostly due to the fact, that there is a lot of edge cases to check and balancing of parameters. If you are already familiar with the low-degree/Reed-Muller PCP's, then I recommend watching the short STOC talk to understand how our construction differ. If you are new to PCP's then i recommend checking out the longer version of the slides of the presentation, which cover in more depth how the construction works. If you want to understand every detail fully, then you can read the paper itself.
Preprints:
The paper develops obstruction theory for A_n-algebra structures within stable infinity-categories. We demonstrate properties of this theoretical framework and apply it to establish that the spectrum S/4 admits an A_5-multiplication using synthetic spectra. This article is based on my Master thesis. If you care about obstruction theories for E_1-algebras, then this paper might be interesting to you.
Hobbies: I like to climb, swim, watch movies 和学习中文. If you are interested in any of these and are in Copenhagen let me know.