waashk/dblp huggingface dataset:
uniformly erasable afl the purpose of this paper is to show that a number of well-known families have property (*). in particular, we prove that the family of context-free languages does indeed have this property. in addition, we show that several familiar subfamilies of the context-free languages, such as the one-counter languages, have property (*). finally, we show that there are families satisfying (*) which are not subfamilies of the context-free languages, for we prove that any family generated from one-letter languages has property (*), thereby extending a result of [17].
the theory of signature testing for vlsi several methods for testing vlsi chips can be classified as signature methods. both conventional and signature testing methods apply a number of test patterns to the inputs of the circuit. the difference is that a conventional method examines each output, while a signature method first accumulates the outputs in some data compression device, then examines the signature - the final contents of the accumulator - to see if it agrees with the signature produced by a good chip. signature testing methods have several advantages, but they run the risk that masking may occur. masking is said to occur if a faulty chip and a good chip behave differently on the test patterns, but the signatures are identical. when masking occurs, the signature testing method will incorrectly conclude that the chip is good, whereas a conventional method would discover that the chip is defective. this paper gives theoretical justification to the use of several signature testing techniques. we show that for these methods, the probability that masking will occur is small. an important difference between this and other work is that our results require very few assumptions about the behavior of faulty chips. they hold even in the presence of so-called correlated errors or even if the circuit were subject to sabatoge. when we speak of the probability of masking, we use the probabilistic approach of gill, rabin and others. that is, we introduce randomness into the testing method in a way which can be controlled by the designer. thus, one theorem assumes that the order of the input patterns - or the patterns themselves - is random; another assumes that the connections between the chip and the signature accumulator are made randomly, and a third assumes that the signature accumulator itself incorporates a random choice. most of the results of this paper use a particularly simple and practical signature accumulator based on a linear feedback shift register.
exact and approximate membership testers in this paper we consider the question of how much space is needed to represent a set. given a finite universe u and some subset v (called the vocabulary), an exact membership tester is a procedure that for each element s in u determines if s is in v. an approximate membership tester is allowed to make mistakes: we require that the membership tester correctly accepts every element of v, but we allow it to also accept a small fraction of the elements of u - v.
how to use expert advice. we analyze algorithms that predict a binary value by combining the predictions of several prediction strategies, called `experts''. our analysis is for worst-case situations, i.e., we make no assumptions about the way the sequence of bits to be predicted is generated. we measure the performance of the algorithm by the difference between the expected number of mistakes it makes on the bit sequence and the expected number of mistakes made by the best expert on this sequence, where the expectation is taken with respect to the randomization in the predictions. we show that the minimum achievable difference is on the order of the square root of the number of mistakes of the best expert, and we give efficient algorithms that achieve this. our upper and lower bounds have matching leading constants in most cases. we then show how this leads to certain kinds of pattern recognition/learning algorithms with performance bounds that improve on the best results currently known in this context. we also extend our analysis to the case in which log loss is used instead of the expected number of mistakes.
dynamic subgraph connectivity with geometric applications. inspired by dynamic connectivity applications in computational geometry, we consider a problem we call dynamic subgraph connectivity: design a data structure for an undirected graph $g=(v,e)$ and a subset of vertices $s \subseteq v$ to support insertions/deletions in $s$ and connectivity queries (are two vertices connected?) in the subgraph induced by $s$. we develop the first sublinear, fully dynamic method for this problem for general sparse graphs, using a combination of several simple ideas. our method requires $\widetilde o(|e|^{4\omega/(3\omega+3)})=o(|e|^{0.94})$ amortized update time, and $\widetilde o(|e|^{1/3})$ query time, after $\widetilde o(|e|^{(5\omega+1)/(3\omega+3)})$ preprocessing time, where &ohgr; is the matrix multiplication exponent and $\widetilde o$ hides polylogarithmic factors.
reversal complexity of counter machines it has long been known that deterministic 1-way counter machines recognize exactly all r.e. sets. here we investigate counter machines with general recursive bounds on counter reversals. our main result is that for bounds which are at least linear, counter reversal is polynomially related to turing machine time, for both 1-way and 2-way counter machines and in both the deterministic and the nondeterministic cases. this leads to natural characterizations of the classes p and np, and hence of the p &equil;? np question, on the counter machine model. we also establish reversal complexity hierarchies for counter machines, using a variety of techniques which include translation of turing machine time hierarchies, padding arguments as well as more ad hoc counting arguments.
a unified analysis of hot video schedulers. in this paper we consider the notion of relative competitive analysis, which is a simple generalization of the conventional competitive analysis and extra-resource analysis for on-line algorithms. we apply this analysis to study on-line schedulers for stream merging in two different video-on-demand (vod) systems, which are based on two common approaches, namely, piggybacking and skimming. our new analysis, in its simplest form, reveals a 3-competitive algorithm for stream merging based on skimming as well as piggybacking. this improves all previous results [4, 8]. we also show how to obtain guarantee on the performance improvement based on adding extra resources, and more interestingly, we provide a unified methodology to compare piggybacking and skimming. we believe that our result gives a clue to system designers for choosing desirable configurations.
abstract families of deterministic languages abstract families of (one-way) deterministic acceptors are formalized and shown to be characterized by families of languages closed under marked union, marked *, and inverse marked gsm mapping. the independence of these closure operations is also proved.
degrees of translatability and canonical forms in program schemas: part i we define a measure of the generality of the control structure of a program schema. this imposes a partial ordering on program schemas, and leads to a concept of the &ldquo;difficulty&rdquo; of a programming problem. in this sense there exists a &ldquo;hardest&rdquo; flowchart program, recursive program etc. some earlier proofs can also be simplified and/or clarified by this approach.
unbounded fan-in circuits and associative functions we consider the computation of finite semigroups using unbounded fan-in circuits. there are constant-depth, polynomial size circuits for semigroup product iff the semigroup does not contain a nontrivial group as a subset. in the case that the semigroup in fact does not contain a group, then for any primitive recursive function f, circuits of size o(nf&minus;1(n)) and constant depth exist for the semigroup product of n elements. the depth depends upon the choice of the primitive recursive function f. the circuits not only compute the semigroup product, but every prefix of the semigroup product. a consequence is that the same bounds apply for circuits computing the sum of two n-bit numbers.
multi-party protocols many different types of inter-process communication have been examined from a complexity point of view [sp, y]. we study a new model, in which a collection of processes p0, ..., pk&minus;1 that share information about a set of integers {a0, ...,ak&minus;1}, communicate to determine a 0-1 predicate of the numbers. in this new model, tremendous sharing of information is allowed, while no single party is given enough information to determine the predicate on its own. formally, each pi has access to every aj except for ai. for simplicity, we only allow the parties to communicate as follows.
computable queries for relational data bases (preliminary report) the concept of a &ldquo;reasonable&rdquo; query in a relational data base is investigated. we provide an abstract characterization of the class of queries which are computable, and define the completeness of a query language as the property of being precisely powerful enough to express the queries in this class. our main result is the completeness of a simple programming language which can be thought of as consisting of the relational algebra augmented with the power of iteration.
equations between regular terms and an application to process logic regular terms with the kleene operations &ugr;,;, and * can be thought of as operators on languages, generating other languages. an equation r1 &equil; r2 between two such terms is said to be satisfiable just in case languages exist which make this equation true. we show that the satisfiability problem even for *-free regular terms is undecidable. similar techniques are used to show that a very natural extension of the process logic of harel, kozen and parikh is undecidable.
embedded implicational dependencies and their inference problem it is shown that the general inference problem for embedded implicational dependencies (eids) is undecidable. for the more important case of finite inference (i.e., inference for finite data bases), the problem is not even recursively enumerable (r.e.); rather, it is complete in co-r.e. these results hold even for typed eids without equality, as well as for (untyped) template dependencies. the case for typed template dependencies remains open. the complexity of the inference problem for full dependencies has also been characterized - it is complete in exponential time for full implicational dependencies, and even for full typed template dependencies.
program schemas with equality we discuss the class of program schemas augmented with equality tests, that is, tests of equality between terms. in the first part of the paper we discuss and illustrate the &ldquo;power&rdquo; of equality tests. it turns out that the class of program schemas with equality is more powerful than the &ldquo;maximal&rdquo; classes of schemas suggested by other investigators. in the second part of the paper we discuss the decision problems of program schemas with equality. it is shown for example that while the decision problems normally considered for schemas (such as halting, divergence, equivalence, isomorphism and freedom) are solvable for ianov schemas, they all become unsolvable if general equality tests are added. we suggest, however, limited equality tests which can be added to certain subclasses of program schemas while preserving their solvable properties.
optimal implementation of conjunctive queries in relational data bases we define the class of conjunctive queries in relational data bases, and the generalized join operator on relations. the generalized join plays an important part in answering conjunctive queries, and it can be implemented using matrix multiplication. it is shown that while answering conjunctive queries is np complete (general queries are pspace complete), one can find an implementation that is within a constant of optimal. the main lemma used to show this is that each conjunctive query has a unique minimal equivalent query (much like minimal finite automata).
the analysis of two-dimensional patterns using picture processing grammars a method for the description of the hierarchical structure of two-dimensional pictures is proposed. the model is called picture-processing grammar. it can be regarded as an extension of phrase-structure grammars to the two-dimensional case. a picture analysis program is described. it accepts picture-processing grammar in tabular form and processes pictures using that grammar. experiments have been performed to analyze handwritten numerals, mathematical expressions and line drawings. some practical applications are discussed.
on the parallel computation of local operations the problem of parallel computation of local operations using five differently organized parallel processing machines (the sasd, sapd, pasd, pamd, and papd computers) is investigated. it is shown that for a special class of local operations, called window operations, there is a trade-off between computation time and machine complexity. it is also shown that for the pamd computer, the computation time increases as the degree of disorderliness of the local operation increases. in conclusion, in the designing of special-purpose parallel processing machines, we must take into consideration the degree of disorderliness of the operations to be performed.
similarity estimation techniques from rounding algorithms. (math) a locality sensitive hashing scheme is a distribution on a family $\f$ of hash functions operating on a collection of objects, such that for two objects x,y, prh&egr;f[h(x) = h(y)] = sim(x,y), where sim(x,y) &egr; [0,1] is some similarity function defined on the collection of objects. such a scheme leads to a compact representation of objects so that similarity of objects can be estimated from their compact sketches, and also leads to efficient algorithms for approximate nearest neighbor search and clustering. min-wise independent permutations provide an elegant construction of such a locality sensitive hashing scheme for a collection of subsets with the set similarity measure sim(a,b) = \frac{|a &pgr; b|}{|a &pgr b|}.(math) we show that rounding algorithms for lps and sdps used in the context of approximation algorithms can be viewed as locality sensitive hashing schemes for several interesting collections of objects. based on this insight, we construct new locality sensitive hashing schemes for:<ol>a collection of vectors with the distance between &rarr; \over u and &rarr; \over v measured by &oslash;(&rarr; \over u, &rarr; \over v)/&pgr;, where &oslash;(&rarr; \over u, &rarr; \over v) is the angle between &rarr; \over u) and &rarr; \over v). this yields a sketching scheme for estimating the cosine similarity measure between two vectors, as well as a simple alternative to minwise independent permutations for estimating set similarity.a collection of distributions on n points in a metric space, with distance between distributions measured by the earth mover distance (emd), (a popular distance measure in graphics and vision). our hash functions map distributions to points in the metric space such that, for distributions p and q, emd(p,q) &xie; eh&egr;\f [d(h(p),h(q))] &xie; o(log n log log n). emd(p, q).</ol>.
incremental clustering and dynamic information retrieval. motivated by applications such as document and image classification in information retrieval, we consider the problem of clustering dynamic point sets in a metric space. we propose a model called incremental clustering which is based on a careful analysis of the requirements of the information retrieval application, and which should also be useful in other applications. the goal is to efficiently maintain clusters of small diameter as new points are inserted. we analyze several natural greedy algorithms and demonstrate that they perform poorly. we propose new deterministic and randomized incremental clustering algorithms which have a provably good performance, and which we believe should also perform well in practice. we complement our positive results with lower bounds on the performance of incremental algorithms. finally, we consider the dual clustering problem where the clusters are of fixed diameter, and the goal is to minimize the number of clusters.
on non-uniform multicommodity buy-at-bulk network design. we study the multicommodity buy-at-bulk network design problem in which we seek to design a network that satisfies the demands between terminals from a given set of source-sink pairs. the key characteristic of this problem is the fact that the cost functions associated with the edges of the graph are sub-additive monotone and hence experience economies of scale. in the non-uniform case, each edge has its own cost function -- possibly different from other edges. special cases of this problem have been studied extensively: there are approximation algorithms when the edge cost functions are identical or when all source-sink pairs share the same source. we present the first non-trivial approximation algorithm for the general case. our algorithm is an extremely simple randomized greedy algorithm and has an approximation guarantee of exp(o√ln n ln ln n)) when the instance has at most n source-sink pairs with unit demands. in the case of general demands, this yields an approximation factor of exp(o √ln n ln ln n)), where n is the sum of all demands.
algorithms for capacitated vehicle routing. given n identical objects (pegs), placed at arbitrary initial locations, we consider the problem of transporting them efficiently to n target locations (slots) with a vehicle that can carry at most k pegs at a time. this problem is referred to as k-delivery tsp, and it is a generalization of the traveling salesman problem. we give a 5-approximation algorithm for the problem of minimizing the total distance traveled by the vehicle.there are two kinds of transportations possible---one that could drop pegs at intermediate locations and pick them up later in the route for delivery (preemptive) and one that transports pegs to their targets directly (nonpreemptive). in the former case, by exploiting the freedom to drop, one may be able to find a shorter delivery route. we construct a nonpreemptive tour that is within a factor 5 of the optimal preemptive tour. in addition we show that the ratio of the distances traveled by an optimal nonpreemptive tour versus a preemptive tour is bounded by 4.
approximating the smallest grammar: kolmogorov complexity in natural models. we consider the problem of finding the smallest context-free grammar that generates exactly one given string of length n. the size of this grammar is of theoretical interest as an efficiently computable variant of kolmogorov complexity. the problem is of practical importance in areas such as data compression and pattern extraction.the smallest grammar is known to be hard to approximate to within a constant factor, and an o(logn/log logn) approximation would require progress on a long-standing algebraic problem [10]. previously, the best proved approximation ratio was o(n1/2) for the bisection algorithm [8]. our main result is an exponential improvement of this ratio; we give an o(log (n/g*)) approximation algorithm, where g* is the size of the smallest grammar.we then consider other computable variants of kolomogorov complexity. in particular we give an o(log2 n) approximation for the smallest non-deterministic finite automaton with advice that produces a given string. we also apply our techniques to "advice-grammars" and "edit-grammars", two other natural models of string complexity.
near-optimal algorithms for unique games. unique games are constraint satisfaction problems that can be viewed as a generalization of max-cut to a larger domain size. the unique games conjecture states that it is hard to distinguish between instances of unique games where almost all constraints are satisfiable and those where almost none are satisfiable. it has been shown to imply a number of inapproximability results for fundamental problems that seem difficult to obtain by more standard complexity assumptions. thus, proving or refuting this conjecture is an important goal. we present significantly improved approximation algorithms for unique games. for instances with domain size k where the optimal solution satisfies 1-ε fraction of all constraints, our algorithms satisfy roughly k-ε/(2-ε) and 1- o(√εlog k) fraction of all constraints. our algorithms are based on rounding a natural semidefinite programming relaxation for the problem and their performance almost matches the integrality gap of this relaxation. our results are near optimal if the unique games conjecture is true, i.e. any improvement (beyond low order terms) would refute the conjecture.
better streaming algorithms for clustering problems. we study clustering problems in the streaming model, where the goal is to cluster a set of points by making one pass (or a few passes) over the data using a small amount of storage space. our main result is a randomized algorithm for the k--median problem which produces a constant factor approximation in one pass using storage space o(k poly log n). this is a significant improvement of the previous best algorithm which yielded a 2o(1/ε) approximation using o(nε) space. next we give a streaming algorithm for the k--median problem with an arbitrary distance function. we also study algorithms for clustering problems with outliers in the streaming model. here, we give bicriterion guarantees, producing constant factor approximations by increasing the allowed fraction of outliers slightly.
clustering to minimize the sum of cluster diameters. we study the problem of clustering points in a metric space so as to minimize the sum of cluster diameters or the sum of cluster radii. significantly improving on previous results, we present a primal-dual based constant factor approximation algorithm for this problem. we present a simple greedy algorithm that achieves a logarithmic approximation. this also applies when the distance function is asymmetric and the objective is to minimize the sum of cluster radii. the previous best-known result obtained a logarithmic approximation with a constant factor blowup in the number of clusters. we also obtain an incremental clustering algorithm that maintains a solution whose cost is at most a constant factor times that of optimal with a constant factor blowup in the number of clusters.
convex decompositions of polyhedra an important direction of research in computational geometry has been to find methods for decomposing complex structures into simpler components. in this paper, we examine the problem of decomposing a three-dimensional polyhedron p into a minimal number of convex pieces. letting n be the number of vertices in p and n the number of edges which exhibit a reflex angle (i.e. the notches of p), our main result is an o(nn3) time algorithm for computing a convex decomposition of p. the algorithm produces o(n2) convex parts, which is optimal in the worst case. in most situations where the problem arises (e.g. graphics, tool design, pattern recognition), the number of notches n seems greatly dominated by the number of vertices n; the algorithm is therefore viable in practice.