waashk/dblp huggingface dataset:
how to generate random integers with known factorization recent work in public-key cryptography has led to the need to generate large random numbers with known factorization. this paper describes a probabilistic algorithm that produces a random k-bit integer in factored form. each such number is equally likely to appear. the expected running time is, up to a constant factor, that required for k prime tests on k-bit integers. thus, under reasonable assumptions about the speed of primality testing, it is a polynomial time process.
realistic analysis of some randomized algorithms many problems such as primality testing can be solved efficiently using a source of independent, identically distributed random numbers. it is therefore customary in the theory of algorithms to assume the availability of such a source. however, probabilistic algorithms often work well in practice with pseudo-random numbers; the point of this paper is to offer a justification for this fact. the results below apply to sequences generated by iteratively applying functions of the form &fnof; (&khgr;) = &agr;&khgr; + &bgr; (mod p) to a randomly chosen seed x, and estimate the probability that a predetermined number of trials of an algorithm will fail. in particular, the following bounds hold: for finding square roots modulo a prime p, a failure probability of &ogr; (log p/&radic;p). for testing p for primality, a failure probability of &ogr; (p-1/4+&egr;), for any &egr;>0. (in both cases, the number of trials is about 1/2 log p.) the analysis uses results of andr&eacute; weil concerning the number of points on algebraic varieties over finite fields.
average case analysis for batched disk scheduling and increasing subsequences. (math) we consider the problem of estimating the tour length and finding approximation algorithms for the asymmetric traveling salesman problem arising from the disk scheduling problem. given n requests, we show that if the seek function has positive derivative at 0 the tour length is concentrated in probability around the value cf,pn1/2 for an explicit constant cf,p dependent on the seek function and the distribution of requests. for linear seek function we provide even tighter bounds and provide an o(nlog(n)) time algorithm for finding the optimal tour. the proof uses several results on the size and location of maximal increasing subsequences. to handle more general seek functions we introduce a more general concept of increasing subsequences. we provide order of magnitude estimates on the tour length for a wide class of seek functions with vanishing derivative at 0. for general seek functions we use some geometric information on the location of maximal generalized increasing subsequences obtained via talagrand's isoperimetric inequalities to produce a probabilistic 1+&egr; approximation algorithm. these results complement the results on guaranteed approximation algorithms for this problem presented in [2].
low-distortion embeddings of general metrics into the line. a low-distortion embedding between two metric spaces is a mapping which preserves the distances between each pair of points, up to a small factor called distortion. low-distortion embeddings have recently found numerous applications in computer science.most of the known embedding results are "absolute",that is, of the form: any metric y from a given class of metrics c can be embedded into a metric x with low distortion c. this is beneficial if one can guarantee low distortion for all metrics y in c. however, in any situations, the worst-case distortion is too large to be meaningful. for example, if x is a line metric, then even very simple metrics (an n - point star or an n -point cycle) are embeddable into x only with distortion linear in n. nevertheless, embeddings into the line (or into low-dimensional spaces) are important for many applications.a solution to this issue is to consider "relative" (or "approximation") embedding problems, where the goal is to design an (a-approxiation) algorithm which, given any metric x from c as an input, finds an embedding of x into y which has distortion a *cy (x), where cy (x)is the best possible distortion of an embedding of x into y.in this paper we show algorithms and hardness results for relative embedding problems.in particular we give: •an algorith that, given a general metric m, finds an embedding with distortion o (δ3⁄4 poly(c line (m))), where δ is the spread of m•an algorithm that,given a weighted tree etric m, finds an embedding with distortion poly(c line (m)) •a hardness result, showing that computing minimum line distortion is hard to approximate up to a factor polynomial in n,even for weighted tree metrics with spread δ=n o (1).
approximate clustering via core-sets. in this paper, we show that for several clustering problems one can extract a small set of points, so that using those core-sets enable us to perform approximate clustering efficiently. the surprising property of those core-sets is that their size is independent of the dimension.using those, we present a (1+ &egr;)-approximation algorithms for the k-center clustering and k-median clustering problems in euclidean space. the running time of the new algorithms has linear or near linear dependency on the number of points and the dimension, and exponential dependency on 1/&egr; and k. as such, our results are a substantial improvement over what was previously known.we also present some other clustering results including (1+ &egr;)-approximate 1-cylinder clustering, and k-center clustering with outliers.
tree transductions and families of tree languges interest in the study of sets of trees, tree languages, has led to the definition of finite automata which accept trees [2,11] and transducers which map trees into other trees [7,9,10]. these generalized machines may read treesfinite automata which accept trees [2,11] and of transducers which map trees into other trees [7,9,10]. these generalized machines may read trees either &ldquo;top-down&rdquo; (from the root toward the leaves) or &ldquo;bottom-up&rdquo; (from the leaves toward the root). here it is shown that both the class of top-down transductions and the class of bottom-up transductions can be characterized in terms of two restricted classes of tree transductions. from these ductions and the class of bottom-up transductions can be characterized in terms of two restricted classes of tree transductions. from these characterizations, it is shown that the composition of any n bottom-up transductions can be realized by the composition of n+1 top-down transductions, and similarly, the composition of any n top-down transductions can be realized by the composition of n+1 bottom-up transductions. next, we study the families of tree languages which can be obtained from the recognizable sets (sets accepted by finite tree automata) by the composition of n top-down or bottom-up transductions, n>0. the yield operation, which concatenates the leaves of a tree from left to right to form a of string, languages from the hierarchy of families of tree languages. it is shown that each family of string languages in this hierarchy is properly contained in the family of context-sensitive languages.
stable prehension with three fingers we study grasps by a robot hand in the absence of friction. in two dimensions, a hand with three spring-loaded fingers and five degrees of freedom can achieve an equilibrium grasp on any object described by a polygon. furthermore, the grasp is stable, that is, at a local minimum of the potential energy function defined by the springs of the fingers. in three dimensions, the hand can grasp any cylinder. in contrast, if the degrees of freedom of the hand are restricted to correspond to a hand built by hanafusa and asada, stable grips on a polygon cannot in general be achieved.
approximation algorithms for deadline-tsp and vehicle routing with time-windows. given a metric space g on n nodes, with a start node r and deadlines d(v) for each vertex v, we consider the deadline-tsp problem of finding a path starting at r that visits as many nodes as possible by their deadlines. we also consider the more general vehicle routing with time-windows problem, in which each node v also has a release-time r(v) and the goal is to visit as many nodes as possible within their "time-windows" [r(v),d(v)]. no good approximations were known previously for these problems on general metric spaces. we give an o(logn) approximation algorithm for deadline-tsp, and extend this algorithm to an o(log2n) approximation for the time-window problem. we also give a bicriteria approximation algorithm for both problems: given an ε>0, our algorithm produces a (1/ε) approximation, while exceeding the deadlines by a factor of 1+ε. we use as a subroutine for these results a constant-factor approximation that we develop for a generalization of the orienteering problem in which both the start and the end nodes of the path are fixed. in the process, we give a 3-approximation to the orienteering problem, improving on the previously best known 4-approximation of [6].
a quasi-ptas for unsplittable flow on line graphs. we study the unsplittable flow problem (ufp) on line graphs and cycles, focusing on the long-standing open question of whether the problem is apx-hard. we describe a deterministic quasi-polynomial time approximation scheme for ufp on line graphs, thereby ruling out an apx-hardness result, unless np ⊆ dtime(2polylog(n)). our result requires a quasi-polynomial bound on all edge capacities and demands in the input instance. we extend this result to undirected cycle graphs.earlier results on this problem included a polynomial time (2+ε)-approximation under the assumption that no demand exceeds any edge capacity (the "no-bottleneck assumption") and a super-constant integrality gap if this assumption did not hold. unlike most earlier work on ufp, our results do not require a no-bottleneck assumption.
server scheduling in the l norm: a rising tide lifts all boat. often server systems do not implement the best known algorithms for optimizing average quality of service (qos) out of concern of that these algorithms may be insufficiently fair to individual jobs. the standard method for balancing average qos and fairness is optimize the lp metric, 1 < p < ∞. thus we consider server scheduling strategies to optimize the lp norms of the standard qos measures, flow and stretch. we first show that there is no no(1)-competitive online algorithm for the lp norms of either flow or stretch. we then show that the standard clairvoyant algorithms for optimizing average qos, sjf and srpt, are o(1+ε)-speed o(1/ε)-competitive for the lp norms of flow and stretch. and that the standard nonclairvoyant algorithm for optimizing average qos, setf, is o(1+ε)-speed o(1/ε(2+2/p))-competitive for the lp norms of flow. these results argue that these standard algorithms will not starve jobs until the system is near peak capacity. in contrast, we show that the round robin, or processor sharing algorithm, which is sometimes adopted because of its seeming fairness properties, is not o(1+ε)-speed no(1)-competitive for sufficiently small ε.
the santa claus problem. we consider the following problem: the santa claus has n presents that he wants to distribute among m kids. each kid has an arbitrary value for each present. let pij be the value that kid i has for present j. the santa's goal is to distribute presents in such a way that the least lucky kid is as happy as possible, i.e he tries to maximize mini=1,...,m sumj ∈ si pij where si is a set of presents received by the i-th kid.our main result is an o(log log m/log log log m) approximation algorithm for the restricted assignment case of the problem when pij ∈ pj,0 (i.e. when present j has either value pj or 0 for each kid). our algorithm is based on rounding a certain natural exponentially large linear programming relaxation usually referred to as the configuration lp. we also show that the configuration lp has an integrality gap of ω(m1/2) in the general case, when pij can be arbitrary.
a unified approach to approximating resource allocation and scheduling. we present a general framework for solving resource allocation and scheduling problems. given a resource of fixed size, we present algorithms that approximate the maximum throughput or the minimum loss by a constant factor. our approximation factors apply to many problems, among which are: (i) real-time scheduling of jobs on parallel machines, (ii) bandwidth allocation for sessions between two endpoints, (iii) general caching, (iv) dynamic storage allocation, and (v) bandwidth allocation on optical line and ring topologies. for some of these problems we provide the first constant factor approximation algorithm. our algorithms are simple and efficient and are based on the local-ratio technique. we note that they can equivalently be interpreted within the primal-dual schema.
bandwidth allocation with preemption. bandwidth allocation is a fundamental problem in the design of networks where bandwidth has to be reserved for connections in advance. the problem is intensified when the requested bandwidth exceeds the capacity and not all requests can be served. furthermore, acceptance/rejection decisions regarding connections have to be made on-line, without knowledge of future requests. we show that the ability to preempt (i.e., abort) connections while in service in order to be able to schedule ``more valuable'''' connections substantially improves the overall throughput of some networks. we present bandwidth allocation strategies that use preemption and show that they achieve constant competiveness with respect to the throughput, given that any single call occupies only a constant fraction of the bandwidth. our results should be contrasted with recent works showing that nonpreemptive strategies have at most logarithmic competitiveness.
on approximating a vertex cover for planar graphs the approximation problem for vertex cover of n-vertex planar graphs is treated. two results are presented: (1) a linear time approximation algorithm for which the (error) performance bound is 2/3. (2) an o(n log n) time approximation scheme.
sampling lower bounds via information theory. we present a novel technique, based on the jensen-shannon divergence from information theory, to prove lower bounds on the query complexity of sampling algorithms that approximate functions over arbitrary domain and range. unlike previous methods, our technique does not use a reduction from a decision promise problem. as a result, it gives stronger bounds for functions that possess a large set of inputs, each two of which exhibit a gap in the function value.we demonstrate the technique with new query complexity lower bounds for three fundamental problems: (1) the "election problem", for which we obtain a quadratic improvement over previous bounds, (2) low rank matrix approximation, for which we prove the first lower bounds, showing that the algorithms given for this problem are almost optimal, and (3) matrix reconstruction.in addition, we introduce a new method for proving lower bounds on the expected query complexity of functions, using the kullback-leibler divergence. we demonstrate its use by a simple query complexity lower bound for the mean.
exponential separation of quantum and classical one-way communication complexity. we give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. specifically, we define the hidden matching problem hmn: alice gets as input a string x ∈ (0, 1)n and bob gets a perfect matching m on the n coordinates. bob's goal is to output a tuple [i,j,b] such that the edge (i,j) belongs to the matching m and b = xi ⊕ xj. we prove that the quantum one-way communication complexity of hmn is o(log n), yet any randomized one-way protocol with bounded error must use ω(√n) bits of communication. no asymptotic gap for one-way communication was previously known. our bounds also hold in the model of simultaneous messages (sm) and hence we provide the first exponential separation between quantum sm and randomized sm with public coins.for a boolean decision version of hmn, we show that the quantum one-way communication complexity remains o(log n) and that the 0-error randomized one-way communication complexity is ω(n). we prove that any randomized linear one-way protocol with bounded error for this problem requires ω(√[3] n log n) bits of communication.
sampling algorithms: lower bounds and applications. we develop a framework to study probabilistic sampling algorithms that approximate general functions of the form \genfunc, where \domain and \range are arbitrary sets. our goal is to obtain lower bounds on the query complexity of functions, namely the number of input variables x_i that any sampling algorithm needs to query to approximate f(x_1,\ldots,x_n).we define two quantitative properties of functions --- the it block sensitivity and the minimum hellinger distance --- that give us techniques to prove lower bounds on the query complexity. these techniques are quite general, easy to use, yet powerful enough to yield tight results. our applications include the mean and higher statistical moments, the median and other selection functions, and the frequency moments, where we obtain lower bounds that are close to the corresponding upper bounds.we also point out some connections between sampling and streaming algorithms and lossy compression schemes.
simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors. a distribution x over binary strings of length n has min-entropy k if every string has probability at most 2-k in x. we say that x is a δ-source if its rate k⁄n is at least δ.we give the following new explicit instructions (namely, poly(n)- time computable functions) of deterministicextractors, dispersers and related objects. all work for any fixed rate δ>0. no previous explicit construction was known for either of these, for any δ‹1⁄2. the first two constitute major progress to very long-standing open problems. bipartite ramsey f1: (0,1)n)2 →0,1, such that for any two independent δ-sources x1, x2 we have f1(x1,x2) = 0,1 this implies a new explicit construction of 2n-vertex bipartite graphs where no induced nδ by nδ subgraph is complete or empty. multiple source extraction f2: (0,1n)3→0,1 such that for any three independent δ-sources x1,x2,x3 we have that f2(x1,x2,x3) is (o(1)-close to being) an unbiased random bit. constant seed condenser2 f3: n →(0,1m)c, such that for any δ-source x, one of the c output distributions f3(x)i, is a 0.9-source over 0,1m. here c is a constant depending only on δ.subspace ramsey f4: 0,1n→0,1 such that for any affine-δ-source3 x we have f4(x)= 0,1.the constructions are quite involved and use as building blocks other new and known gadgets. but we can point out two important themes which recur in these constructions. one is that gadgets which were designed to work with independent inputs, sometimes perform well enough with correlated, high entropy inputs. the second is using the input to (introspectively) find high entropy regions within itself.
strict polynomial-time in simulation and extraction. the notion of efficient computation is usually identified in cryptography and complexity with (strict) probabilistic polynomial-time. however, until recently, in order to obtain \emph{constant-round} zero-knowledge proofs and proofs of knowledge, one had to allow simulators and knowledge extractors to run in time that is only polynomial on the average (i.e., expected polynomial-time). recently barak gave the first constant-round zero-knowledge argument with a strict (in contrast to expected) polynomial-time simulator. the simulator in his protocol is a nonblack-box simulator (i.e., it makes inherent use of the description of the code of the verifier).in this paper, we further address the question of strict polynomial-time in constant-round zero-knowledge proofs and arguments of knowledge. first, we show that there exists a constant-round zero-knowledge argument of knowledge with a strict polynomial-time knowledge extractor. as in the simulator of barak's zero-knowledge protocol, the extractor for our argument of knowledge is not black-box and makes inherent use of the code of the prover. on the negative side, we show that nonblack-box techniques are essential for both strict polynomial-time simulation and extraction. that is, we show that no (nontrivial) constant-round zero-knowledge proof or argument can have a strict polynomial-time black-box simulator. similarly, we show that no (nontrivial) constant-round zero-knowledge proof or argument of knowledge can have a strict polynomial-time black-box knowledge extractor.
2-source dispersers for sub-polynomial entropy and ramsey graphs beating the frankl-wilson construction. the main result of this paper is an explicit disperser for two independent sources on n bits, each of entropy k=no(1). put differently, setting n=2n and k=2k, we construct explicit n x n boolean matrices for which no k x k submatrix is monochromatic. viewed as adjacency matrices of bipartite graphs, this gives an explicit construction of k-ramsey bipartite graphs of size n.this greatly improves the previous bound of k=o(n) of barak, kindler, shaltiel, sudakov and wigderson [4]. it also significantly improves the 25-year record of k = õ (√n) on the special case of ramsey graphs, due to frankl and wilson [9].the construction uses (besides "classical" extractor ideas) almost all of the machinery developed in the last couple of years for extraction from independent sources, including:bourgain's extractor for 2 independent sources of some entropy rate < 1/2 [5]raz's extractor for 2 independent sources, one of which has any entropy rate > 1/2 [18]rao's extractor for 2 independent block-sources of entropy nω (1) [17]the "challenge-response" mechanism for detecting "entropy concentration" of [4].the main novelty comes in a bootstrap procedure which allows the challenge-response mechanism of [4] to be used with sources of less and less entropy, using recursive calls to itself. subtleties arise since the success of this mechanism depends on restricting the given sources, and so recursion constantly changes the original sources. these are resolved via a new construct, in between a disperser and an extractor, which behaves like an extractor on sufficiently large subsources of the given ones.this version is only an extended abstract, please see the full version, available on the authors' homepages, for more details.
short random walks on graphs. the short-term behavior of random walks on graphs is studied, in particular, the rate at which a random walk discovers new vertices and edges. a conjecture by linial that the expected time to find $\cal n$ distinct vertices is $o({\cal n}^{3})$ is proved. in addition, upper bounds of $o({\cal m}^{2})$ on the expected time to traverse $\cal m$ edges and of $o(\cal m \cal n)$ on the expected time to either visit $\cal n$ vertices or traverse $\cal m$ edges (whichever comes first) are proved.
now you may compose temporal logic specifications a compositional temporal logic proof system for the specification and verification of concurrent programs is presented. versions of the system are developed for shared variables and communication based programming languages that include procedures.
finite monoids and the fine structure of nc¹ recently a new connection was discovered between the parallel complexity class nc1 and the theory of finite automata in the work of barrington on bounded width branching programs. there (nonuniform) nc1 was characterized as those languages recognized by a certain nonuniform version of a dfa. here we extend this characterization to show that the internal structures of nc1 and the class of automata are closely related. in particular, using th&eacute;rien's classification of finite monoids, we give new characterizations of the classes ac0, depth-k ac0, and acc, the last being the ac0 closure of the mod q functions for all constant q. we settle some of the open questions in [3], give a new proof that the dot-depth hierarchy of algebraic automata theory is infinite [8], and offer a new framework for understanding the internal structure of nc1.