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 supervison of Srikanth Srinivasan

My research interests include (quantum) error correcting codes, PCP's, algebraic complexity and tensor rank.

Publications:

• Ideals, Macaulay Bases, and PCPs
  [ACM], [Arxiv], [Presentation Slides (long)], [STOC talk (coming soon)]
Abstract

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 2^nε, 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.

How to understand this paper

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:

• Obstructions for Associativity in Stable Homotopy Theory
  [arxiv]
Abstract

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.

CV

Hobbies: I like to climb, swim, watch movies 和学习中文. If you are interested in any of these and are in Copenhagen let me know.