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

Dirk Oliver Theis

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

ResearcherUnclaimed source record
math.CODiscrete Mathematicsmath.OCComputational Complexityquant-phComputationData Structures and AlgorithmsMachine Learning

Catalog footprint

What is connected

29works
8topics
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

29 published item(s)

preprint2022arXiv

Optimality of Finite-Support Parameter Shift Rules for Derivatives of Variational Quantum Circuits

Variational (or, parameterized) quantum circuits are quantum circuits that contain real-number parameters, that need to be optimized/"trained" in order to achieve the desired quantum-computational effect. For that training, analytic derivatives (as opposed to numerical derivation) are useful. Parameter shift rules have received attention as a way to obtain analytic derivatives, via statistical estimators. In this paper, using Fourier Analysis, we characterize the set of all shift rules that realize a given fixed partial derivative of a multi-parameter VQC. Then, using Convex Optimization, we show how the search for the shift rule with smallest standard deviation leads to a primal-dual pair of convex optimization problems. We study these optimization problems theoretically, prove a strong duality theorem, and use it to establish optimal dual solutions for several families of VQCs. This also proves optimality for some known shift rules and answers the odd open question. As a byproduct, we demonstrate how optimal shift rules can be found efficiently computationally, and how the known optimal dual solutions help with that.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Input Redundancy for Parameterized Quantum Circuits

The topic area of this paper parameterized quantum circuits (quantum neural networks) which are trained to estimate a given function, specifically the type of circuits proposed by Mitarai et al. (Phys. Rev. A, 2018). The input is encoded into amplitudes of states of qubits. The no-cloning principle of quantum mechanics suggests that there is an advantage in redundantly encoding the input value several times. We follow this suggestion and prove lower bounds on the number of redundant copies for two types of input encoding. We draw conclusions for the architecture design of QNNs.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

MAXENT3D_PID: An Estimator for the Maximum-entropy Trivariate Partial Information Decomposition

Chicharro (2017) introduced a procedure to determine multivariate partial information measures within the maximum entropy framework, separating unique, redundant, and synergistic components of information. Makkeh, Theis, and Vicente (2018) formulated the latter trivariate partial information measure as Cone Programming. In this paper, we present MAXENT3D_PID, a production-quality software that computes the trivariate partial information measure based on the Cone Programming model. We describe in detail our software, explain how to use it, and perform some experiments reflecting its accuracy in estimating the trivariate partial information decomposition.

0 citations0 reviewsNo code linkedOpen access
preprint2018arXiv

BROJA-2PID: A robust estimator for bivariate partial information decomposition

Makkeh, Theis, and Vicente found in [8] that Cone Programming model is the most robust to compute the Bertschinger et al. partial information decompostion (BROJA PID) measure [1]. We developed a production-quality robust software that computes the BROJA PID measure based on the Cone Programming model. In this paper, we prove the important property of strong duality for the Cone Program and prove an equivalence between the Cone Program and the original Convex problem. Then describe in detail our software and how to use it.\newline\indent

0 citations0 reviewsNo code linkedOpen access
preprint2017arXiv

Fooling Sets and the Spanning Tree Polytope

In the study of extensions of polytopes of combinatorial optimization problems, a notorious open question is that for the size of the smallest extended formulation of the Minimum Spanning Tree problem on a complete graph with $n$ nodes. The best known lower bound is $Ω(n^2)$, the best known upper bound is $O(n^3)$. In this note we show that the venerable fooling set method cannot be used to improve the lower bound: every fooling set for the Spanning Tree polytope has size $O(n^2)$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the Graph of the Pedigree Polytope

Pedigree polytopes are extensions of the classical Symmetric Traveling Salesman Problem polytopes whose graphs (1-skeletons) contain the TSP polytope graphs as spanning subgraphs. While deciding adjacency of vertices in TSP polytopes is coNP-complete, Arthanari has given a combinatorial (polynomially decidable) characterization of adjacency in Pedigree polytopes. Based on this characterization, we study the graphs of Pedigree polytopes asymptotically, for large numbers of cities. Unlike TSP polytope graphs, which are vertex transitive, Pedigree graphs are not even regular. Using an "adjacency game" to handle Arthanari's intricate inductive characterization of adjacency, we prove that the minimum degree is asymptotically equal to the number of vertices, i.e., the graph is "asymptotically almost complete".

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Short note on the number of 1-ascents in dispersed dyck paths

A dispersed Dyck path (DDP) of length n is a lattice path on $N\times N$ from (0,0) to (n,0) in which the following steps are allowed: "up" (x, y) $\to$ (x+1, y+1); "down" (x, y) $\to$ (x+1, y-1); and "right" (x,0) $\to$ (x+1,0). An ascent in a DDP is an inclusion-wise maximal sequence of consecutive up steps. A 1-ascent is an ascent consisting of exactly 1 up step. We give a closed formula for the total number of 1-ascents in all dispersed Dyck paths of length n, A191386 in Sloane's OEIS. Previously, only implicit generating function relations and asymptotics were known.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The (minimum) rank of typical fooling set matrices

A fooling-set matrix has nonzero diagonal, but at least one in every pair of diagonally opposite entries is 0. Dietzfelbinger et al. '96 proved that the rank of such a matrix is at least $\sqrt n$. It is known that the bound is tight (up to a multiplicative constant). We ask for the "typical" minimum rank of a fooling-set matrix: For a fooling-set zero-nonzero pattern chosen at random, is the minimum rank of a matrix with that zero-nonzero pattern over a field $\mathbb F$ closer to its lower bound $\sqrt{n}$ or to its upper bound $n$? We study random patterns with a given density $p$, and prove an $Ω(n)$ bound for the cases when: (a) $p$ tends to $0$ quickly enough, (b) $p$ tends to $0$ slowly, and $|\mathbb F|=O(1)$, (c) $p\in(0,1]$ is a constant. We have to leave open the case when $p\to 0$ slowly and $\mathbb F$ is a large or infinite field (e.g., $\mathbb F=GF(2^n)$, $F=\mathbb{R}$).

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Graph of the Pedigree Polytope is Asymptotically Almost Complete (Extended Abstract)

Graphs (1-skeletons) of Traveling-Salesman-related polytopes have attracted a lot of attention. Pedigree polytopes are extensions of the classical Symmetric Traveling Salesman Problem polytopes (Arthanari 2000) whose graphs contain the TSP polytope graphs as spanning subgraphs (Arthanari 2013). Unlike TSP polytopes, Pedigree polytopes are not "symmetric", e.g., their graphs are not vertex transitive, not even regular. We show that in the graph of the pedigree polytope, the quotient minimum degree over number of vertices tends to 1 as the number of cities tends to infinity.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Fooling sets and rank

An $n\times n$ matrix $M$ is called a \textit{fooling-set matrix of size $n$} if its diagonal entries are nonzero and $M_{k,\ell} M_{\ell,k} = 0$ for every $k\ne \ell$. Dietzfelbinger, Hromkovi{č}, and Schnitger (1996) showed that $n \le (\mbox{rk} M)^2$, regardless of over which field the rank is computed, and asked whether the exponent on $\mbox{rk} M$ can be improved. We settle this question. In characteristic zero, we construct an infinite family of rational fooling-set matrices with size $n = \binom{\mbox{rk} M+1}{2}$. In nonzero characteristic, we construct an infinite family of matrices with $n= (1+o(1))(\mbox{rk} M)^2$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

An algorithm for random signed 3-SAT with Intervals

In signed k-SAT problems, one fixes a set M and a set $\mathcal S$ of subsets of M, and is given a formula consisting of a disjunction of m clauses, each of which is a conjunction of k literals. Each literal is of the form "$x \in S$", where $S \in \mathcal S$, and x is one of n variables. For Interval-SAT (iSAT), M is an ordered set and $\mathcal S$ the set of intervals in M. We propose an algorithm for 3-iSAT, and analyze it on uniformly random formulas. The algorithm follows the Unit Clause paradigm, enhanced by a (very limited) backtracking option. Using Wormald's ODE method, we prove that, if $m/n \le 2.3$, with high probability, our algorithm succeeds in finding an assignment of values to the variables satisfying the formula.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Fooling-sets and rank in nonzero characteristic (extended abstract)

An n\times n matrix M is called a fooling-set matrix of size n, if its diagonal entries are nonzero, whereas for every k\ne \ell we have M_{k,\ell} M_{\ell,k} = 0. Dietzfelbinger, Hromkovič, and Schnitger (1996) showed that n \le (\rk M)^2, regardless of over which field the rank is computed, and asked whether the exponent on \rk M can be improved. We settle this question for nonzero characteristic by constructing a family of matrices for which the bound is asymptotically tight. The construction uses linear recurring sequences.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Support-based lower bounds for the positive semidefinite rank of a nonnegative matrix

The positive semidefinite rank of a nonnegative $(m\times n)$-matrix~$S$ is the minimum number~$q$ such that there exist positive semidefinite $(q\times q)$-matrices $A_1,\dots,A_m$, $B_1,\dots,B_n$ such that $S(k,\ell) = \mbox{tr}(A_k^* B_\ell)$. The most important, lower bound technique for nonnegative rank is solely based on the support of the matrix S, i.e., its zero/non-zero pattern. In this paper, we characterize the power of lower bounds on positive semidefinite rank based on solely on the support.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Combinatorial Bounds on Nonnegative Rank and Extended Formulations

An extended formulation of a polytope P is a polytope Q which can be projected onto P. Extended formulations of small size (i.e., number of facets) are of interest, as they allow to model corresponding optimization problems as linear programs of small sizes. The main known lower bounds on the minimum sizes of extended formulations for fixed polytope P (Yannakakis 1991) are closely related to the concept of nondeterministic communication complexity. We study the relative power and limitations of the bounds on several examples.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Compact Formulations of the Steiner Traveling Salesman Problem and Related Problems

The Steiner Traveling Salesman Problem (STSP) is a variant of the Traveling Salesman Problem (TSP) that is particularly suitable when dealing with sparse networks, such as road networks. The standard integer programming formulation of the STSP has an exponential number of constraints, just like the standard formulation of the TSP. On the other hand, there exist several known {\em compact} formulations of the TSP, i.e., formulations with a polynomial number of both variables and constraints. In this paper, we show that some of these compact formulations can be adapted to the STSP. We also briefly discuss the adaptation of our formulations to some closely-related problems.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Good edge-labelings and graphs with girth at least five

A good edge-labeling of a graph [Araújo, Cohen, Giroire, Havet, Discrete Appl. Math., forthcoming] is an assignment of numbers to the edges such that for no pair of vertices, there exist two non-decreasing paths. In this paper, we study edge-labeling on graphs with girth at least 5. In particular we verify, under this additional hypothesis, a conjecture by Araújo et al. This conjecture states that if the average degree of G is less than 3 and G is minimal without an edge-labeling, then G \in {C_3,K_{2,3}}. (For the case when the girth is 4, we give a counterexample.)

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Small Minors in Dense Graphs

A fundamental result in structural graph theory states that every graph with large average degree contains a large complete graph as a minor. We prove this result with the extra property that the minor is small with respect to the order of the whole graph. More precisely, we describe functions $f$ and $h$ such that every graph with $n$ vertices and average degree at least $f(t)$ contains a $K_t$-model with at most $h(t)\cdot\log n$ vertices. The logarithmic dependence on $n$ is best possible (for fixed $t$). In general, we prove that $f(t)\leq 2^{t-1}+\eps$. For $t\leq 4$, we determine the least value of $f(t)$; in particular $f(3)=2+\eps$ and $f(4)=4+\eps$. For $t\leq4$, we establish similar results for graphs embedded on surfaces, where the size of the $K_t$-model is bounded (for fixed $t$).

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Symmetry Matters for Sizes of Extended Formulations

In 1991, Yannakakis (J. Comput. System Sci., 1991) proved that no symmetric extended formulation for the matching polytope of the complete graph K_n with n nodes has a number of variables and constraints that is bounded subexponentially in n. Here, symmetric means that the formulation remains invariant under all permutations of the nodes of K_n. It was also conjectured in the paper mentioned above that "asymmetry does not help much," but no corresponding result for general extended formulations has been found so far. In this paper we show that for the polytopes associated with the matchings in K_n with log(n) (rounded down) edges there are non-symmetric extended formulations of polynomial size, while nevertheless no symmetric extended formulations of polynomial size exist. We furthermore prove similar statements for the polytopes associated with cycles of length log(n) (rounded down). Thus, with respect to the question for smallest possible extended formulations, in general symmetry requirements may matter a lot. Compared to the extended abtract that has appeared in the Proceedings of IPCO XIV at Lausanne, this paper does not only contain proofs that had been ommitted there, but it also presents slightly generalized and sharpened lower bounds.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A note on the Cops & Robber game on graphs embedded in non-orientable surfaces

The Cops and Robber game is played on undirected finite graphs. A number of cops and one robber are positioned on vertices and take turns in sliding along edges. The cops win if they can catch the robber. The minimum number of cops needed to win on a graph is called its cop number. It is known that the cop number of a graph embedded on a surface $X$ of genus $g$ is at most $3g/2 + 3$, if $X$ is orientable (Schroeder 2004), and at most $2g+1$, otherwise (Nowakowski & Schroeder 1997). We improve the bounds for non-orientable surfaces by reduction to the orientable case using covering spaces. As corollaries, using Schroeder's results, we obtain the following: the maximum cop number of graphs embeddable in the projective plane is 3; the cop number of graphs embeddable in the Klein Bottle is at most 4, and an upper bound is $3g/2 + 3/2$ for all other $g$.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

A note on the relationship between the Graphical Traveling Salesman Polyhedron, the Symmetric Traveling Salesman Polytope, and the Metric Cone

In this short communication, we observe that the Graphical Traveling Salesman Polyhedron is the intersection of the positive orthant with the Minkowski sum of the Symmetric Traveling Salesman Polytope and the polar of the metric cone. This follows almost trivially from known facts. There are two reasons why we find this observation worth communicating none-the-less: It is very surprising; it helps to understand the relationship between these two important families of polyhedra.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On a class of metrics related to graph layout problems

We examine the metrics that arise when a finite set of points is embedded in the real line, in such a way that the distance between each pair of points is at least 1. These metrics are closely related to some other known metrics in the literature, and also to a class of combinatorial optimization problems known as graph layout problems. We prove several results about the structure of these metrics. In particular, it is shown that their convex hull is not closed in general. We then show that certain linear inequalities define facets of the closure of the convex hull. Finally, we characterise the unbounded edges of the convex hull and of its closure.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On some lower bounds on the number of bicliques needed to cover a bipartite graph

The biclique covering number of a bipartite graph G is the minimum number of complete bipartite subgraphs (bicliques) whose union contains every edge of G. In this little note we compare three lower bounds on the biclique covering number: A bound jk(G) proposed by Jukna & Kulikov (Discrete Math. 2009); the well-known fooling set bound fool(G); the "tensor-power" fooling set bound fool^\infty(G). We show jk \le fool le fool^\infty \le min_Q (rk Q)^2, where the minimum is taken over all matrices with a certain zero/nonzero-pattern. Only the first inequality is really novel, the third one generalizes a result of Dietzfelbinger, Hromkovič, Schnitger (1994). We also give examples for which fool \ge (rk)^{log_4 6} improving on Dietzfelbinger et al.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

On the satisfiability of random regular signed SAT formulas

Regular signed SAT is a variant of the well-known satisfiability problem in which the variables can take values in a fixed set V \subset [0,1], and the `literals' have the form "x \le a" or "x \ge a". We answer some open question regarding random regular signed k-SAT formulas: the probability that a random formula is satisfiable increases with |V|; there is a constant upper bound on the ratio m/n of clauses m over variables n, beyond which a random formula is asypmtotically almost never satisfied; for k=2 and V=[0,1], there is a phase transition at m/n=2.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Random lifts of $K_5\setminus e$ are 3-colourable

Amit, Linial, and Matou\vsek (Random lifts of graphs III: independence and chromatic number, Random Struct. Algorithms, 2001) have raised the following question: Is the chromatic number of random $h$-lifts of $K_5$ asymptotically (for $h\to\infty$) almost surely equal to a single number? In this paper, we offer the following partial result: The chromatic number of a random lift of $K_5\setminus e$ is asymptotically almost surely three.

0 citations0 reviewsNo code linkedOpen access
preprint2008arXiv

The Cops & Robber game on series-parallel graphs

The Cops and Robber game is played on undirected finite graphs. $k$ cops and one robber are positioned on vertices and take turn in moving along edges. The cops win if, after a move, a cop and the robber are on the same vertex. A graph is called $k$-copwin, if the cops have a winning strategy. It is known that planar graphs are 3-copwin (Aigner & Fromme, 1984) and that outerplanar graphs are 2-copwin (Clarke, 2002). In this short note, we prove that series-parallel (i.e., graphs with no $K_4$ minor) graphs are 2-copwin. It is a well-known trick in the literature of cops & robber games to define variants of the game which impose restrictions on the possible strategies of the cops (see Clarke, 2002). For our proof, we define the ``cops & robber game with exits''. Our proof yields a winning strategy for the cops.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

Odd minimum cut sets and b-matchings revisited

The famous Padberg-Rao separation algorithm for b-matching polyhedra can be implemented to run in O(n^2m log(n^2/m)) time in the uncapacitated case, and in O(nm^2 log(n^2/m)) time in the capacitated case (where n is the number of vertices and m is the number of edges of the underlying graph). We give a new and simple algorithm for the capacitated case which can be implemented to run in O(n^2m log(n^2/m)) time.

0 citations0 reviewsNo code linkedOpen access