waashk/dblp huggingface dataset:
tiling groups for wang tiles. we apply tiling groups and height functions to tilings of regions in the plane by wang tiles, which are squares with colored boundaries where the colors of shared edges must match. we define a set of tiles as unambiguous if it contains all tiles equivalent to the identity in its tiling group. for all but one set of unambiguous tiles with two colors, we give efficient algorithms that tell whether a given region with colored boundary is tileable, show how to sample random tilings, and how to calculate the number of local moves or "flips" required to transform one tiling into another. we also analyze the lattice structure of the set of tilings, and study several examples with three and four colors as well.
generic quantum fourier transforms. the quantum fourier transform (qft) is the principal ingredient of most efficient quantum algorithms. we present a generic framework for the construction of efficient quantum circuits for the qft by "quantizing" the highly successful separation of variables technique for the construction of efficient classical fourier transforms. specifically, we use bratteli diagrams, gel'fand-tsetlin bases, and strong generating sets of small adapted diameter to provide efficient quantum circuits for the qft over a wide variety of finite abelian and non-abelian groups, including all group families for which efficient qfts are currently known and many new group families. moreover, our method provides the first subexponential-size quantum circuits for the qft over the linear groups glk(q), slk(q), and the finite groups of lie type, for any fixed prime power q.
the power of basis selection in fourier sampling: hidden subgroup problems in affine groups. many quantum algorithms, including shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which a unknown subgroup h of a group g must be determined from a quantum state &psi; over g that is uniformly supported on a left coset of h. these hidden subgroup problems are typically solved by fourier sampling: the quantum fourier transform of &psi; is computed and measured. when the underlying group is nonabelian, two important variants of the fourier sampling paradigm have been identified: the weak standard method, where only representation names are measured, and the strong standard method, where full measurement (i.e., the row and column of the representation as well as its name) occurs. it has remained open whether the strong method is indeed stronger, that is, whether there are hidden subgroups that can be reconstructed via the strong method but not by the weak, or any other known, method.in this article, we settle this question in the affirmative. we show that hidden subgroups of semidirect products of the form ℤq &times; ℤp, where q | (p - 1) and q = p/polylog(p), can be efficiently determined by the strong standard method. furthermore, the weak standard method and the "forgetful" abelian method are insufficient for these groups so that, in fact, it appears that use of the corresponding nonabelian representation theory is crucial. we extend this to an informationtheoretic solution for the hidden subgroup problem over the groups ℤq &times; ℤp where q | (p - 1) and, in particular, the affine groups ap. finally, we prove a simple closure property for the class of groups over which the hidden subgroup problem can be solved efficiently.
load balancing requires omega(log) expected time. in order to obtain very fast parallel algorithms, it is almost always necessary to have some sort of load balancing procedure, so that processors which have finished their required tasks can help processors which have not. if the overloaded processors are not helped, then the expected time of the entire algorithm suffers. in general, we would like to distribute the remaining work as evenly as possible among the processors, or more formally, given at most n independent tasks distributed in an arbitrary way among n processors, we would like to redistribute the tasks so that each processor contains o(1) tasks. we show here that even on the strongest randomized crcw pram model, for a simple random distribution tasks load balancing requires &ohgr;(log* n) expected time. gil, matias, and vishkin [9] give an o(log* n) expected time randomized algorithm which solves the load balancing problem in the worst case, so the lower bound is tight. by reduction we show that both padded sort [12], and linear approximate compaction [13] require &ohgr;(log* n) expected time. we note that our basic technique is one of the few parallel lower bound techniques known which only require 0/1 inputs. we also note that the bounds given in this paper do not place any restriction on the instruction set of the machine, the amount of information which can be stored in a memory cell, or on the number of memory cells.
fully-dynamic two dimensional orthogonal range and line segment intersection reporting in logarithmic time. we consider the two dimensional fully-dynamic orthogonal range reporting problem and the two dimensional fully-dynamic orthogonal line segment intersection reporting problem in the comparison model. we show that if n is the number of stored elements, then these problems can be solved in worst case time &theta;(log n) plus time proportional to the size of the output pr. operation.
trade-offs on the location of the core node in a network. the selection of a core node in a network is a crucial step in the set-up of several multimedia applications such as videoconferences or multi-player games. for a given group of application users, a poorly chosen location can lead to a waste of bandwidth or to long communication delays. since this kind of application usually involves unicast and multicast communications at the same time, we are naturally interested in a core location such that both the sum of the unicast path lengths to the users and the cost of the multicast tree spanning the users and the core are simultaneously small. while optimizing the first criterion is equivalent to finding a 1-median of the users, the second criterion corresponds to the minimum cost steiner tree problem.the goal of this paper is to show that there always exists a core location for which both criteria are close to their optimum. more precisely, we give a continuum of results which proves in particular that both criteria can simultaneously be within 1.37 times their optimum. finally we apply our results to the problem of minimizing a weighted sum of the criteria and we give an easy and fast heuristic with a small approximation ratio.
testing hierarchical systems. we investigate the testing of hierarchical (modular) systems, in which individual modules are modeled by finite state machines. given a hierarchical system, we are interested in finding a small set of tests that exercises all the transitions of the system. we present tight approximation algorithms and hardness results for the problem. our techniques extend to other criteria and metrics.
quantum algorithms for the triangle problem. we present two new quantum algorithms that either find a triangle (a copy of $k_{3}$) in an undirected graph $g$ on $n$ nodes, or reject if $g$ is triangle free. the first algorithm uses combinatorial ideas with grover search and makes $\tilde{o}(n^{10/7})$ queries. the second algorithm uses $\tilde{o}(n^{13/10})$ queries and is based on a design concept of ambainis [in proceedings of the $45$th ieee symposium on foundations of computer science, 2004, pp. 22-31] that incorporates the benefits of quantum walks into grover search [l. grover, in proceedings of the twenty-eighth acm symposium on theory of computing, 1996, pp. 212-219]. the first algorithm uses only $o(\log n)$ qubits in its quantum subroutines, whereas the second one uses $o(n)$ qubits. the triangle problem was first treated in [h. buhrman et al., siam j. comput., 34 (2005), pp. 1324-1330], where an algorithm with $o(n+\sqrt{nm})$ query complexity was presented, where $m$ is the number of edges of $g$.
caching queues in memory buffers. motivated by the need for maintaining multiple, large queues of data in modern high-performance systems, we study the problem of caching queues in memory under the following simple, but widely applicable, model. at each clock-tick, any number of data items may enter the various queues, while data-items are consumed from the heads of the queues. since the number of unconsumed items may exceed memory buffer size, some items in the queues need to be spilled to secondary storage and later moved back into memory for consumption. we provide online queue-caching algorithms under a number of interesting cost models.
i/o-efficient algorithms for graphs of bounded treewidth. we present i/o-efficient algorithms for the single source shortest path problem and np-hard problems on graphs of bounded treewidth. the main step in these algorithms is a method to compute a tree-decomposition for the given graph i/o-efficiently.
a practical approximation algorithm for the lms line estimator. the problem of fitting a straight line to a finite collection of points in the plane is an important problem in statistical estimation. robust estimators are widely used because of their lack of sensitivity to outlying data points. the least median-of-squares (lms) regression line estimator is among the best known robust estimators. given a set of n points in the plane, it is defined to be the line that minimizes the median squared residual or, more generally, the line that minimizes the residual of any given quantile q, where 0=0, and a quantile approximation, which approximates the fraction of points that lie within the strip to within a given error bound @e"q>=0. we present two randomized approximation algorithms for the lms line estimator. the first is a conceptually simple quantile approximation algorithm, which given fixed q and @e"q>0 runs in o(nlogn) time. the second is a practical algorithm, which can solve both types of approximation problems or be used as an exact algorithm. we prove that when used as a quantile approximation, this algorithm's expected running time is o(nlog^2n). we present empirical evidence that the latter algorithm is quite efficient for a wide variety of input distributions, even when used as an exact algorithm.
i/o-optimal algorithms for planar graphs using separators. we present i/o-optimal algorithms for several fundamental problems on planar graphs. our main contribution is an i/o-efficient algorithm for computing a small vertex separator of an unweighted planar graph. this algorithm is superior to all existing external memory algorithms for this problem, as it requires neither a breadth-first search tree nor an embedding of the graph as part of the input. in fact, we derive i/o-optimal algorithms for planar embedding, breadth-first search, depth-first search, single source shortest paths, and computing weighted separators of planar graphs from our unweighted separator algorithm.
colored tutte polynomials and kaufman brackets for graphs of bounded tree width. tutte polynomials are important graph invariants with rich applications in combinatorics, topology, knot theory, coding theory and even physics. the tutte polynomial t(g, x, y) is a polynomial in z[x, y] which depends on a graph g. computing the coefficients of t(g, x, y), and even evaluating t(g, x, y) at specific points (x, y) is #p hard by a result of jaeger et al. (math. proc. cambridge philos. soc. 108 (1989) 35). on the other hand, andrzejak (discrete math. 190 (1998) 39-54) and noble (combin. probab. comput. 7 (1998) 307-321) have shown independently, that, if g is a graph of bounded tree width, computing t(g, x, y) can be done in polynomial time. we extend this result to the signed tutte polynomials introduced in 1989 by kauffman and the colored tutte polynomials introduced in 1999 by bollobas and riordan. this allows us to prove similar results for the jones polynomials and kauffman brackets for knots and links which have a signed graph presentation of bounded tree width. jones polynomials and kauffman polynomials are the most prominent invariants of knot theory. for alternating links, they are easily computable from the tutte polynomials of the signed graph representing the link by a result of thistlethwaite (1988). for general links one has to use the colored tutte polynomial instead. knots and links can be presented as labeled planar graphs. the tree width of a link l is defined as the tree width of its graphical presentation d(l) as crossing diagrams. we show that for (not necessarily alternating) knots and links of tree width at most k, even the kauffman square bracket [l] introduced by bollobas and riordan can be computed in polynomial time. hence, the classical kauffman bracket (l) and the jones polynomial of links of tree width at most k are computable in polynomial time. our proof is based on, but extends considerably previous work by b. courcelle, u. rotics and the author. it also gives a new proof of the result for tutte polynomials and generalizes to a wide class of polynomials defined as generating functions definable in monadic second order logic with order, but invariant under it.
deterministic skip lists. we explore techniques based on the notion of a skip list to guarantee logarithmic search, insert and delete costs. the basic idea is to insist that between any pair of elements above a given height are a small number of elements of precisely that height. the desired behaviour can be achieved by either using some extra space for pointers, or by adding the constraint that the physical sizes of the nodes be exponentially increasing. the first approach leads to simpler code, whereas the second is ideally suited to a buddy system of memory allocation. our techniques are competitive in terms of time and space with balanced tree schemes, and, we feel, inherently simpler when taken from first principles.
a new look at survey propagation and its generalizations. we study the survey propagation algorithm [19, 5, 4], which is an iterative technique that appears to be very effective in solving random k-sat problems even with densities close to threshold. we first describe how any sat formula can be associated with a novel family of markov random fields (mrfs), parameterized by a real number &rho;. we then show that applying belief propagation---a well-known "message-passing technique---to this family of mrfs recovers various algorithms, ranging from pure survey propagation at one extreme (&rho; = 1) to standard belief propagation on the uniform distribution over sat assignments at the other extreme (&rho; = 0). configurations in these mrfs have a natural interpretation as generalized satisfiability assignments, on which a partial order can be defined. we isolate cores as minimal elements in this partial ordering, and prove that any core is a fixed point of survey propagation. we investigate the associated lattice structure, and prove a weight-preserving identity that shows how any mrf with p > 0 can be viewed as a "smoothed" version of the naive factor graph representation of the k-sat problem (p = 0). our experimental results show that message-passing on our family of mrfs is most effective for values of &rho; &ne; 1 (i.e., distinct from survey propagation); moreover, they suggest that random formulas may not typically possess non-trivial cores. finally, we isolate properties of gibbs sampling and message-passing algorithms that are typical for an ensemble of k-sat problems. we prove that the space of cores for random formulas is highly disconnected, and show that for values of p sufficiently close to one, either the associated mrf is highly concentrated around the all-star assignment, or it has exponentially small conductance. similarly, we prove that for p sufficiently close to one, the all-star assignment is attractive for message-passing when analyzed in the density-evolution setting.
representing dynamic binary trees succinctly. we introduce a new updatable representation of binary trees. the structure requires the information theoretic minimum 2n + &ogr;(n) bits and supports basic navigational operations in constant time and subtree size in &ogr;(lg n). in contrast to the linear update costs of previously proposed succinct representations, our representation supports updates in &ogr;(lg2 n) amortized time.
an analysis of the burrows-wheeler transform. the burrows-wheeler transform (also known as block-sorting) is at the base of compression algorithms which are the state of the art in lossless data compression. in this paper we analyze two algorithms which use this technique. the first one is the original algorithm described by burrows and wheeler, which, despite its simplicity, outperforms the gzip compressor. the second one uses an additional run-length encoding step to improve compression. we prove that the compression ratio of both algorithms can be bounded in terms of the k-th order empirical entropy of the input string for any k<0. we make no assumptions on the input and we obtain bounds which hold in the worst case, that is, for every possible input string. all previous results for block-sorting algorithms were concerned with the average compression ratio and have been established assuming that the input comes from a finite-order markov source.
fast distributed graph coloring with o(delta) colors. we consider the problem of deterministic distributed coloring of an n-vertex graph with maximum degree &dgr;, assuming that every vertex knows a priori only its own label and parameters n and &dgr;. the aim is to get a fast algorithm using few colors. linial [17] showed a vertex-coloring algorithm working in time &ogr;(log* n) and using &ogr;(&dgr;2 colors. we improve both the time and the number of colors simultaneously by showing an algorithm working in time &ogr;(log*(n/&dgr;)) and using &ogr;(&dgr;) colors. this is the first known &ogr;(&dgr;)-vertex-coloring distributed algorithm which can work faster than in polylogarithmic time. our method also gives an edge-coloring algorithm with the number of colors and time as above. on the other hand, it follows from linial [17] that our time of &ogr;(&dgr;)-coloring cannot be improved in general. in addition we show how our method gives fast coloring algorithms in communication models weaker than linial's.
fast mixing for independent sets, colorings and other models on trees. we study the mixing time of the glauber dynamics for general spin systems on bounded-degree trees, including the ising model, the hard-core model (independent sets) and the antiferromagnetic potts model at zero temperature (colorings). we generalize a framework, developed in our recent paper [18] in the context of the ising model, for establishing mixing time o(n log n), which ties this property closely to phase transitions in the underlying model. we use this framework to obtain rapid mixing results for several models over a significantly wider range of parameter values than previously known, including situations in which the mixing time is strongly dependent on the boundary condition.
efficient algorithms for document retrieval problems. we are given a collection d of text documents d1,&hellip;,dk, with &sum;i = n, which may be preprocessed. in the document listing problem, we are given an online query comprising of a pattern string p of length m and our goal is to return the set of all documents that contain one or more copies of p. in the closely related occurrence listing problem, we output the set of all positions within the documents where pattern p occurs. in 1973, weiner [24] presented an algorithm with o(n) time and space preprocessing following which the occurrence listing problem can be solved in time o(m + output) where output is the number of positions where p occurs; this algorithm is clearly optimal. in contrast, no optimal algorithm is known for the closely related document listing problem, which is perhaps more natural and certainly well-motivated.we provide the first known optimal algorithm for the document listing problem. more generally, we initiate the study of pattern matching problems that require retrieving documents matched by the patterns; this contrasts with pattern matching problems that have been studied more frequently, namely, those that involve retrieving all occurrences of patterns. we consider document retrieval problems that are motivated by online query processing in databases, information retrieval systems and computational biology. we present very efficient (optimal) algorithms for our document retrieval problems. our approach for solving such problems involve performing "local" encodings whereby they are reduced to range query problems on geometric objects --- points and lines --- that have color. we present improved algorithms for these colored range query problems that arise in our reductions using the structural properties of strings. this approach is quite general and yields simple, efficient, implementable algorithms for all the document retrieval problems in this paper.
adaptive sampling for quickselect. quickselect with median-of-3 is largely used in practice and its behavior is fairly well understood. however, the following natural adaptive variant, which we call proportion-from-3, had not been previously analyzed: choose as pivot the smallest of the sample if the rank of the sought element is small, the largest if the rank is large, and the median if the rank is medium". we first analyze proportion-from-2 and then proportion-from3. we also analyze &nu;-find, a generalization of proportion-from-3 with interval breakpoints at &nu; and 1 -- &nu;. we show that there exists an optimal value of &nu; and we also provide the range of values of &nu; where &nu;-find outperforms median-of-3. our results atrongly suggest that a suitable implementation of this variant could be the method of choice in a practical setting. finally, we also show that proportion-from-s and similar strategies are optimal when s &rarr; &infin;
data streams: algorithms and applications. in the data stream scenario, input arrives very rapidly and there is limited memory to store the input. algorithms have to work with one or few passes over the data, space less than linear in the input size or time significantly less than the input size. in the past few years, a new theory has emerged for reasoning about algorithms that work within these constraints on space, time, and number of passes. some of the methods rely on metric embeddings, pseudo-random computations, sparse approximation theory and communication complexity. the applications for this scenario include ip network traffic analysis, mining text message streams and processing massive data sets in general. researchers in theoretical computer science, databases, ip networking and computer systems are working on the data stream challenges. this article is an overview and survey of data stream algorithmics and is an updated version of [1].
percolation theory and computing with faulty arrays of processors. let h be an n x n mesh-connected array of processors. each processor is assumed to fail (independently) with probability p. raghavan [5] gave an algorithm that with high probability routes packets in this mesh with o(log n) dilation and o(log2n) load so long as p &le; 0.29. kklmrrtt [3] improve the load to o(1) for &ldquo;small&rdquo; p while keeping the o(log n) bound for dilation and showing an o(1) bound for congestion. in this paper we show these bounds hold for p as high as *** 0.4. we also consider the problem where links rather than processors fail and shows these same bounds hold for q < 1/2. in both cases these bounds are tight: for greater probabilities of failure the above embedding bounds cannot be achieved. this short cutoff follows from a zero-one result of percolation theory.