Dion Gijswijt

Followers

Following

Co-authors

Public Views

Interests

Uploads

Papers by Dion Gijswijt

Excluding affine configurations over a finite field

Cornell University - arXiv, Dec 23, 2021

Let ai1x1 +• • •+a ik x k = 0, i ∈ [m] be a balanced homogeneous system of linear equations with ... more Let ai1x1 +• • •+a ik x k = 0, i ∈ [m] be a balanced homogeneous system of linear equations with coefficients aij from a finite field Fq. We say that a solution x = (x1,. .. , x k) with x1,. .. , x k ∈ F n q is generic if every homogeneous balanced linear equation satisfied by x is a linear combination of the given equations. We show that if the given system is tame, subsets S ⊆ F n q without generic solutions must have exponentially small density. Here, the system is called tame if for every implied system the number of equations is less than half the number of used variables. Using a subspace sampling argument this also gives a 'supersaturation result': there is a constant c such that for ǫ > 0 sufficiently small, every subset S ⊆ F n q of size at least q (1−ǫ)n contains Ω(q (k−m−ǫc)n) solutions as n → ∞. For q < 4 the tameness condition can be left out. Our main tool is a modification of the slice rank method to leverage the existence of many solutions in order to obtain high rank solutions.

Download

Enumerating all bilocal Clifford distillation protocols through symmetry reduction

Quantum, May 19, 2022

Entanglement distillation is an essential building block in quantum communication protocols. Here... more Entanglement distillation is an essential building block in quantum communication protocols. Here, we study the class of near-term implementable distillation protocols that use bilocal Clifford operations followed by a single round of communication. We introduce tools to enumerate and optimise over all protocols for up to n = 5 (not necessarily equal) Belldiagonal states using a commodity desktop computer. Furthermore, by exploiting the symmetries of the input states, we find all protocols for up to n = 8 copies of a Werner state. For the latter case, we present circuits that achieve the highest fidelity with perfect operations and no decoherence. These circuits have modest depth and number of two-qubit gates. Our results are based on a correspondence between distillation protocols and double cosets of the symplectic group, and improve on previously known protocols.

Download

UvA-DARE (Digital Academic Repository) A combinatorial identity arising from cobordism theory

Let α = (α 1 , α 2 , • • • , αm) ∈ R m >0. Let α i,j be the vector obtained from α by deleting th... more Let α = (α 1 , α 2 , • • • , αm) ∈ R m >0. Let α i,j be the vector obtained from α by deleting the entries α i and α j. Besser and Moree [1] introduced some invariants and near invariants related to the solutions ∈ {±1} m−2 of the linear inequality |α i − α j | < , α i,j < α i + α j , where , denotes the usual inner product and α i,j the vector obtained from α by deleting α i and α j. The main result of Besser and Moree [1] is extended here to a much more general setting, namely that of certain maps from finite sets to {−1, 1}.

Download

Achieving Sybil-Proofness in Distributed Work Systems

In a multi-agent system where agents provide quantifiable work for each other on a voluntary basi... more In a multi-agent system where agents provide quantifiable work for each other on a voluntary basis, reputation mechanisms are incorporated to induce cooperation. Hereby agents assign their peers numerical scores based on their reported transaction histories. In such systems, adversaries can launch an attack by creating fake identities called Sybils, who report counterfeit transactions among one another, with the aim of increasing their own scores in the eyes of others. This paper provides new results about the Sybil-proofness of reputation mechanisms. We revisit the impossibility result of Seuken and Parkes (2011), who show that strongly-beneficial Sybil attacks cannot be prevented on reputation mechanisms satisfying three particular requirements. We prove that, under a more rigorous set of definitions of Sybil attack benefit, this result no longer holds. We characterise properties under which reputation mechanisms are susceptible to strongly-beneficial Sybil attacks. Building on ou...

Download

UvA-DARE ( Digital Academic Repository ) Graph parameters and invariants of the orthogonal group

Disclaimer/Complaints regulations If you believe that digital publication of certain material inf... more Disclaimer/Complaints regulations If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library: http://uba.uva.nl/en/contact, or a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.

Download

On the constant in a transference inequality for the vector-valued Fourier transform

arXiv: Classical Analysis and ODEs, 2015

The standard proof of the equivalence of Fourier type on R^d and on the torus T^d is usually stat... more

Download

The power of shaking hands

Hamiltonian paths By a Hamiltonian path in a graph G, we mean a path that visits every node exact... more Hamiltonian paths By a Hamiltonian path in a graph G, we mean a path that visits every node exactly once. Here, we will be interested in Hamiltonian paths between to given nodes s and t (we ignore the direction in which the path is traversed and only consider the set of edges on the path). Not every graph has a Hamiltonian path, and it is NP-hard to decide if a given graph has a Hamiltonian path between two given nodes. However, if we have one such path, we can sometimes conclude that there must be another.

Download

Integer packing sets form a well-quasi-ordering

Oper. Res. Lett., 2021

An integer packing set is a set of non-negative integer vectors with the property that, if a vect... more An integer packing set is a set of non-negative integer vectors with the property that, if a vector $x$ is in the set, then every non-negative integer vector $y$ with $y \leq x$ is in the set as well. Integer packing sets appear naturally in Integer Optimization. In fact, the set of integer points in any packing polyhedron is an integer packing set. The main result of this paper is that integer packing sets, ordered by inclusion, form a well-quasi-ordering. This result allows us to answer a question recently posed by Bodur et al. In fact, we prove that the k-aggregation closure of any packing polyhedron is again a packing polyhedron. The generality of our main result allows us to provide a generalization to non-polyhedral sets: The k-aggregation closure of any downset of $\mathbb{R}^n_+$ is a packing polyhedron.

Download

$Research paper thumbnail of Asymptotic upper bounds on progression-free sets in $\mathbb{Z}_p^n$$

Asymptotic upper bounds on progression-free sets in $\mathbb{Z}_p^n$

arXiv: Combinatorics, 2016

We show that any subset of $\mathbb{Z}_p^n$ ($p$ an odd prime) without $3$-term arithmetic progre... more

Download

$Research paper thumbnail of On the size of subsets of $\mathbb{F}_q^n$ avoiding solutions to linear systems with repeated columns$

On the size of subsets of $\mathbb{F}_q^n$ avoiding solutions to linear systems with repeated columns

Cornell University - arXiv, Nov 18, 2021

Consider a system of m balanced linear equations in k variables with coefficients in Fq. If k ≥ 2... more Consider a system of m balanced linear equations in k variables with coefficients in Fq. If k ≥ 2m + 1, then a routine application of the slice rank method shows that there are constants β, γ ≥ 1 with γ < q such that, for every subset S ⊆ F n q of size at least β • γ n , the system has a solution (x1,. .. , x k) ∈ S k with x1,. .. , x k not all equal. Building on a series of papers by Mimura and Tokushige and on a paper by Sauermann, this paper investigates the problem of finding a solution of higher non-degeneracy; that is, a solution where x1,. .. , x k are pairwise distinct, or even a solution where x1,. .. , x k do not satisfy any balanced linear equation that is not a linear combination of the equations in the system. In this paper, we present general techniques for systems with repeated columns. This class of linear systems is disjoint from the class covered by Sauermann's result, and captures the systems studied by Mimura and Tokushige into a single proof. A special case of our results shows that, if S ⊆ F n p is a subset such that S − S does not contain a non-trivial k-term arithmetic progression (where p ≥ k ≥ 3), then S must have exponentially small density.

Download

Constructing tree decompositions of graphs with bounded gonality

Journal of Combinatorial Optimization

In this paper, we give a constructive proof of the fact that the treewidth of a graph is at most ... more In this paper, we give a constructive proof of the fact that the treewidth of a graph is at most its divisorial gonality. The proof gives a polynomial time algorithm to construct a tree decomposition of width at most k, when an effective divisor of degree k that reaches all vertices is given. We also give a similar result for two related notions: stable divisorial gonality and stable gonality.

Download

Computing graph gonality is hard

Discrete Applied Mathematics

$Research paper thumbnail of On large subsets of \mathbb F_q^n with no three-term arithmetic progression$

On large subsets of \mathbb F_q^n with no three-term arithmetic progression

Annals of Mathematics

Important note To cite this publication, please use the final published version (if applicable). ... more

Download

Computing divisorial gonality is hard

Matrix algebras and semidefinite programming techniques for codes

Algorithmica, 2005

Download

De Huwelijksstelling van Hall

Int J Electron Commer, 2009

ABSTRACT This popularizing paper gives an exposition to a wide audience of bipartite matching the... more ABSTRACT This popularizing paper gives an exposition to a wide audience of bipartite matching theory. Through the example of marrying a set of men to a set of women, K\&quot;onigs theorem, Hall&#39;s marriage theorem and an algorithm for maximum size matching, are explained at an elementary level.

Semidefinite programming and coding bounds

Fractional matroid matching

Semidefinite Code Bounds Based on Quadruple Distances

IEEE Transactions on Information Theory, 2000

Let A(n, d) be the maximum number of 0, 1 words of length n, any two having Hamming distance at l... more

Download

De wiskunde van het vouwen

Stoch Proc Appl, 2008

Dion Gijswijt

Uploads

Papers by Dion Gijswijt

Log In