waashk/dblp huggingface dataset:
on finding lowest common ancestors in trees trees in an n node forest are to be merged according to instructions in a given sequence, while other instructions in the sequence ask for the lowest common ancestor of pairs of nodes. we show that any sequence of o(n) instructions can be processed &ldquo;on line&rdquo; in o(n log n) steps on a random access computer. if we can accept our answer &ldquo;off-line&rdquo;, that is, no answers need to be produced until the entire sequence of instructions has been seen seen, then we may perform the task in o(n g(n)) steps, where g(n) is the number of times we must apply log2 to n to obtain a number less than or equal to zero. a third algorithm solves a problem of intermediate complexity. we require the answers on line, but we suppose that all tree merging instructions precede the information requests. this algorithm requires o(n log log n) time. we apply the first on line algorithm to a problem in code optimization, that of computing immediate dominators in a reducible flow graph. we show how this computation can be performed in o(n log n) steps.
on notions of information transfer in vlsi circuits several papers have recently dealt with techniques for proving area-time lower bounds for vlsi computation by &ldquo;crossing sequence&rdquo; methods. a number of natural questions are raised by these definitions. 1.is the fooling set approach the most powerful way to get information-transfer-based lower bounds? we shall show it is not, and offer a candidate for the title &ldquo;most powerful.&rdquo; of course, without a precise definition of &ldquo;information transfer argument,&rdquo; there could be other contenders. 2.are the notions of the three papers cited equivalent? we shall exhibit certain inequivalences among the three notions, although open questions remain. however, we can resolve an open question of papadimitriou and sipser [ps] concerning the relationship between nondeterministic and deterministic communication complexity.
quantum lower bounds by quantum arguments. we propose a new method for proving lower bounds on quantum query algorithms. instead of a classical adversary that runs the algorithm with on input and then modifies the input, we use a quantum adversary that runs the algorithm with a superposition of inputs. if the algorithm works correctly, its state becomes entangled with the superposition over inputs. we bound the number of queries needed to achieve a sufficient entanglement and this implies a lower bound on the number of queries for the computation. using this method, we prove two new ω(√n) lower bounds on computing and of ors and inverting a permutation and also provide more uniform proofs for several known lower bounds which have been previously proven via a variety of different techniques.
a new protocol and lower bounds for quantum coin flipping. we present a new protocol and two lower bounds for quantum coin flipping. in our protocol, no dishonest party can achieve one outcome with probability more than 0.75. then we show that out protocol is optimal among 3-round protocols of a certain form.for arbitrary quantum protocols, we show that if a protocol achieves a bias of at most ε, it must use at least ω(log log 1ε) rounds of communication. this implies that the parallel repetition fails for quantum coin flipping. (the bias of a protocol cannot be arbitrarily decreased by running several copies of it in parallel.)
quantum algorithms a decade after shor. in 1994, peter shor discovered a polynomial time quantum algorithm for factoring and discrete logarithm. two years later, in 1996, lov grover discovered a search algorithm which is quadratically better than conventional search. by now, each of the two algorithms has developed into a line of research which goes well beyond the original algorithm. shor's algorithm has inspired the study of quantum fourier sampling which has resulted in more quantum algorithms for number-theoretic and group-theoretic problems. grover's algorithm has developed into the area of quantum query algorithms.i will survey the developments in quantum query algorithms. the topics will include: applications of grover's algorithm to element distinctness and other problems, lower bounds on quantum algorithms and the use of quantum random walks to design better search algorithm. i will also describe how some of techniques in this area can be used as "quantum black boxes" in an otherwise classical algorithm.
lower bounds for linear degeneracy testing. in the late nineties, erickson proved a remarkable lower bound on the decision tree complexity of one of the central problems of computational geometry: given n numbers, do any r of them add up to 0? his lower bound of &omega;(n&lceil;r/2&rceil;), for any fixed r, is optimal if the polynomials at the nodes are linear and at most r-variate. we generalize his bound to s-variate polynomials for s > r. erickson's bound decays quickly as r grows and never reaches above pseudo-polynomial: we provide an exponential improvement. our arguments are based on three ideas: (i) a geometrization of erickson's proof technique; (ii) the use of error-correcting codes; and (iii) a tensor product construction for permutation matrices.
one-dimensional quantum walks. we define and analyze quantum computational variants of random walks on one-dimensional lattices. in particular, we analyze a quantum analog of the symmetric random walk, which we call the hadamard walk. several striking differences between the quantum and classical cases are observed. for example, when unrestricted in either direction, the hadamard walk has position that is nearly uniformly distributed in the range [-t/\sqrt 2, t/\sqrt 2] after t steps, which is in sharp contrast to the classical random walk, which has distance o(\sqrt t) from the origin with high probability. with an absorbing boundary immediately to the left of the starting position, the probability that the walk exits to the left is 2/&pgr, and with an additional absorbing boundary at location n, the probability that the walk exits to the left actually increases, approaching 1/\sqrt 2 in the limit. in the classical case both values are 1.
approximate nearest neighbors and the fast johnson-lindenstrauss transform. we introduce a new low-distortion embedding of l2d into lpo(log n) (p=1,2), called the fast-johnson-linden-strauss-transform. the fjlt is faster than standard random projections and just as easy to implement. it is based upon the preconditioning of a sparse projection matrix with a randomized fourier transform. sparse random projections are unsuitable for low-distortion embeddings. we overcome this handicap by exploiting the "heisenberg principle" of the fourier transform, ie, its local-global duality. the fjlt can be used to speed up search algorithms based on low-distortion embeddings in l1 and l2. we consider the case of approximate nearest neighbors in l2d. we provide a faster algorithm using classical projections, which we then further speed up by plugging in the fjlt. we also give a faster algorithm for searching over the hypercube.
quantum walks on graphs. we set the ground for a theory of quantum walks on graphs-the generalization of random walks on finite graphs to the quantum world. such quantum walks do not converge to any stationary distribution, as they are unitary and reversible. however, by suitably relaxing the definition, we can obtain a measure of how fast the quantum walk spreads or how confined the quantum walk stays in a small neighborhood. we give definitions of mixing time, filling time, dispersion time. we show that in all these measures, the quantum walk on the cycle is almost quadratically faster then its classical correspondent. on the other hand, we give a lower bound on the possible speed up by quantum walks for general graphs, showing that quantum walks can be at most polynomially faster than their classical counterparts.
aggregating inconsistent information: ranking and clustering. we address optimization problems in which we are given contradictory pieces of input information and the goal is to find a globally consistent solution that minimizes the number of disagreements with the respective inputs. specifically, the problems we address are rank aggregation, the feedback arc set problem on tournaments, and correlation and consensus clustering. we show that for all these problems (and various weighted versions of them), we can obtain improved approximation factors using essentially the same remarkably simple algorithm. additionally, we almost settle a long-standing conjecture of bang-jensen and thomassen and show that unless np⊆bpp, there is no polynomial time algorithm for the problem of minimum feedback arc set in tournaments.
the invasiveness of off-line memory checking. memory checking is the task of checking the correctness of a sequence of "store" and "retrieve" operations. the operations are performed in a large unreliable memory. a checker using a much smaller but completely reliable memory tries to decide whether they were executed correctly. m. blum, w. evans, p. gemmel, s. kannan and m. naor, has shown in 1991 that the off-line checking of a sequence of memory operations concerning a ram consisting of n registers can be done, in a probabilistic sense, by a checker using only o(log n) reliable memory and a constant number of ram operation per each "store" and "retrieve" operations (with log n word length), moreover no unproven cryptographic assumptions are needed in the proof. the probability of error will be polynomially small in n. the solution however requires the checker to store some extra information in the unreliable memory, that is, the checking protocol is invasive. (in this solution the time of each "store" operation must be stored together with the data and must be supplied to the checker at the time of the corresponding retrieve operation.) in this paper we prove that off-line memory checking, in the sense described above, is necessarily invasive, even if we make the problem somewhat easier for the checker to exclude trivial counter-examples. we show that even if the checker is allowed to read a constant number of registers from the large memory after each "store" or "retrieve" instruction, off-line non-invasive memory checking is not possible. moreover for the case when the invasiveness consists of storing some extra information together with each piece of data and retrieving it together with the data we give a quantitative lower bound on the amount of extra "invasive" information stored in the memory. namely, if the checker has o(log n) memory and the probability of error is polynomially small than the "invasiveness" of the mentioned method of [5] is optimal upto a constant factor. with other words the total number of extra bits that must be written in the memory is at least &egr;t log t, where t is the number of store and retrieve operations. in the lower bounds we do not restrict the computational power of the checker at all, in fact we only assume that the checker is an n-way branching program with o(log n) bits of memory.
the worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice. schnorr's algorithm for finding an approximation for the shortest nonzero vector in an n dimensional lattice depends on a parameter k. he proved that for a fixed k ≤ n his algorithm (block 2k-reduction) provides a lattice vector whose length is greater than the length of a shortest nonzero vector in the lattice by at most a factor of (4k2) n/k. (the time required by the algorithm depends on k.) we show that if k=o(n), this bound on the performance of schnorr's algorithm cannot be improved (apart from a constant factor in the exponent), namely there is a lattice and a basis so that if they are given as an input to the algorithm then the resulting approximating factor of the output is at least k ε n/k. (for larger integers k if schnorr's algorithm runs in polynomial time then we have already a polynomial time algorithm for finding the shortest nonzero vector.) we also solve an open problem formulated by schnorr about the the korkine-zolotareff lattice constants αk. we show that his upper bound αk ≤ k1 + ln k is the best possible apart from a constant factor in the exponent. we prove a similar result about his upper bound βk≤ 4k2, where βk is another lattice constant with an important role in schnorr's analysis of his algorithm.
hierarchies based on computational complexity and irregularities of class determining measured sets (preliminary report) we consider here the problem of building transfinite hierarchies of computable functions on the basis of their difficulty of computation. previous hierarchies of functions through the constructive ordinals have had two major problems, each apparently caused by not having techniques to restrict the classes considered at limit ordinals. these problems are, first that every function occurs at some name for &ohgr;, or some other small ordinal, and second that two names for the same constructive ordinal have two different classes of functions associated with them. the axioms of computational complexity introduced by blum[1] and several theorems by blum[1],and by mccreight and meyer[9], particularly the union theorem, lead to a very natural method of hierarchy building that partially avoids the first of these problems. the other problem is not overcome, however. in attempting to understand the problem of obtaining unique, or nearly unique classes of functions we have encountered difficulties because the class determining measured sets of mccreight and meyer[9] lack several properties that might reasonably be desired.
computing the betti numbers of arrangements. (math) in this paper, we consider the problem of computing the betti numbers of an arrangement of $n$ compact semi-algebraic sets, $s_1,\ldots,s_n \subset \r^k$, where each $s_i$ is described using a constant number of polynomials with degrees bounded by a constant. such arrangements are ubiquitous in computational geometry. we give an algorithm for computing $\ell$-th betti number, $\beta_\ell(\cup_i s_i), 0 \leq \ell \leq k-1$, using $o(n^{\ell+2})$ algebraic operations. additionally, one has to perform linear algebra on matrices of size bounded by $o(n^{\ell+1})$. all previous algorithms for computing the betti numbers of arrangements, triangulated the arrangement giving rise to a complex of size $o(n^{2^k})$ in the worst case. to our knowledge this is the first algorithm for computing $\beta_\ell(\cup_i s_i)$ that does not rely on such a global triangulation, and has a graded complexity which depends on $\ell$.
hardness of the undirected edge-disjoint paths problem. we show that there is no log 1 over 3-ε m approximation for the undirected edge-disjoint paths problem unless np ⊆ zptime(npolylog(n), where m is the size of the graph and ε is any positive constant. this hardness result also applies to the undirected all-or-nothing multicommodity flow problem and the undirected node-disjoint paths problem.
hardness of the undirected congestion minimization problem. we show that there is no $\gamma\log\log m/\log\log\log m$-approximation for the undirected congestion minimization problem unless $np \subseteq zptime(n^{{\rm polylog} n})$, where $m$ is the size of the graph and &ggr; is some positive constant.
logarithmic hardness of the directed congestion minimization problem. we show that for any constant ε > 0, there is no ω(log1-εm)-approximation algorithm for the directed congestion minimization problem on networks of size m unless np ⊆ zptime(npolylog n). this bound is almost tight given the o(log m/ log log m)-approximation via randomized rounding due to raghavan and thompson.
finding patterns common to a set of strings (extended abstract) we motivate, formalize, and study a computational problem in concrete inductive inference. a &ldquo;pattern&rdquo; is defined to be a concatenation of constants and variables, and the language of a pattern is defined to be the set of strings obtained by substituting constant strings for the variables. the problem we consider is, given a set of strings, find a minimal pattern language containing this set. this problem is shown to be effectively solvable in the general case and to lead to correct inference in the limit of the pattern languages. there exists a polynomial time algorithm for it in the restricted case of one-variable patterns. inference from positive data is re-examined, and a characterization given of when it is possible for a family of recursive languages. various collateral results about patterns and pattern languages are obtained. section 1 is an introduction explaining the context of this work and informally describing the problem formulation. section 2 is definitions. section 3 is results concerning patterns and pattern languages. section 4 concerns the abstract question of inference from positive data. section 5 gives a polynomial time algorithm for finding minimal one-variable pattern languages compatible with a given set of strings. section 6 contains remarks.
local and global properties in networks of processors (extended abstract) this paper attempts to get at some of the fundamental properties of distributed computing by means of the following question: &ldquo;how much does each processor in a network of processors need to know about its own identity, the identities of other processors, and the underlying connection network in order for the network to be able to carry out useful functions?&rdquo; the approach we take is to require that the processors be designed without any knowledge (or only very broad knowledge) of the networks they are to be used in, and furthermore, that all processors with the same number of communication ports be identical. given a particular network function, e.g., setting up a spanning tree, we ask whether processors may be designed so that when they are embedded in any connected network and started in some initial configuration, they are guaranteed to accomplish the desired function.
learning a circuit by injecting values. we propose a new model for exact learning of acyclic circuits using experiments in which chosen values may be assigned to an arbitrary subset of wires internal to the circuit, but only the value of the circuit's single output wire may be observed. we give polynomial time algorithms to learn (1) arbitrary circuits with logarithmic depth and constant fan-in and (2) boolean circuits of constant depth and unbounded fan-in over and, or, and not gates. thus, both ac0 and nc1 circuits are learnable in polynomial time in this model. negative results show that some restrictions on depth, fan-in and gate types are necessary: exponentially many experiments are required to learn and/or circuits of unbounded depth and fan-in; it is np-hard to learn and/or circuits of unbounded depth and fan-in 2; and it is np-hard to learn circuits of bounded depth and unbounded fan-in over and, or, and threshold gates, even when the target circuit is known to contain at most one threshold gate and that threshold gate has threshold 2. we also consider the effect of adding an oracle for behavioral equivalence. in this case there are polynomial-time algorithms to learn arbitrary circuits of constant fan-in and unbounded depth and to learn boolean circuits with arbitrary fan-in and unbounded depth over and, or, and not gates. a corollary is that these two classes are pac-learnable if experiments are available.
fast probabilistic algorithms for hamiltonian circuits and matchings the main purpose of this paper is to give techniques for analysing the probabilistic performance of certain kinds of algorithms, and hence to suggest some fast algorithms with provably desirable probabilistic behaviour. the particular problems we consider are: finding hamiltonian circuits in directed graphs (dhc), finding hamiltonian circuits in undirected graphs (uhc), and finding perfect matchings in undirected graphs (pm). we show that for each problem there is an algorithm that is extremely fast (0(n(log n)2) for dhc and uhc, and 0(nlog n) for pm), and which with probability tending to one finds a solution in randomly chosen graphs of sufficient density. these results contrast with the known np-completeness of the first two problems [2,12] and the best worst-case upper bound known of 0(n2.5) for the last [9].
near-optimal network design with selfish agents. we introduce a simple network design game that models how independent selfish agents can build or maintain a large network. in our game every agent has a specific connectivity requirement, i.e. each agent has a set of terminals and wants to build a network in which his terminals are connected. possible edges in the network have costs and each agent's goal is to pay as little as possible. determining whether or not a nash equilibrium exists in this game is np-complete. however, when the goal of each player is to connect a terminal to a common source, we prove that there is a nash equilibrium as cheap as the optimal network, and give a polynomial time algorithm to find a (1+ε)-approximate nash equilibrium that does not cost much more. for the general connection game we prove that there is a 3-approximate nash equilibrium that is as cheap as the optimal network, and give an algorithm to find a (4.65+ε)-approximate nash equilibrium that does not cost much more.
stability of load balancing algorithms in dynamic adversarial systems. in the dynamic load balancing problem, we seek to keep the job load roughly evenly distributed among the processors of a given network. the arrival and departure of jobs is modeled by an adversary restricted in its power. muthukrishnan and rajaraman [an adversarial model for distributed dynamic load balancing, in proceedings of the 10th acm symposium on parallel algorithms and architectures, acm, new york, 1998] gave a clean characterization of a restriction on the adversary that can be considered the natural analogue of a cut condition. they proved that a simple local balancing algorithm proposed by aiello et al. [approximate load balancing on dynamic and asynchronous networks, in proceedings of the 25th acm symposium on theory of computing, acm, new york, 1993] is stable against such an adversary if the insertion rate is restricted to a $(1-\varepsilon)$ fraction of the cut size. they left as an open question whether the algorithm is stable at rate 1. in this paper, we resolve this question positively, by proving stability of the local algorithm at rate 1. our proof techniques are very different from the ones used by muthukrishnan and rajaraman and yield a simpler proof and tighter bounds on the difference in loads. in addition, we introduce a multicommodity version of this load balancing model and show how to extend the result to the case of balancing two different kinds of loads at once (obtaining as a corollary a new proof of the 2-commodity max-flow min-cut theorem). we also show how to apply the proof techniques to the problem of routing packets in adversarial systems. awerbuch et al. [simple routing strategies for adversarial systems, in proceedings of the 42nd ieee symposium on foundations of computer science, ieee computer society, los alamitos, ca, 2001] showed that the same load balancing algorithm is stable against an adversary, inserting packets at rate 1 with a single destination in dynamically changing networks. our techniques give a much simpler proof for a different model of adversarially changing networks.