BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Dion Gijswijt

Dion Gijswijt appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.OCquant-phData Structures and AlgorithmsDiscrete MathematicsInformation Theorymath.CAmath.FAmath.ITmath.NTmath.RA

Catalog footprint

What is connected

15works
11topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

15 published item(s)

preprint2022arXiv

Enumerating all bilocal Clifford distillation protocols through symmetry reduction

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) Bell-diagonal 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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Constructing Tree Decompositions of Graphs with Bounded Gonality

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.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Integer packing sets form a well-quasi-ordering

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.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

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

In this note, we show that the method of Croot, Lev, and Pach can be used to bound the size of a subset of $F_q^n$ with no three terms in arithmetic progression by $c^n$ with $c < q$. For $q=3$, the problem of finding the largest subset with no three terms in arithmetic progression is called the `cap problem'. Previously the best known upper bound for the cap problem, due to Bateman and Katz, was $O(3^n / n^{1+ε})$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Approximation Algorithms for Hard Capacitated $k$-facility Location Problems

We study the capacitated $k$-facility location problem, in which we are given a set of clients with demands, a set of facilities with capacities and a constant number $k$. It costs $f_i$ to open facility $i$, and $c_{ij}$ for facility $i$ to serve one unit of demand from client $j$. The objective is to open at most $k$ facilities serving all the demands and satisfying the capacity constraints while minimizing the sum of service and opening costs. In this paper, we give the first fully polynomial time approximation scheme (FPTAS) for the single-sink (single-client) capacitated $k$-facility location problem. Then, we show that the capacitated $k$-facility location problem with uniform capacities is solvable in polynomial time if the number of clients is fixed by reducing it to a collection of transportation problems. Third, we analyze the structure of extreme point solutions, and examine the efficiency of this structure in designing approximation algorithms for capacitated $k$-facility location problems. Finally, we extend our results to obtain an improved approximation algorithm for the capacitated facility location problem with uniform opening cost.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Treewidth is a lower bound on graph gonality

We prove that the (divisorial) gonality of a finite connected graph is lower bounded by its treewidth. We show that equality holds for grid graphs and complete multipartite graphs. We prove that the treewidth lower bound also holds for \emph{metric graphs} by constructing for any positive rank divisor on a metric graph $Γ$ a positive rank divisor of the same degree on a subdivision of the underlying graph. Finally, we show that the treewidth lower bound also holds for a related notion of gonality defined by Caporaso and for stable gonality as introduced by Cornelissen et al.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An algorithm for weighted fractional matroid matching

Let M be a matroid on ground set E. A subset l of E is called a `line' when its rank equals 1 or 2. Given a set L of lines, a `fractional matching' in (M,L) is a nonnegative vector x indexed by the lines in L, that satisfies a system of linear constraints, one for each flat of M. Fractional matchings were introduced by Vande Vate, who showed that the set of fractional matchings is a half-integer relaxation of the matroid matching polytope. It was shown by Chang et al. that a maximum size fractional matching can be found in polynomial time. In this paper we give a polynomial time algorithm to find for any given weights on the lines in L, a maximum weight fractional matching.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Violating the Shannon capacity of metric graphs with entanglement

The Shannon capacity of a graph G is the maximum asymptotic rate at which messages can be sent with zero probability of error through a noisy channel with confusability graph G. This extensively studied graph parameter disregards the fact that on atomic scales, Nature behaves in line with quantum mechanics. Entanglement, arguably the most counterintuitive feature of the theory, turns out to be a useful resource for communication across noisy channels. Recently, Leung, Mancinska, Matthews, Ozols and Roy [Comm. Math. Phys. 311, 2012] presented two examples of graphs whose Shannon capacity is strictly less than the capacity attainable if the sender and receiver have entangled quantum systems. Here we give new, possibly infinite, families of graphs for which the entangled capacity exceeds the Shannon capacity.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Matrix Algebras and Semidefinite Programming Techniques for Codes

This PhD thesis is concerned with SDP bounds for codes: upper bounds for (non)-binary error correcting codes and lower bounds for (non)-binary covering codes. The methods are based on the method of Schrijver that uses triple distances in stead of pairs as in the classical Delsarte bound. The main topics discussed are: 1) Block-diagonalisation of matrix *-algebras, 2) Terwilliger-algebra of the nonbinary Hamming scheme (including an explicit block-diagonalisation), 3) SDP-bounds for (nonbinary) error-correcting codes and covering codes (including computational results), 4) Discussion on the relation with matrix-cuts, 5) Computational results for Affine caps.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Polyhedra with the Integer Caratheodory Property

A polyhedron P has the Integer Caratheodory Property if the following holds. For any positive integer k and any integer vector w in kP, there exist affinely independent integer vectors x_1,...,x_t in P and positive integers n_1,...,n_t such that n_1+...+n_t=k and w=n_1x_1+...+n_tx_t. In this paper we prove that if P is a (poly)matroid base polytope or if P is defined by a TU matrix, then P and projections of P satisfy the integer Caratheodory property.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

On a set-theoretic invariant

Let a_1,...,a_m be positive real numbers. Besser and Moree considered weighted numbers of -1,+1 solutions of the linear inequality |a_i-a_j| < e_ka_k < a_i+a_j, with e_k=-1 of 1 and k running over the integers 1,...,m with i and j skipped. They introduced some invariants and near invariants related to this situation (invariant meaning here: not depending on the choice of i and j). The main result of their paper is extended here to a much more general setting, namely that of certain maps from finite sets to {-1,1}. Some applications are given.

0 citations0 reviewsNo code linkedOpen access