# Christoph Spiegel

### Postdoctoral reasearcher working on

Combinatorics, Optimization and Learning.

Room 3036 • 14195 Berlin

**Office hours**

Wednesdays at the Zuse

Institute by e-mail appointment

#### proceedings

**5. The Rado Multiplicity Problem in Vector Spaces over Finite Fields**

We study an analogue of the Ramsey multiplicity problem for additive structures, in particular establishing the minimum number of monochromatic 3-APs in 3-colorings of GF(3)ⁿ as well as obtaining the first non-trivial lower bound for the minimum number of monochromatic 4-APs in 2-colorings of GF(5)ⁿ. The former parallels results by Cumings et al (2013) in extremal graph theory and the latter improves upon results of Saad and Wolf (2017) The lower bounds are notably obtained by extending the flag algebra calculus of Razborov (2007) to additive structures in vector spaces over finite fields.

**4. How I Learned to Stop Worrying and Love Retraining**

Network pruning is a widely used technique for effectively compressing Deep Neural Networks with little to no degradation in performance during inference. Iterative Magnitude Pruning (IMP) is one of the most established approaches for network pruning, consisting of several iterative training and pruning steps, where a significant amount of the network's performance is lost after pruning and then recovered in the subsequent retraining phase. While commonly used as a benchmark reference, it is often argued that a) it reaches suboptimal states by not incorporating sparsification into the training phase, b) its global selection criterion fails to properly determine optimal layer-wise pruning rates and c) its iterative nature makes it slow and non-competitive. In light of recently proposed retraining techniques, we investigate these claims through rigorous and consistent experiments where we compare IMP to pruning-during-training algorithms, evaluate proposed modifications of its selection criterion and study the number of iterations and total training time actually required. We find that IMP with SLR for retraining can outperform state-of-the-art pruning-during-training approaches without or with only little computational overhead, that the global magnitude selection criterion is largely competitive with more complex approaches and that only few retraining epochs are needed in practice to achieve most of the sparsity-vs.-performance tradeoff of IMP. Our goals are both to demonstrate that basic IMP can already provide state-of-the-art pruning results on par with or even outperforming more complex or heavily parameterized approaches and also to establish a more realistic yet easily realisable baseline for future research.

**3. Fully Computer-Assisted Proofs in Extremal Combinatorics**

We study two related problems concerning the number of monochromatic cliques in two-colorings of the complete graph that go back to questions of Erdős. Most notably, we improve the 25-year-old upper bounds of Thomason on the Ramsey multiplicity of $K_4$ and $K_5$ and we settle the minimum number of independent sets of size 4 in graphs with clique number at most 4. Motivated by the elusiveness of the symmetric Ramsey multiplicity problem, we also introduce an off-diagonal variant and obtain tight results when counting monochromatic $K_4$ or $K_5$ in only one of the colors and triangles in the other. The extremal constructions for each problem turn out to be blow-ups of a finite graph and were found through search heuristics. They are complemented by lower bounds and stability results established using Flag Algebras, resulting in a fully computer-assisted approach. More broadly, these problems lead us to the study of the region of possible pairs of clique and independent set densities that can be realized as the limit of some sequence of graphs.

**2. New Ramsey Multiplicity Bounds and Search Heuristics **

We study two related problems concerning the number of monochromatic cliques in two-colorings of the complete graph that go back to questions of Erd\H{o}s. Most notably, we improve the 25-year-old upper bound of the $K_4$ and $K_5$ Ramsey multiplicity due to Thomason and settle the minimum number of independent sets of size $4$ in graphs with clique number at most $4$. We also introduce a notion of off-diagonal Ramsey multiplicity, obtaining two tight results when counting triangles in one color, and more broadly motivate this question by relating it to the study of which pairs of clique and independent set densities can be realized as the limit of some sequence of graphs.

**1. On a problem of Sárkőzy and Sós for multivariate linear forms**

We prove that for pairwise co-prime numbers \(k_1,\dots,k_d \geq 2\) there does not exist any infinite set of positive integers \(A\) such that the representation function \(r_A (n) = \{ (a_1, \dots, a_d) \in A^d : k_1 a_1 + \dots + k_d a_d = n \}\) becomes constant for \(n\) large enough. This result is a particular case of our main theorem, which poses a further step towards answering a question of Sárkőzy and Sós and widely extends a previous result of Cilleruelo and Rué for bivariate linear forms.

#### journal

**10. Another Note on Intervals in the Hales-Jewett Theorem**

The Hales-Jewett Theorem states that any \(r\)-colouring of \([m]^n\) contains a monochromatic combinatorial line if \(n\) is large enough. Shelah's proof of the theorem implies that for \(m = 3\) there always exists a monochromatic combinatorial lines whose set of active coordinates is the union of at most \(r\) intervals. Conlon and Kamčev proved the existence of colourings for which it cannot be fewer than \(r\) intervals if \(r\) is odd. For \(r = 2\) however, Leader and Räty showed that one can always find a monochromatic combinatorial line whose active coordinate set is a single interval. In this paper, we extend the result of Leader and Räty to the case of all even \(r\)=, showing that one can always find a monochromatic combinatorial line in \([3]^n\) whose set of active coordinate is the union of at most \(r-1\) intervals.

**9. On strong infinite Sidon and \(B_h\) sets and random sets of integers**

A set of integers \(S \subset \mathbb{N}\) is an \(\alpha\)-strong Sidon} set if the pairwise sums of its elements are far apart by a certain measure depending on \(\alpha\), more specifically if \( \big| (x+w) - (y+z) \big| \geq \max \{ x^{\alpha},y^{\alpha},z^{\alpha},w^\alpha \} \) for every \(x,y,z,w \in S\) satisfying \( \{x,w\} \neq \{y,z\}\). We obtain a new lower bound for the growth of \( \alpha \)-strong infinite Sidon sets when \( 0 \leq \alpha < 1 \). We also further extend that notion in a natural way by obtaining the first non-trivial bound for \( \alpha \)-strong infinite \( B_h \) sets. In both cases, we study the implications of these bounds for the density of, respectively, the largest Sidon or \( B_h \) set contained in a random infinite subset of \( \mathbb{N} \). Our theorems improve on previous results by Kohayakawa, Lee, Moreira and Rödl.

**8. An Erdős-Fuchs Theorem for Ordered Representation Functions**

Let $k\geq 2$ be a positive integer. We study concentration results for the ordered representation functions $r^{\leq}_k(\mathcal{A},n) = \# \big\{ (a_1 \leq \dots \leq a_k) \in \mathcal{A}^k : a_1+\dots+a_k = n \big\}$ and $r^{<}_k(\mathcal{A},n) = \# \big\{ (a_1 < \dots < a_k) \in \mathcal{A}^k : a_1+\dots+a_k = n \big\}$ for any infinite set of non-negative integers $\mathcal{A}$. Our main theorem is an Erdős-Fuchs-type result for both functions: for any $c > 0$ and $\star \in \{\leq,<\}$ we show that $\sum_{j = 0}^{n} \Big( r^{\star}_k (\mathcal{A},j) - c \Big)= o\big(n^{1/4}\log^{-1/2}n\big)$ is not possible. We also show that the mean squared error $E^\star_{k,c}(\mathcal{A},n)=\frac{1}{n} \sum_{j = 0}^{n} \Big( r^{\star}_k(\mathcal{A},j) - c \Big)^2$ satisfies $\limsup_{n \to \infty} E^\star_{k,c}(\mathcal{A},n)>0$. These results extend two theorems for the non-ordered representation function proved by Erdős and Fuchs in the case of $k=2$.

**7. On the Odd Cycle Game and Connected Rules**

We study the positional game where two players, Maker and Breaker, alternately select respectively 1 and b previously unclaimed edges of \( K_n \). Maker wins if she succeeds in claiming all edges of some odd cycle in Kn and Breaker wins otherwise. Improving on a result of Bednarska and Pikhurko, we show that Maker wins the odd cycle game if \( b \leq (4 - \sqrt{6})/5 +o(1) n \). We furthermore introduce “connected rules” and study the odd cycle game under them, both in the Maker-Breaker as well as in the Client-Waiter variant.

**6. A step beyond Freĭman's theorem for set addition modulo a prime**

Freĭman's 2.4-Theorem states that any set \(A \subset \mathbb{Z}_p\) satisfying \(|2A| \leq 2.4|A| - 3 \) and \(|A| < p/35\) can be covered by an arithmetic progression of length at most \(|2A| - |A| + 1\). A more general result of Green and Ruzsa implies that this covering property holds for any set satisfying \(|2A| \leq 3|A| - 4\) as long as the rather strong density requirement \(|A| < p/10^{215}\) is satisfied. We present a version of this statement that allows for sets satisfying \(|2A| \leq 2.48|A| - 7\) with the more modest density requirement of \(|A| < p/10^{10}\).

**5. On a problem of Sárkőzy and Sós for multivariate linear forms**

We prove that for pairwise co-prime numbers \(k_1,\dots,k_d \geq 2\) there does not exist any infinite set of positive integers \(A\) such that the representation function \(r_A (n) = \{ (a_1, \dots, a_d) \in A^d : k_1 a_1 + \dots + k_d a_d = n \}\) becomes constant for \(n\) large enough. This result is a particular case of our main theorem, which poses a further step towards answering a question of Sárkőzy and Sós and widely extends a previous result of Cilleruelo and Rué for bivariate linear forms.

**4. On the optimality of the uniform random strategy**

The concept of biased Maker-Breaker games, introduced by Chvátal and Erdős, is a central topic in the field of positional games, with deep connections to the theory of random structures. For any given hypergraph \(\cal H\) the main questions is to determine the smallest bias \(q({\cal H})\) that allows Breaker to force that Maker ends up with an independent set of \(\cal H\). Here we prove matching general winning criteria for Maker and Breaker when the game hypergraph satisfies a couple of natural `container-type' regularity conditions about the degree of subsets of its vertices. This will enable us to derive a hypergraph generalization of the \(H\)-building games, studied for graphs by Bednarska and Łuczak. Furthermore, we investigate the biased version of generalizations of the van der Waerden games introduced by Beck. We refer to these generalizations as Rado games and determine their threshold bias up to constant factors by applying our general criteria. We find it quite remarkable that a purely game theoretic deterministic approach provides the right order of magnitude for such a wide variety of hypergraphs, when the generalizations to hypergraphs in the analogous setup of sparse random discrete structures are usually quite challenging.

**3. Additive Volume of Sets Contained in Few Arithmetic Progressions**

A conjecture of Freĭman gives an exact formula for the largest volume of a finite set \(A\) of integers with given cardinality \(k = |A|\) and doubling \(T = |2A|\). The formula is known to hold when \(T \le 3k-4\), for some small range over \(3k-4\) and for families of structured sets called chains. In this paper we extend the formula to sets of every dimension and prove it for sets composed of three segments, giving structural results for the extremal case. A weaker extension to sets composed of a bounded number of segments is also discussed.

G.A. Freĭman, O. Serra, and C. Spiegel. Integers 19:#A34, 2019.

**2. Threshold functions and Poisson convergence for systems of equations in random sets**

We present a unified framework to study threshold functions for the existence of solutions to linear systems of equations in random sets which includes arithmetic progressions, sum-free sets, \(B_{h}[g]\)-sets and Hilbert cubes. In particular, we show that there exists a threshold function for the property "\(\mathcal{A}\) contains a non-trivial solution of \(M\cdot\textbf{x}=\textbf{0}\)", where \(\mathcal{A}\) is a random set and each of its elements is chosen independently with the same probability from the interval of integers \(\{1,\dots,n\}\). Our study contains a formal definition of trivial solutions for any combinatorial structure, extending a previous definition by Ruzsa when dealing with a single equation. Furthermore, we study the behaviour of the distribution of the number of non-trivial solutions at the threshold scale. We show that it converges to a Poisson distribution whose parameter depends on the volumes of certain convex polytopes arising from the linear system under study as well as the symmetry inherent in the structures, which we formally define and characterize.

**1. A Note on Sparse Supersaturation and Extremal Results for Linear Homogeneous Systems**

We study the thresholds for the property of containing a solution to a linear homogeneous system in random sets. We expand a previous sparse Szémeredi-type result of Schacht to the broadest class of matrices possible. We also provide a shorter proof of a sparse Rado result of Friedgut, Rödl, Ruciński and Schacht based on a hypergraph container approach due to Nenadov and Steger. Lastly we further extend these results to include some solutions with repeated entries using a notion of non-trivial solutions due to Ruzsa as well as Rué et al.

#### preprint

**6. The 4-color Ramsey Multiplicity of Triangles**

One of the most impactful tools for computer-assisted proofs in mathematics is due to Razborov, who introduced flag algebras in 2007 in order to study the limits of discrete objects in Extremal Combinatorics using concepts from First-Order Logic and Model Theory. They allow one to apply a Cauchy-Schwarz-type argument to classic problems in Turán and Ramsey theory by solving a concrete semidefinite programming formulation. In this work we exploit symmetries in these formulations in order to reduce their size and extend the envelope of what is attainable using this technique. The resulting methods are based on combinatorial insights and a parameter-dependent notion of homomorphisms. To demonstrate their efficacy, we determine the 4-color Ramsey multiplicity of triangles.

**4. Compression-aware Training of Neural Networks using Frank-Wolfe**

Many existing Neural Network pruning approaches either rely on retraining to compensate for pruning-caused performance degradation or they induce strong biases to converge to a specific sparse solution throughout training. A third paradigm obtains a wide range of compression ratios from a single dense training run while also avoiding retraining. Recent work of Pokutta et al. (2020) and Miao et al. (2022) suggests that the Stochastic Frank-Wolfe (SFW) algorithm is particularly suited for training state-of-the-art models that are robust to compression. We propose leveraging k-support norm ball constraints and demonstrate significant improvements over the results of Miao et al. (2022) in the case of unstructured pruning. We also extend these ideas to the structured pruning domain and propose novel approaches to both ensure robustness to the pruning of convolutional filters as well as to low-rank tensor decompositions of convolutional layers. In the latter case, our approach performs on-par with nuclear-norm regularization baselines while requiring only half of the computational resources. Our findings also indicate that the robustness of SFW-trained models largely depends on the gradient rescaling of the learning rate and we establish a theoretical foundation for that practice.

**3. Deep Neural Network Training with Frank-Wolfe**

This paper studies the empirical efficacy and benefits of using projection-free first-order methods in the form of Conditional Gradients, a.k.a. Frank-Wolfe methods, for training Neural Networks with constrained parameters. We draw comparisons both to current state-of-the-art stochastic Gradient Descent methods as well as across different variants of stochastic Conditional Gradients. In particular, we show the general feasibility of training Neural Networks whose parameters are constrained by a convex feasible region using Frank-Wolfe algorithms and compare different stochastic variants. We then show that, by choosing an appropriate region, one can achieve performance exceeding that of unconstrained stochastic Gradient Descent and matching state-of-the-art results relying on \(L^2\) -regularization. Lastly, we also demonstrate that, besides impacting performance, the particular choice of constraints can have a drastic impact on the learned representations.

**2. Projection-Free Adaptive Gradients for Large-Scale Optimization**

The complexity in large-scale optimization can lie in both handling the objective function and handling the constraint set. In this respect, stochastic Frank-Wolfe algorithms occupy a unique position as they alleviate both computational burdens, by querying only approximate first-order information from the objective and by maintaining feasibility of the iterates without using projections. In this paper, we improve the quality of their first-order information by blending in adaptive gradients. Starting from the design of adaptive gradient algorithms, we propose to solve the occurring constrained optimization subproblems very incompletely via a fixed and small number of iterations of the Frank-Wolfe algorithm (often times only 2 iterations), in order to preserve the low per-iteration complexity. We derive convergence rates and demonstrate the computational advantage of our method over the state-of-the-art stochastic Frank-Wolfe algorithms on both convex and nonconvex objectives.

**1. Independent Chains in Acyclic Posets**

We consider the problem of determining the maximum order of an induced vertex-disjoint union of cliques in a graph. More specifically, given some family of graphs $\mathcal{G}$ of equal order, we are interested in the parameter $a(\mathcal{G}) = \min_{G \in \mathcal{G}} \max \{ |U| : U \subseteq V, G[U] \text{ is a vertex-disjoint union of cliques} \}$. We determine the value of this parameter precisely when $\mathcal{G}$ is the family of comparability graphs of $n$-element posets with acyclic cover graph. In particular, we show that $a(\mathcal{G}) = (n+o(n))/\log_2 (n)$ in this class.

#### conference and workshop talks

**July 2024**
DMD Conference,
Alcalá de Henares
PDF

**October 2023**
BMS RTA 8 - Practical Course,
Berlin
PDF

**August 2023**
12th EuroComb Conference,
Prague
PDF

**August 2023**
ICIAM 2023 Minisymposium: Advances in Optimization I,
Tokyo
PDF

**August 2023**
5th DOxML Conference,
Tokyo
PDF

**June 2023**
FoCM 2023 Workshop I.3 Workshop,
Paris
PDF

**May 2023**
CANT Conference,
New York
PDF

**March 2023**
Optimization and ML Workshop,
Waischenfeld
PDF

**February 2023**
37th AAAI Conference,
Washington, DC
PDF

**January 2023**
Aussois Workshop,
Aussois
PDF

**December 2022**
Recent Advances in Optimization Workshop,
Toronto
PDF

**September 2022**
6th RIKEN-MODAL Workshop,
Tokyo
and
Fukuoka
PDF

**July 2022**
DMD Conference,
Santander
PDF

**June 2019**
Postgraduate Combinatorial Conference,
Oxford
PDF

**June 2019**
GAPCOMB Workshop,
Campelles
PDF

**June 2018**
DMD Conference,
Sevilla
PDF

**May 2018**
CANT Conference,
New York
PDF

**March 2018**
GRAPHS at IMPA,
Rio de Janeiro
PDF

**September 2017**
The Music of Numbers Conference,
Madrid
PDF

**June 2017**
Interactions with Combinatorics
PDF

**March 2017**
FUB-TAU workshop
PDF

#### seminar talks

**February 2023**
LIMDA Seminar,
Barcelona

**April 2022**
LIMDA Seminar,
Barcelona

**November 2019**
Research Seminar Combinatorics,
Berlin

**November 2019**
Research Seminar Large Networks and Random Graphs,
Ilmenau

**May 2019**
Seminar and PhD Seminar on Combinatorics, Games and Optimisation,
London

**May 2019**
Combinatorial Theory Seminar,
Oxford

**February 2019**
Extremal Set Theory Seminar,
Budapest

**December 2018**
Research Seminar Combinatorics,
Berlin

**December 2017**
Research Seminar Combinatorics,
Berlin

**October 2017**
LIMDA Seminar,
Barcelona

**May 2017**
LIMDA Seminar,
Barcelona

**March 2016**
LIMDA Seminar,
Barcelona

**February 2016**
Research Seminar Combinatorics,
Berlin

**January 2016**
Research Seminar Combinatorics,
Berlin

**December 2015**
"What is ...?" seminar

**October 2015**
Research Seminar Combinatorics,
Berlin

#### 2023

**September** Wőrkshop on Open Problems in Combinatorics and Graph Theory, Wilhelmsaue

**August** 10th EUROCOMB Conference, Prague

**August** 10th ICIAM Conference, Tokyo

**August** 5th DOxML Conference, Tokyo

**June** 11th FoCM Conference, Paris

**February** IPAM Workshop on Machine Assisted Proofs, Los Angeles, California

**February** 37th AAAI Conference on Artificial Intelligence, Washington, DC

**January** 25th Aussois Combinatorial Optimization Workshop, Aussois

#### 2022

**December** Workshop on Recent Advances in Optimization, Toronto

**September** 6th RIKEN-IMI-ISM-NUS-ZIB-MODAL-NHR Workshop, Tokyo and Fukuoka

**August** Wőrkshop on Open Problems in Combinatorics and Graph Theory, Wilhelmsaue

**July** GAPCOMB Workshop, Montserrat

**July**Discrete Mathematics Days, Santander

#### 2021

**September** EUROCOMB 2021, Barcelona

**September** Wőrkshop on Open Problems in Combinatorics and Graph Theory, Wilhelmsaue

#### 2019

**October** Growth in Finite and Infinite Groups, Oberwolfach

**September** Wőrkshop on Open Problems in Combinatorics and Graph Theory, Wilhelmsaue

**June** GAPCOMB Workshop, Campelles

**June** Postgraduate Combinatorial Conference, Oxford

**May** One-Day Meeting in Combinatorics, Oxford

#### 2018

**September** Wőrkshop on Open Problems in Combinatorics and Graph Theory, Wilhelmsaue

**June** Discrete Mathematics Days, Sevilla

**May** Combinatorial and Additive Number Theory Conference, New York

**May** Georgia Discrete Analysis Conference, Athens

**March** Graphs and Randomness, Rio de Janeiro

#### 2017

**October** BMS-BGSMath Junior Meeting, Barcelona

**September** Wőrkshop on Open Problems in Combinatorics and Graph Theory, Wilhelmsaue

**September** The Music of Numbers, Madrid

**June** Interactions with Combinatorics, Birmingham

**May to June** Random Discrete Structures, Barcelona

**April to May** Interactions of harmonic analysis, combinatorics and number theory, Barcelona

**March** FUB-TAU Joint Workshop, Tel Aviv

**January** SODA17, ANALCO17 and ALENEX17, Barcelona

#### 2014 - 2016

**September 2016** Wőrkshop on Open Problems in Combinatorics and Graph Theory, Wilhelmsaue

**July 2016** Symposium Diskrete Mathematik, Berlin

**July 2016** Discrete Mathematics Days Barcelona, Barcelona

**February 2016** PosGames2016, Berlin

**January 2016** Combinatorial and Additive Number Theory, Graz

**September 2015** Cargèse Fall School on Random Graphs

**September 2015** Wőrkshop on Open Problems in Combinatorics and Graph Theory, Vysoká Lípa

**May 2015** Berlin-Poznan-Hamburg Seminar: 20th Anniversary, Berlin

**October 2014** Methods in Discrete Structures Block Course: Towards the Polynomial Freĭman-Ruzsa Conjecture, Berlin

**
Winter 2023
** Lecturer for
Einführung in die Lineare und Kombinatorische Optimierung (ADM I) at TUB

**
Summer 2023
** Lecturer for
Analysis I und Lineare Algebra für Ingenieurwissenschaften at TUB

**
Autumn 2018
** Assistant for
Discrete Mathematics and Optimization at UPF

**
Autumn 2017
** Assistant for
Discrete Mathematics and Optimization at UPF

**
Winter 2013
** Tutor for
Analysis I (Lehramt) at FUB

**
Summer 2012
** Tutor for
Analysis II (Lehramt) at FUB

**
Summer 2011
** Tutor for
Analysis I (Lehramt) at FUB

**June 2020**Ph.D. in Applied Mathematics at Universitat Politècnica de Catalunya PDF

**March 2015** Master of Science at Freie Universität Berlin

*Approximating Primitive Integrals and Aircraft Performance*(09/2014 - 03/2015) in the area of Graph Theory and Optimization under the supervision of Prof. Dr. Ralf Borndörfer. The research was part of the Flight Trajectory Optimization on Airway Networks project at the Zuse-Institute Berlin (ZIB). The main industry partner of this project is Lufthansa Systems Frankfurt. Furthermore it is part of the joint project

*E-Motion - Energieeffiziente Mobilität*which is funded by the German Ministry of Education and Research (BMBF).During the course of my research I was employed as a student research assistant at the ZIB (05/2014 - 03/2015).

**September 2012** Bachelor of Science at Freie Universität Berlin

*Numerical Pricing of Financial Derivatives*(06/2012 - 09/2012) under the supervision of Prof. Dr. Carsten Hartmann.

**Juni 2009** Abitur at Canisius-Kolleg Berlin