Search

info:eu-repo/semantics/published

info:eu-repo/semantics/published

info:eu-repo/semantics/published

info:eu-repo/semantics/published

info:eu-repo/semantics/published

info:eu-repo/semantics/published

info:eu-repo/semantics/published

info:eu-repo/semantics/published

info:eu-repo/semantics/published

info:eu-repo/semantics/published

info:eu-repo/semantics/published

info:eu-repo/semantics/published

We study the space reachable by rolling a 3D convex polyhedron on a 2D periodic tessellation in the xy-plane, where at every step a face of the polyhedron must coincide exactly with a tile of the tessellation it rests upon, and the polyhedron rotates around one of the incident edges of that face until the neighboring face hits the xy plane. If the whole plane can be reached by a sequence of such rolls, we call the polyhedron a plane roller for the given tessellation. We further classify polyhedra that reach a constant fraction of the plane, an infinite area but vanishing fraction of the plane, or a bounded area as hollow-plane rollers, band rollers, and bounded rollers respectively. We present a polynomial-time algorithm to determine the set of tiles in a given periodic tessellation reachable by a given polyhedron from a given starting position, which in particular determines the roller type of the polyhedron and tessellation. Using this algorithm, we compute the reachability for every regular-faced convex polyhedron on every regular-tiled (≤ 4)-uniform tessellation., SCOPUS: cp.p, info:eu-repo/semantics/published

info:eu-repo/semantics/inPress

info:eu-repo/semantics/published

Continuous-time quantum walks provide a natural framework to tackle the fundamental problem of finding a node among a set of marked nodes in a graph, known as spatial search. Whether spatial search by continuous-time quantum walk provides a quadratic advantage over classical random walks has been an outstanding problem. Thus far, this advantage is obtained only for specific graphs or when a single node of the underlying graph is marked. In this Letter, we provide a new continuous-time quantum walk search algorithm that completely resolves this: our algorithm can find a marked node in any graph with any number of marked nodes, in a time that is quadratically faster than classical random walks. The overall algorithm is quite simple, requiring time evolution of the quantum walk Hamiltonian followed by a projective measurement. A key component of our algorithm is a purely analogue procedure to perform operations on a state of the form e-tH2, SCOPUS: ar.j, info:eu-repo/semantics/published

Ils ont colonisé notre environnement. Les algorithmes numériques sont partout ou presque, dans les applications de nos smartphones, nos ordinateurs, nos objets connectés. Ils nous recommandent des séries, des films, des morceaux de musique, des articles de presse sur les réseaux sociaux. Les algorithmes sont aussi devenus des outils de différentes politiques publiques qui nous impactent au quotidien.Quelles sont les potentielles dérives du tout-à-l’algorithme ? Analyse croisée de deux chercheurs : Corentin Debailleul, doctorant en géographie à l’Université Libre de Bruxelles et Jérémy Grosman,doctorant en philosophie à l’Université de Namur., https://www.liguedh.be/etat-des-droits-humains-en-belgique-rapport-2021, info:eu-repo/semantics/published

The fragile complexity of a comparison-based algorithm is f(n) if each input element participates in O(f(n)) comparisons. In this paper, we explore the fragile complexity of algorithms adaptive to various restrictions on the input, i.e. algorithms with a fragile complexity parameterized by a quantity other than the input size n. We show that searching for the predecessor in a sorted array has fragile complexity Θ(logk), where k is the rank of the query element, both in a randomized and a deterministic setting. For predecessor searches, we also show how to optimally reduce the amortized fragile complexity of the elements in the array. We also prove the following results: Selecting the k-th smallest element has expected fragile complexity O(loglogk) for the element selected. Deterministically finding the minimum element has fragile complexity Θ(log(Inv)) and Θ(log(Runs)), where Inv is the number of inversions in a sequence and Runs is the number of increasing runs in a sequence. Deterministically finding the median has fragile complexity O(log(Runs)+loglogn) and Θ(log(Inv)). Deterministic sorting has fragile complexity Θ(log(Inv)) but it has fragile complexity Θ(logn) regardless of the number of runs., info:eu-repo/semantics/published

Afshani, Barbay and Chan (2017) introduced the notion of instance-optimal algorithm in the order-oblivious setting. An algorithm A is instance-optimal in the order-oblivious setting for a certain class of algorithms A* if the following hold:- A takes as input a sequence of objects from some domain;- for any instance σ and any algorithm A' in A*, the runtime of A on σ is at most a constant factor removed from the runtime of A' on the worst possible permutation of σ. If we identify permutations of a sequence as representing the same instance, this essentially states that A is optimal on every possible input (and not only in the worst case).We design instance-optimal algorithms for the problem of reporting, given a bichromatic set of points in the plane S, all pairs consisting of points of different color which span an empty axis-aligned rectangle (or reporting all points which appear in such a pair). This problem has applications for training-set reduction in nearest-neighbour classifiers. It is also related to the problem consisting of finding the decision boundaries of a euclidean nearest-neighbour classifier, for which Bremner et al. (2005) gave an optimal output-sensitive algorithm.By showing the existence of an instance-optimal algorithm in the order-oblivious setting for this problem we push the methods of Afshani et al. closer to their limits by adapting and extending them to a setting which exhibits highly non-local features. Previous problems for which instance-optimal algorithms were proven to exist were based solely on local relationships between points in a set., info:eu-repo/semantics/published

info:eu-repo/semantics/published

info:eu-repo/semantics/published

info:eu-repo/semantics/published

In this paper, we provide an effective characterization of all the subgame-perfect equilibria in infinite duration games played on finite graphs with mean-payoff objectives. To this end, we introduce the notion of requirement, and the notion of negotiation function. We establish that the plays that are supported by SPEs are exactly those that are consistent with the least fixed point of the negotiation function. Finally, we show that the negotiation function is piecewise linear, and can be analyzed using the linear algebraic tool box. As a corollary, we prove the decidability of the SPE constrained existence problem, whose status was left open in the literature., SCOPUS: cp.p, info:eu-repo/semantics/published

Node counting on a graph is subject to some fundamental theoretical limitations, yet a solution to such problems is necessary in many applications of graph theory to real-world systems, such as collective robotics and distributed sensor networks. Thus several stochastic and naïve deterministic algorithms for distributed graph size estimation or calculation have been provided. Here we present a deterministic and distributed algorithm that allows every node of a connected graph to determine the graph size in finite time, if an upper bound on the graph size is provided. The algorithm consists in the iterative aggregation of information in local hubs which then broadcast it throughout the whole graph. The proposed node-counting algorithm is on average more efficient in terms of node memory and communication cost than its previous deterministic counterpart for node counting, and appears comparable or more efficient in terms of average-case time complexity. As well as node counting, the algorithm is more broadly applicable to problems such as summation over graphs, quorum sensing, and spontaneous hierarchy creation., SCOPUS: ar.j, info:eu-repo/semantics/published

info:eu-repo/semantics/published

info:eu-repo/semantics/published

The modular subset sum problem consists of deciding, given a modulus m, a multiset S of n integers in 0.m – 1, and a target integer t, whether there exists a subset of S with elements summing to t (mod m), and to report such a set if it exists. We give a simple O(m log m)-time with high probability (w.h.p.) algorithm for the modular subset sum problem. This builds on and improves on a previous O(m log7 m) w.h.p. algorithm from Axiotis, Backurs, Jin, Tzamos, and Wu (SODA 19). Our method utilizes the ADT of the dynamic strings structure of Gawrychowski et al. (SODA 18). However, as this structure is rather complicated we present a much simpler alternative which we call the Data Dependent Tree. As an application, we consider the computational version of a fundamental theorem in zero-sum Ramsey theory. The Erdős-Ginzburg-Ziv Theorem states that a multiset of 2n – 1 integers always contains a subset of cardinality exactly n whose values sum to a multiple of n. We give an algorithm for finding such a subset in time O(n log n) w.h.p. which improves on an O(n2) algorithm due to Del Lungo, Marini, and Mori (Disc. Math. 09)., info:eu-repo/semantics/published

info:eu-repo/semantics/inPress

We present fully dynamic approximation algorithms for the Maximum Independent Set problem on several types of geometric objects: intervals on the real line, arbitrary axis-aligned squares in the plane and axis-aligned d-dimensional hypercubes.It is known that a maximum independent set of a collection of n intervals can be found in O(nlogn) time, while it is already \textsf{NP}-hard for a set of unit squares. Moreover, the problem is inapproximable on many important graph families, but admits a \textsf{PTAS} for a set of arbitrary pseudo-disks. Therefore, a fundamental question in computational geometry is whether it is possible to maintain an approximate maximum independent set in a set of dynamic geometric objects, in truly sublinear time per insertion or deletion. In this work, we answer this question in the affirmative for intervals, squares and hypercubes.First, we show that for intervals a (1+ε)-approximate maximum independent set can be maintained with logarithmic worst-case update time. This is achieved by maintaining a locally optimal solution using a constant number of constant-size exchanges per update.We then show how our interval structure can be used to design a data structure for maintaining an expected constant factor approximate maximum independent set of axis-aligned squares in the plane, with polylogarithmic amortized update time. Our approach generalizes to d-dimensional hypercubes, providing a O(4d)-approximation with polylogarithmic update time.Those are the first approximation algorithms for any set of dynamic arbitrary size geometric objects; previous results required bounded size ratios to obtain polylogarithmic update time. Furthermore, it is known that our results for squares (and hypercubes) cannot be improved to a (1+ε)-approximation with the same update time., info:eu-repo/semantics/published

A data structure is presented that explicitly maintains the graph of a Voronoi diagram of N point sites in the plane or the dual graph of a convex hull of points in three dimensions while allowing insertions of new sites/points. Our structure supports insertions in O~(N3/4) expected amortized time, where O~ suppresses polylogarithmic terms. This is the first result to achieve sublinear time insertions; previously it was shown by Allen et al. that Θ(N−−√) amortized combinatorial changes per insertion could occur in the Voronoi diagram but a sublinear-time algorithm was only presented for the special case of points in convex position., info:eu-repo/semantics/published

IPSJ Outstanding Paper Award 2020 Candidate., info:eu-repo/semantics/published

info:eu-repo/semantics/published

The modular subset sum problem consists of deciding, given a modulus m, a multiset S of n integers in 0.m−1, and a target integer t, whether there exists a subset of S with elements summing to tmodm, and to report such a set if it exists. We give a simple O(mlogm)-time with high probability (w.h.p.) algorithm for the modular subset sum problem. This builds on and improves on a previous O(mlog7m) w.h.p. algorithm from Axiotis, Backurs, Jin, Tzamos, and Wu (SODA 19). Our method utilizes the ADT of the dynamic strings structure of Gawrychowski et al. (SODA~18). However, as this structure is rather complicated we present a much simpler alternative which we call the Data Dependent Tree. As an application, we consider the computational version of a fundamental theorem in zero-sum Ramsey theory. The Erdős-Ginzburg-Ziv Theorem states that a multiset of 2n−1 integers always contains a subset of cardinality exactly n whose values sum to a multiple of n. We give an algorithm for finding such a subset in time O(nlogn) w.h.p. which improves on an O(n2) algorithm due to Del Lungo, Marini, and Mori (Disc. Math. 09)., info:eu-repo/semantics/published

Let P and Q be finite point sets of the same cardinality in R2, each labelled from 1 to n. Two noncrossing geometric graphs GP and GQ spanning P and Q, respectively, are called compatible if for every face f in GP, there exists a corresponding face in GQ with the same clockwise ordering of the vertices on its boundary as in f. In particular, GP and GQ must be straight-line embeddings of the same connected n-vertex graph.Deciding whether two labelled point sets admit compatible geometric paths is known to be NP-complete. We give polynomial-time algorithms to find compatible paths or report that none exist in three scenarios: O(n) time for points in convex position; O(n2) time for two simple polygons, where the paths are restricted to remain inside the closed polygons; and O(n2logn) time for points in general position if the paths are restricted to be monotone., info:eu-repo/semantics/published

info:eu-repo/semantics/published

We consider the design of adaptive data structures for searching elements of a tree-structured space.We use a natural generalization of the rotation-based online binary search tree model in which the underlying search space is the set of vertices of a tree. This model is based on a simple structure for decomposing graphs, previously known under several names including elimination trees, vertex rankings, and tubings.The model is equivalent to the classical binary search tree model exactly when the underlying tree is a path.We describe an online $O(log log n)$-competitive search tree data structure in this model, matching thebest known competitive ratio of binary search trees.Our method is inspired by Tango trees, an online binary search tree algorithm, but critically needs several new notions including one which we call Steiner-closed search trees, which may be of independent interest. Moreover our technique is based on a novel use of two levels of decomposition, first from search space to a set of Steiner-closed trees, and secondly from these trees into paths., info:eu-repo/semantics/published

info:eu-repo/semantics/published

One of the most important algorithmic applications of quantum walks is to solve spatial search problems. A widely used quantum algorithm for this problem, introduced by Childs and Goldstone [Phys. Rev. A 70, 022314 (2004)PLRAAN1050-294710.1103/PhysRevA.70.022314], finds a marked node on a graph of n nodes via a continuous-time quantum walk. This algorithm is said to be optimal if it can find any of the nodes in O(n) time. However, given a graph, no general conditions for the optimality of the algorithm are known and previous works demonstrating optimal quantum search for certain graphs required an instance-specific analysis. In fact, the demonstration of the necessary and sufficient conditions that a graph must fulfill for quantum search to be optimal has been a long-standing open problem. In this work we make significant progress towards solving this problem. We derive general expressions, depending on the spectral properties of the Hamiltonian driving the walk, that predict the performance of this quantum search algorithm provided certain spectral conditions are fulfilled. Our predictions are valid, for example, for (normalized) Hamiltonians whose spectral gap is considerably larger than n-1/2. This allows us to derive necessary and sufficient conditions for optimal quantum search in this regime, as well as provide examples of graphs where quantum search is suboptimal. In addition, by extending this analysis, we are also able to show the optimality of quantum search for certain graphs with very small spectral gaps, such as graphs that can be efficiently partitioned into clusters. Our results imply that, to the best of our knowledge, all prior results analytically demonstrating the optimality of this algorithm for specific graphs can be recovered from our general results., SCOPUS: ar.j, info:eu-repo/semantics/published

The fundamental problem of sampling from the limiting distribution of quantum walks on networks, known as mixing, finds widespread applications in several areas of quantum information and computation. Of particular interest in most of these applications is the minimum time beyond which the instantaneous probability distribution of the quantum walk remains close to this limiting distribution, known as the "quantum mixing time". However, this quantity is only known for a handful of specific networks. In this Letter, we prove an upper bound on the quantum mixing time for almost all networks, i.e. the fraction of networks for which our bound holds, goes to one in the asymptotic limit. To this end, using several results in random matrix theory, we find the quantum mixing time of Erdös-Renyi random networks: networks of n nodes where each edge exists with probability p independently. For example, for dense random networks, where p is a constant, we show that the quantum mixing time is O(n3/2+o(1)). In addition to opening avenues for the analytical study of quantum dynamics on random networks, our work could find applications beyond quantum information processing. Owing to the universality of Wigner random matrices, our results on the spectral properties of random graphs hold for general classes of random matrices that are ubiquitous in several areas of physics. In particular, our results could lead to novel insights into the equilibration times of isolated quantum systems defined by random Hamiltonians, a foundational problem in quantum statistical mechanics., SCOPUS: ar.j, info:eu-repo/semantics/published

The problem of sampling from the stationary distribution of a Markov chain finds widespread applications in a variety of fields. The time required for a Markov chain to converge to its stationary distribution is known as the classical mixing time. In this article, we deal with analog quantum algorithms for mixing. First, we provide an analog quantum algorithm that, given a Markov chain, allows us to sample from its stationary distribution in a time that scales as the sum of the square root of the classical mixing time and the square root of the classical hitting time. Our algorithm makes use of the framework of interpolated quantum walks and relies on Hamiltonian evolution in conjunction with von Neumann measurements. There also exists a different notion for quantum mixing: the problem of sampling from the limiting distribution of quantum walks, defined in a time-averaged sense. In this scenario, the quantum mixing time is defined as the time required to sample from a distribution that is close to this limiting distribution. Recently, we provided an upper bound on the quantum mixing time for Erdos-Rényi random graphs [Phys. Rev. Lett. 124, 050501 (2020)PRLTAO0031-900710.1103/PhysRevLett.124.050501]. Here, we also extend and expand upon our findings therein. Namely, we provide an intuitive understanding of the state-of-the-art random matrix theory tools used to derive our results. In particular, for our analysis we require information about macroscopic, mesoscopic, and microscopic statistics of eigenvalues of random matrices which we highlight here. Furthermore, we provide numerical simulations that corroborate our analytical findings and extend this notion of mixing from simple graphs to any ergodic, reversible, Markov chain., SCOPUS: ar.j, info:eu-repo/semantics/published

Spatial search by a discrete-time quantum walk can find a marked node on any ergodic, reversible Markov chain P quadratically faster than its classical counterpart, i.e. in a time that is in the square root of the hitting time of P. However, in the framework of continuous-time quantum walks, it was previously unknown whether such general speedup is possible. In fact, in this framework, the widely used quantum algorithm by Childs and Goldstone fails to achieve such a speedup. Furthermore, it is not clear how to apply this algorithm for searching any Markov chain P. In this article we aim to reconcile the apparent differences between the running times of spatial search algorithms in these two frameworks. We first present a modified version of the Childs and Goldstone algorithm which can search for a marked element for any ergodic, reversible P by performing a quantum walk on its edges. Although this approach improves the algorithmic running time for several instances, it cannot provide a generic quadratic speedup for any P. Second, using the framework of interpolated Markov chains, we provide a spatial search algorithm by a continuous-time quantum walk which can find a marked node on any P in the square root of the classical hitting time. In the scenario where multiple nodes are marked, the algorithmic running time scales as the square root of a quantity known as the extended hitting time. Our results establish a connection between discrete-time and continuous-time quantum walks and can be used to develop a number of Markov chain-based quantum algorithms., SCOPUS: ar.j, info:eu-repo/semantics/published

info:eu-repo/semantics/inPress