waashk/dblp huggingface dataset:
quantum algorithms for simon's problem over general groups. daniel simon's 1994 discovery of an efficient quantum algorithm for solving the hidden subgroup problem (hsp) over zn2 provided one of the first algebraic problems for which quantum computers are exponentially faster than their classical counterparts. in this paper, we study the generalization of simon's problem to arbitrary groups. fixing a finite group g, this is the problem of recovering an involution m = (m1,...,mn) &epsilon; gn from an oracle f with the property that f(x) = f(x &middot; y) ⇔ y &epsilon; {1, m}. in the current parlance, this is the hidden subgroup problem (hsp) over groups of the form gn, where g is a nonabelian group of constant size, and where the hidden subgroup is either trivial or has order two. although groups of the form gn have a simple product structure, they share important representation-theoretic properties with the symmetric groups sn, where a solution to the hsp would yield a quantum algorithm for graph isomorphism. in particular, solving their hsp with the so-called "standard method" requires highly entangled measurements on the tensor product of many coset states. here we give quantum algorithms with time complexity 2o(&radic;n log n) that recover hidden involutions m = (m1,..., mn) &epsilon; gn where, as in simon's problem, each mi is either the identity or the conjugate of a known element m and there is a character x of g for which x(m) = - x(1). our approach combines the general idea behind kuperberg's sieve for dihedral groups with the "missing harmonic" approach of moore and russell. these are the first nontrivial hidden subgroup algorithms for group families that require highly entangled multiregister fourier sampling.
a simple storage scheme for strings achieving entropy bounds. we propose a storage scheme for a string s[1, n], drawn from an alphabet &sigma;, that requires space close to the &kappa;-th order empirical entropy of s, and allows to retrieve any l-long substring of s in optimal o(1+l/log|&sum;|n) time. this matches the best known bounds [14, 7], via the use of binary encodings and tables only. we also apply this storage scheme to prove new time vs space trade-offs for compressed self-indexes [5, 12] and the burrows-wheeler transform [2].
quantum algorithm for a generalized hidden shift problem. consider the following generalized hidden shift problem: given a function f on {0,..., m - 1} x zn promised to be injective for fixed b and satisfying f(b, x) = f(b + 1,x + s) for b = 0, 1,..., m - 2, find the unknown shift s &epsilon; zn. for m = n, this problem is an instance of the abelian hidden subgroup problem, which can be solved efficiently on a quantum computer, whereas for m = 2, it is equivalent to the dihedral hidden subgroup problem, for which no efficient algorithm is known. for any fixed positive &epsilon;, we give an efficient (i.e., poly(log n)) quantum algorithm for this problem provided m &ge; n&epsilon;. the algorithm is based on the "pretty good measurement" and uses h. lenstra's (classical) algorithm for integer programming as a subroutine.
counting colors in boxes. let p be a set of n points in rd, so that each point is colored by one of c given colors. we present algorithms for preprocessing p into a data structure that efficiently supports queries of the form: given an axis-parallel box q, count the number of distinct colors of the points of p &cap; q. we present a general and relatively simple solution that has polylogarithmic query time and worst-case storage about o(nd). it is based on several interesting structural properties of the problem that we derive. we also show that for random inputs, the data structure requires almost linear expected storage. we then present several techniques for achieving space-time tradeoff. in r2, the most efficient solution uses fast matrix multiplication in the preprocessing stage. in higher dimensions we obtain a tradeoff using simpler mechanisms. we give a reduction from matrix multiplication to the offline version of problem, which shows that in r2 our time-space tradeoffs are close to optimal in the sense that improving them substantially would improve the best exponent of matrix multiplication. finally, we present a generalized matrix multiplication problem and show its intimate relation to counting colors in boxes in any dimension.
designing and learning optimal finite support auctions. a classical paper of myerson [18] shows how to construct an optimal (revenue-maximizing) auction in a model where bidders' values are drawn from known continuous distributions. in this paper we show how to adapt this approach to finite support distributions that may be partially unknown. we demonstrate that a myerson-style auction can be constructed in time polynomial in the number of bidders and the size of the support sets. next, we consider the scenario where the mechanism designer knows the support sets, but not the probability of each value. in this situation, we show that the optimal auction may be learned in polynomial time using a weak oracle that, given two candidate auctions, returns one with a higher expected revenue. to study this problem, we introduce a new class of truthful mechanisms which we call order-based auctions. we show that the optimal mechanism is an order-based auction and use the internal structure of this class to prove the correctness of our learning algorithm as well as to bound its running time.
delaunay refinement for piecewise smooth complexes. we present a delaunay refinement algorithm for meshing a piecewise smooth complex in three dimensions. the algorithm protects edges with weighted points to avoid the difficulty posed by small angles between adjacent input elements. these weights are chosen to mimic the local feature size and to satisfy a lipschitz-like property. a delaunay refinement algorithm using the weighted voronoi diagram is shown to terminate with the recovery of the topology of the input. guaranteed bounds on the aspect ratios, normal variation, and dihedral angles are also provided. to this end, we present new concepts and results including a new definition of local feature size and a proof for a generalized topological ball property.
squarepants in a tree: sum of subtree clustering and hyperbolic pants decomposition. we provide efficient constant-factor approximation algorithms for the problems of finding a hierarchical clustering of a point set in any metric space, minimizing the sum of minimimum spanning tree lengths within each cluster, and in the hyperbolic or euclidean planes, minimizing the sum of cluster perimeters. our algorithms for the hyperbolic and euclidean planes can also be used to provide a pants decomposition, that is, a set of disjoint simple closed curves partitioning the plane minus the input points into subsets with exactly three boundary components, with approximately minimum total length. in the euclidean case, these curves are squares; in the hyperbolic case, they combine our euclidean square pants decomposition with our tree clustering method for general metric spaces.
all-pairs bottleneck paths in vertex weighted graphs. let g = (v, e, w) be a directed graph, where w : v &larr; r is an arbitrary weight function defined on its vertices. the bottleneck weight, or the capacity, of a path is the smallest weight of a vertex on the path. for two vertices u, v the bottleneck weight, or the capacity, from u to v, denoted c(u, v), is the maximum bottleneck weight of a path from u to v. in the all-pairs bottleneck paths (apbp) problem we have to find the bottleneck weights for all ordered pairs of vertices. our main result is an o(n2.575) time algorithm for the apbp problem. the exponent is derived from the exponent of fast matrix multiplication. our algorithm is the first sub-cubic algorithm for this problem. unlike the sub-cubic algorithm for the all-pairs shortest paths (apsp) problem, that only applies to bounded (or relatively small) integer edge or vertex weights, the algorithm presented for apbp problem works for arbitrary large vertex weights. the apbp problem has numerous applications, and several interesting problems that have recently attracted attention can be reduced to it, with no asymptotic loss in the running times of the known algorithms for these problems. some examples are a result of vassilevska and williams [stoc 2006] on finding a triangle of maximum weight, a result of bender et al. [soda 2001] on computing least common ancestors in dags and a result of kowaluk and lingas [icalp 2005] on finding maximum witnesses for boolean matrix multiplication. thus, the apbp problem provides a uniform framework for these applications. for some of these problems, we can in fact show that their complexity is equivalent to that of the apbp problem. a slight modification of our algorithm enables us to compute shortest paths of maximum bottleneck weight. let d(u, v) denote the (unweighted) distance from u to v, and let sc(u, v) denote the maximum bottleneck weight of a path from u to v having length d(u, v). the all-pairs bottleneck shortest paths (apbsp) problem is to compute sc(u, v) for all ordered pairs of vertices. we present an algorithm for the apbsp problem whose running time is o(n2.86).
approximating entropy from sublinear samples. we consider the problem of approximating the entropy of a discrete distribution p on a domain of size q, given access to n independent samples from the distribution. it is known that n &ge; q is necessary, in general, for a good additive estimate of the entropy. a problem of multiplicative entropy estimate was recently addressed by batu, dasgupta, kumar, and rubinfeld. they show that n = q&alpha; suffices for a factor-&alpha; approximation, &alpha; > 1. we introduce a new parameter of a distribution--its effective alphabet size qef(p). this is a more intrinsic property of the distribution depending only on its entropy moments. we show qef &le; &otilde;(q). when the distribution p is essentially concentrated on a small part of the domain qef &lt; q. we strengthen the result of batu et al. by showing it holds with qef replacing q. this has several implications. in particular the rate of convergence of the maximum-likelihood entropy estimator (the empirical entropy) for both finite and infinite alphabets is shown to be dictated by the effective alphabet size of the distribution. several new, and some known, facts about this estimator follow easily. our main result is algorithmic. though the effective alphabet size is, in general, an unknown parameter of the distribution, we give an efficient procedure, with access to the alphabet size only, that achieves a factor-&alpha; approximation of the entropy with n = &otilde; (exp {&alpha; 1/4 &middot; log3/4 q &middot; log1/4 qef}). assuming (for instance) log qef &lt; log q this is smaller than any power of q. taking &alpha; &rarr; 1 leads in this case to efficient additive estimates for the entropy as well. in particular, this result shows that for many natural scenarios, a tight estimation of the entorpy may be achieved using a sub-linear sample. several extensions of the results above are discussed.
algorithms and incentives for robust ranking. spam in the form of link spam and click spam has become a major obstacle in the effective functioning of ranking and reputation systems. even in the absence of spam, difficulty in eliciting feedback and self-reinforcing nature of ranking systems are known problems. in this paper, we make a case for sharing with users the revenue generated by such systems as incentive to provide useful feedback and present an incentive based ranking scheme in a realistic model of user behavior which addresses the above problems. we give an explicit ranking algorithm based on user feedback. our incentive structure and ranking algorithm ensure that there is a profitable arbitrage opportunity for the users of the system in correcting the inaccuracies of the ranking. the system is oblivious to the source of inaccuracies (benign or malicious), thus making it robust to spam as well as the problems of eliciting feedback and self-reinforcement.
cheap labor can be expensive. we study markets in which consumers are trying to hire a team of agents to perform a complex task. each agent in the market prices their labor, and based on these prices, consumers hire the cheapest available team capable of doing the job they need done. we define the cheap labor cost in such a market as the ratio of the best nash equilibrium of the original market and the best possible nash equilibrium of any of its submarkets, where "best" is defined with respect to consumers, i.e., we are looking at nash equilibria in which the consumer pays the least. this definition is motivated by a "braess-style" paradox: in certain kinds of marketplaces, competition, in the form of the availability of "cheap labor", can actually cause the prices paid by consumers to go up. we present tight bounds on the cheap labor cost for a variety of markets including s-t path markets, matroid markets and perfect bipartite matching markets. the differences in cheap labor cost across markets demonstrate the complex relationship between the combinatorial structure of the marketplace and the advantages or more precisely, disadvantages to consumers due to competition.
the communication and streaming complexity of computing the longest common and increasing subsequences. we consider the communication complexity of finding the longest increasing subsequence (lis) of a string shared between two parties. we prove tight bounds for the space complexity of randomized one-pass streaming algorithms for this problem. our bounds are parameterized in terms of the lis of the inputs. this resolves an open question in [19]. we also give the first bounds for approximating the lis and its length. next, we consider the communication complexity of finding the longest common subsequece (lcs) of two strings held by different parties, as well as the problem of approximating its length. we improve the existing lower bounds for these problems, even in the most difficult case when both parties have a permutation of n symbols. our results yield tight space bounds for multipass deterministic streaming algorithms. for randomized mutlipass algorithms, our bounds are tight up to a logarithmic factor.
a near-optimal algorithm for computing the entropy of a stream. we describe a simple algorithm for approximating the empirical entropy of a stream of m values in a single pass, using o(&epsilon;-2 log(&delta;-1) log m) words of space. our algorithm is based upon a novel extension of a method introduced by alon, matias, and szegedy [1]. we show a space lower bound of &omega;(&epsilon;-2 / log(&epsilon;-1)), meaning that our algorithm is near-optimal in terms of its dependency on &epsilon;. this improves over previous work on this problem [8, 13, 17, 5]. we show that generalizing to kth order entropy requires close to linear space for all k &ge; 1, and give additive approximations using our algorithm. lastly, we show how to compute a multiplicative approximation to the entropy of a random walk on an undirected graph.
deterministic rendezvous, treasure hunts and strongly universal exploration sequences. we obtain several improved solutions for the deterministic rendezvous problem in general undirected graphs. our solutions answer several problems left open in a recent paper by dessmark et al. we also introduce an interesting variant of the rendezvous problem which we call the deterministic treasure hunt problem. both the rendezvous and the treasure hunt problems motivate the study of universal traversal sequences and universal exploration sequences with some strengthened properties. we call such sequences strongly universal traversal (exploration) sequences. we give an explicit construction of strongly universal exploration sequences. the existence of strongly universal traversal sequences, as well as the solution of the most difficult variant of the deterministic treasure hunt problem, are left as intriguing open problems.
worst case and probabilistic analysis of the 2-opt algorithm for the tsp: extended abstract. 2-opt is probably the most basic and widely used local search heuristic for the tsp. this heuristic achieves amazingly good results on "real world" euclidean instances both with respect to running time and approximation ratio. there are numerous experimental studies on the performance of 2-opt. however, the theoretical knowledge about this heuristic is still very limited. not even its worst case running time on euclidean instances was known so far. in this paper, we clarify this issue by presenting a family of euclidean instances on which 2-opt can take an exponential number of steps. previous probabilistic analyses were restricted to instances in which n points are placed uniformly at random in the unit square [0, 1]2, where it was shown that the expected number of steps is bounded by &otilde;(n10) for euclidean instances. we consider a more advanced model of probabilistic instances in which the points can be placed according to general distributions on [0, 1]2. in particular, we allow different distributions for different points. we study the expected running time in terms of the number n of points and the maximal density &phis; of the probability distributions. we show an upper bound on the expected length of any 2-opt improvement path of &otilde;(n4+1/3 &middot; &phis;8/3). when starting with an initial tour computed by an insertion heuristic, the upper bound on the expected number of steps improves even to &otilde;(n3+5/6 &middot; &phis;8/3). if the distances are measured according to the manhattan metric, then the expected number of steps is bounded by &otilde;(n3+1/2 &middot; &phis;). in addition, we prove an upper bound of o(&radic;&phis;) on the expected approximation factor with respect to both of these metrics. let us remark that our probabilistic analysis covers as special cases the uniform input model with &phis; = 1 and a smoothed analysis with gaussian perturbations of standard deviation &sigma; with &phis; ~ 1/&sigma;2. besides random metric instances, we also consider an alternative random input model in which an adversary specifies a graph and distributions for the edge lengths in this graph. in this model, we achieve even better results on the expected running time of 2-opt.
the quantum schur and clebsch-gordan transforms: i. efficient qudit circuits. we present an efficient family of quantum circuits for a fundamental primitive in quantum information theory, the schur transform. the schur transform on n d-dimensional quantum systems is a transform between a standard computational basis to a labelling related to the representation theory of the symmetric and unitary groups. if we desire to implement the schur transform to an accuracy of &epsilon;-1, then our circuit construction uses a number of gates which is polynomial in n, d and log(&epsilon;-1). the key tool in our construction is a poly(d, log n, log(&epsilon;-1)) algorithm for the ud clebsch-gordan transform. our efficient circuit construction renders numerous protocols in quantum information theory computationally tractable and yields a new possible approach to quantum algorithms which is distinct from the standard paradigm of the quantum fourier transform.
whole genome duplications, multi-break rearrangements, and genome halving problem. the genome halving problem, motivated by the whole genome duplication events in molecular evolution, was solved by el-mabrouk and sankoff. the el-mabrouk-sankoff algorithm is rather complex inspiring a quest for a simpler solution. an alternative approach to genome halving problem based on the notion of the contracted breakpoint graph was recently proposed in [2]. this new technique reveals that while the el-mabrouk-sankoff result is correct in most cases, it does not hold in the case of unichromosomal genomes. this raises a problem of correcting el-mabrouk-sankoff analysis and devising an algorithm that deals adequately with all genomes. in this paper we efficiently classify all genomes into two classes and show that while the el-mabrouk-sankoff theorem holds for the first class, it is incorrect for the second class. the crux of our analysis is a new combinatorial invariant defined on duplicated permutations. using this invariant we were able to come up with a full proof of the genome halving theorem and a polynomial algorithm for genome halving problem (for unichromosomal genomes). we also give the first short proof of the original el-mabrouk-sankoff result for multichromosomal genomes. finally, we discuss a generalization of genome halving problem for a more general set of rearrangement operations (including transpositions) and propose an efficient algorithm for solving this problem.
dynamic weighted ancestors. in the weighted ancestor problem one preprocesses a weighted tree (the weights are on the nodes and increase with tree depth) to support predecessor queries, which are called weighted ancestors queries, on the paths from the query node to the root. since, the weighted ancestor problem appears in numerous applications, the problem has been studied and solutions for static trees are well known. however, it has been an open question whether this can be solved optimally for the dynamic version of the problem, where node insertions are supported. node insertions are leaf insertions or edge splittings. in this paper we present a solution for the dynamic weighted ancestors problem which supports queries and update operations in the same time bounds as those for dynamic predecessor structures.
maximum independent sets in graphs of low degree. we study computational complexity of the maximum independent set problem on graphs of bounded vertex degree. in general, this problem is np-hard. however, under certain restrictions it becomes polynomial-time solvable. we identify three graph properties to which the complexity of the problem is sensible.
the -orientability thresholds for . we prove that, for k &ge; 2, the k-orientability threshold for the random graph gn, p coincides with the threshold at which the (k + 1)-core has average degree 2k. the proof involves the analysis of a heuristic algorithm that attempts to find a k-orientation of the random graph. the k-orientation threshold has several applications including offline balanced allocation with a limit of k on maximum bin-size, perfect hashing with a limit of k on maximum chain-length, and concurrent access to parallel memories through redundancy,
an algebraic algorithm for weighted linear matroid intersection. we present a new algebraic algorithm for the classical problem of weighted matroid intersection. this problem generalizes numerous well-known problems, such as bipartite matching, network flow, etc. our algorithm has running time &otilde;(nr&omega;-1w1+&epsilon;) for linear matroids with n elements and rank r, where &omega; is the matrix multiplication exponent, and w denotes the maximum weight of any element. this algorithm is the fastest known when w is small. our approach builds on the recent work of sankowski (2006) for weighted bipartite matching and harvey (2006) for unweighted linear matroid intersection.