waashk/dblp huggingface dataset:
on the limits of cache-obliviousness. in this paper, we present lower bounds for permuting and sorting in the cache-oblivious model. we prove that (1) i/o optimal cache-oblivious comparison based sorting is not possible without a tall cache assumption, and (2) there does not exist an i/o optimal cache-oblivious algorithm for permuting, not even in the presence of a tall cache assumption.our results for sorting show the existence of an inherent trade-off in the cache-oblivious model between the strength of the tall cache assumption and the overhead for the case m » b, and show that funnelsort and recursive binary mergesort are optimal algorithms in the sense that they attain this trade-off.
optimal finger search trees in the pointer machine. we develop a new finger search tree with worst-case constant update time in the pointer machine (pm) model of computation. this was a major problem in the field of data structures and was tantalizingly open for over 20 years, while many attempts by researchers were made to solve it. the result comes as a consequence of the innovative mechanism that guides the rebalancing operations, combined with incremental multiple splitting and fusion techniques over nodes.
trading space for time in undirected s-t connectivity aleliunas et al. [1] posed the following question: &ldquo;the reachability problem for undirected graphs can be solved in logspace and o(mn) time [m is the number of edges and n is the number of vertices] by a probabilistic algorithm that simulates a random walk, or in linear time and space by a conventional deterministic graph traversal algorithm. is there a spectrum of time-space trade-offs between these extremes?&rdquo; we answer this question in the affirmative for linear-sized graphs by presenting an algorithm which is faster than the random walk by a factor essentially proportional to the size of its workspace. for denser graphs, the algorithm is faster than the random walk but the speed-up factor is smaller.
the complexity of priority queue maintenance a notion of priority queue efficiency is defined, based on comparison counting. a good lower bound on the average and worst case number of comparisons is derived; several priority queue algorithms are exhibited which nearly attain the bound. it is shown that one of these algorithms, using binomial queues, can be characterized in a simple way based on the number and type of comparisons that it requires. the proof of this result involves an interesting problem on trees for which huffman's construction gives a solution.
kraft storage and access for list implementations (extended abstract) this paper is part of an investigation into efficient ways of implementing variable-length lists (see brown [1]). storage and access optimality are discussed from an information-theoretic viewpoint; in particular, we develop the notions of kraft storage and kraft access (see elias [4]). our attention here is restricted to the implementation of questions of the form: &ldquo;what is the ith element in the list?&rdquo; we derive consequences of achieving kraft storage and/or kraft access and then examine some common implementation schemes. in this abstract we shall give only an informal discussion of some basic concepts and results.
a representation for linear lists with movable fingers this paper describes a data structure which is useful for representing linear lists when the pattern of accesses to a list exhibits a (perhaps time-varying) locality of reference. the structure has many of the properties of the representation proposed by guibas, mccreight, plass, and roberts [4], but is substantially simpler and may be practical for lists of moderate size. the analysis of our structure includes a general treatment of the worst-case node splitting caused by consecutive insertions into a 2-3 tree.
on time-space classes and their relation to the theory of real addition a new lower bound on the computational complexity of the theory of real addition and several related theories is established: any decision procedure for these theories requires either space 2&egr;n or nondeterministic time 2&egr;n2 for some constant &egr; > o and infinitely many n. the proof is based on the families of languages tisp(t(n),s(n)) which can be recognized simultaneously in time t(n) and space s(n) and the conditions under which they form a hierarchy.
on the extended direct sum conjecture we consider the quadratic complexity of certain sets of quadratic forms. we study a classes of direct sums of quadratic forms. for these classes of problems we show that the complexity of one direct sum is the sum of the complexity of the summands and that every minimal quadratic algorithm for computing the direct sums is a direct-sum algorithm.
noise-tolerant distribution-free learning of general geometric concepts. we present an efficient algorithm for pac-learning a very general class of geometric concepts over r d for fixed d. more specifically, let t be any set of s halfspaces. let x =(x1, &hellip;, xd) be an arbitrary point in r d. with each t&isin;t we associate a boolean indicator function it(x) which is 1 if and only if x is in the halfspace t. the concept class, cds , that we study consists of all concepts formed by any boolean function over it1, &hellip;, its for ti &isin;t . this class is much more general than any geometric concept class known to be pac-learnable. our results can be extended easily to learn efficiently any boolean combination of a polynomial number of concepts selected from any concept class c over r given that the vc-dimension of c has dependence only on d and there is a polynomial time algorithm to determine if there is a concept from c consistent with a given set of labeled examples. we also present a statistical query version of our algorithm that can tolerate random classification noise. finally we present a generalization of the standard &egr;-net result of haussler and welzl [1987] and apply it to give an alternative noise-tolerant algorithm for d = 2 based on geometric subdivisions.
learning arithmetic read-once formulas a formula is read-once if each variable appears at most once in it. an arithmetic read-once formula is one in which the operators are addition, subtraction, multiplication, and division. we present polynomial time algorithm for exactly learning (or interpolating) arithmetic read-once formulas computing functions over a field. we present an algorithm that uses randomized membership queries (or substitutions) to identify such formulas over large finite fields and infinite fields. we also present a deterministic algorithm that uses equivalence queries as well as membership queries to identify arithmetic read-once formulas over small finite fields. we then non-constructively show the existence of deterministic membership query (interpolation) algorithms for arbitrary formulas over fields of characteristic 0 and for division-free formulas over large or infinite fields. our algorithms assume we are able to efficiently perform arithmetic operations on field elements and compute square roots in the field. it is shown that the ability to compute square roots is necessary, in the sense that the problem of computing n &ndash; 1 square roots in a field can be reduced to the problem of identifying an arithmetic formula over n variables in that field. our equivalence queries are of a slightly non-standard form, in which counterexamples are required to not be inputs on which the formula evaluates to 0/0. this assumption is shown to be necessary for fields of size o(n/log n), for which it is shown that there is no polynomial time identification algorithm that uses just membership and standard equivalence queries.
opt versus load in dynamic storage allocation. dynamic storage allocation is the problem of packing given axis-aligned rectangles into a horizontal strip of minimum height by sliding the rectangles vertically but not horizontally. where l= is the maximum sum of heights of rectangles that intersect any vertical line and opt is the minimum height of the enclosing strip, it is obvious that $\ensuremath{\text{\it opt}}\ge \ensuremath{\text{\it load}}$; previous work showed that $\ensuremath{\text{\it opt}}\le 3\cdot load. we continue the study of the relationship between opt and load, proving that opt=l+o((hmax/l)1/7)l, where hmax is the maximum job height. conversely, we prove that for any $\epsilon>0$, there exists a c>0 such that for all sufficiently large integers $h_{\max}$, there is a dynamic storage allocation instance with maximum job height $h_{\max}$, maximum load at most l, and $\ensuremath{\text{\it opt}}\geq l+c(h_{\max}/l)^{1/2+\epsilon}l$, for infinitely many integers l. en route, we construct several new polynomial-time approximation algorithms for dynamic storage allocation, including a $(2+\epsilon)$-approximation algorithm for the general case and polynomial-time approximation schemes for several natural special cases.
are bitvectors optimal? we study the it static membership problem: given a set s of at most n keys drawn from a universe u of size m, store it so that queries of the form "is u in s?" can be answered by making few accesses to the memory. we study schemes for this problem that use space close to the information theoretic lower bound of $\omega(n\log(\frac{m}{n}))$ bits and yet answer queries by reading a small number of bits of the memory.we show that, for $\epsilon > 0$, there is a scheme that stores $o(\frac{n}{\epsilon^2}\log m)$ bits and answers membership queries using a randomized algorithm that reads just one bit of memory and errs with probability at most $\epsilon$. we consider schemes that make no error for queries in s but are allowed to err with probability at most $\epsilon$ for queries not in s. we show that there exist such schemes that store $o((\frac{n}{\epsilon})^2 \log m)$ bits and answer queries using just one bitprobe. if multiple probes are allowed, then the number of bits stored can be reduced to $o(n^{1+\delta}\log m)$ for any $\delta > 0$. the schemes mentioned above are based on probabilistic constructions of set systems with small intersections.we show lower bounds that come close to our upper bounds (for a large range of n and $\epsilon$): schemes that answer queries with just one bitprobe and error probability $\epsilon$ must use $\omega(\frac{n}{\epsilon\log(1/\epsilon)} \log m)$ bits of storage; if the error is restricted to queries not in s, then the scheme must use $\omega(\frac{n^2}{\epsilon^2 \log (n/\epsilon)}\log m)$ bits of storage. we also consider deterministic schemes for the static membership problem and show tradeoffs between space and the number of probes.
the complexity of maximal constraint languages. many combinatorial search problems can be expressed as &ldquo;constraint satisfaction problems&rdquo; using an appropriate &ldquo;constraint language&rdquo;, that is, a set of relations over some fixed finite set of values. it is well-known that there is a trade-off between the expressive power of a constraint language and the complexity of the problems it can express. in the present paper we systematically study the complexity of all maximal constraint languages, that is, languages whose expressive power is just weaker than that of the language of all constraints. using the algebraic invariance properties of constraints, we exhibit a strong necessary condition for tractability of such a constraint language. moreover, we show that, at least for small sets of values, this condition is also sufficient.
counting complexity classes for numeric computations ii: algebraic and semialgebraic sets. we define counting classes #pr and #pc in the blum-shub-smale setting of computations over the real or complex numbers, respectively. the problems of counting the number of solutions of systems of polynomial inequalities over r, or of systems of polynomial equalities over c, respectively, turn out to be natural complete problems in these classes. we investigate to what extent the new counting classes capture the complexity of computing basic topological invariants of semialgebraic sets (over r) and algebraic sets (over c). we prove that the problem of computing the euler-yao characteristic of semialgebraic sets is fpr#pr-complete, and that the problem of computing the geometric degree of complex algebraic sets is fpc#pc-complete. we also define new counting complexity classes in the classical turing model via taking boolean parts of the classes above, and show that the problems to compute the euler characteristic and the geometric degree of (semi)algebraic sets given by integer polynomials are complete in these classes. we complement the results in the turing model by proving, for all k ∈ n, the fpspace-hardness of the problem of computing the kth betti number of the set of real zeros of a given integer polynomial. this holds with respect to the singular homology as well as for the borel-moore homology.
complexity problems in real time computation the study of computational complexity is continued under the additional requirement that the turing machines operate in real time. the work reported here is motivated by that of rabin [r] which asks implicitly about the computational power of n tape vs n+1 tape real time turing machines and that of hartmanis [h] who attempts a complexity measure for turing machines in terms of reversals. the first result concerns itself with n tape real time turing machines operating in a reversal bounded mode. a doubly infinite hierarchy (tapes-reversals) of classes of real time computable functions is shown to exist. the second result deals with n deterministic real time pushdown automata operating independently in parallel. it is shown that an increase in the number of pushdown automata operating in this manner always yields an increase in the computational power of the configuration.
on generalized finite automata and unrestricted generative grammars the notion of the graphical representation of a &ldquo;canonical derivation&rdquo; is extended to semi-thue systems; the graphs are called &ldquo;derivation structures.&rdquo; derivation structures are distinguished from phrase structures and generative grammars are distinguished from phrase structure grammars. the distinctions disappear only in the context free case. this paper considers generative grammars and derivation structures. (a subsequent paper will consider phrase-structure grammars and phrase structures.) the notion of generalized finite automaton (tree automaton) is extended to systems which process arbitrary labeled directed ordered acyclic graphs. we study a restriction of these automata which process derivation structures. analogous to the hierarchy of generative grammars, it is shown that there is a hierarchy of generalized finite automata which recognize the same languages. their structure-defining relationship is a generalization of the context free case, i.e., the structures recognized by the automata are projections of the structures defined by the grammars. the proofs give algorithms for constructing the automata from the grammars and the grammars from the automata.
a decomposition of multi-dimensional point-sets with applications to k-nearest-neighbors and n-body potential fields (preliminary version) we define the notion of a well-separated pair decomposition of points in d-dimensional space. we develop efficient sequential and parallel algorithms for computing such a decomposition. we apply the resulting decomposition to the efficient computation of k-nearest neighbors and n-body potential fields.
adaptively secure multi-party computation. a fundamental problem in designing secure multi-party protocols is how to deal with adaptive adversaries (i.e., adversaries that may choose the corrupted parties during the course of the computation), in a setting where the channels are insecure and secure communication is achieved by cryptographic primitives based on computational limitations of the adversary. it turns out that the power of an adaptive adversary is greatly affected by the amount of information gathered upon the corruption of the party. this amount of information models the extent to which uncorrupted parties are trusted to carry out instructions that cannot be externally verified, such as erasing records of past configurations. it has been shown that if the parties are trusted to erase such records, then adaptivity secure computation can be carried out using known primitives. however, this total trust in parties may be unrealistic in many scenarios. an important question, open since 1986, is whether adaptively secure multi-party computation can be carried out in the "insecure channel" setting, even if no party is thoroughly trusted. our main result is an affirmative resolution of this question for the case where even uncorrupted parties may deviate from the protocol by keeping record of all past configurations. we first propose a novel property of encryption protocols and show that if an encryption protocol enjoying this property is used, instead of a standard encryption scheme, then known constructions become adaptively secure. next we constructed, based on standard rsa assumption, an encryption protocol that enjoys this property. we also consider parties that, even when corrupted, may internally deviate from their protocols in arbitrary ways, as long as no external test can detect faulty behavior. we show that in this case no non-trivial protocol can be proven adaptively secure using black-box simulation. this holds even if the communication channels are totally secure.
bounding the power of preemption in randomized scheduling. we study on-line scheduling in overloaded systems. requests for jobs arrive one by one as time proceeds; the serving agents have limited capacity and not all requests can be served. still, we want to serve the "best" set of requests according to some criterion. in this situation, the ability to preempt (i.e., abort) jobs in service in order to make room for better jobs that would otherwise be rejected has proven to be of great help in some scenarios. we show that, surprisingly, in many other scenarios this is not the case. in a simple, generic model, we prove a polylogarithmic lower bound on the competitiveness of randomized and preemptive on-line scheduling algorithms. our bound applies to several recently studied problems. in fact, in certain scenarios our bound is quite close to the competitiveness achieved by known deterministic, nonpreemptive algorithms.
universally composable two-party and multi-party secure computation. we show how to securely realize any multi-party functionality in a universally composable way, regardless of the number of corrupted participants. that is, we consider a multi-party network with open communication and an adversary that can adaptively corrupt as many parties as it wishes. in this setting, our protocols allow any subset of the parties (with pairs of parties being a special case) to securely realize any desired functionality of their local inputs, and be guaranteed that security is preserved regardless of the activity in the rest of the network. this implies that security is preserved under concurrent composition of an unbounded number of protocol executions, it implies non-malleability with respect to arbitrary protocols, and more. our constructions are in the common reference string model and make general intractability assumptions.
some algebraic and geometric computations in pspace we give a pspace algorithm for determining the signs of multivariate polynomials at the common zeros of a system of polynomial equations. one of the consequences of this result is that the &ldquo;generalized movers' problem&rdquo; in robotics drops from exptime into pspace, and is therefore pspace-complete by a previous hardness result [rei]. we also show that the existential theory of the real numbers can be decided in pspace. other geometric problems that also drop into pspace include the 3-d euclidean shortest path problem, and the &ldquo;2-d asteroid avoidance problem&rdquo; described in [rs]. our method combines the theorem of the primitive element from classical algebra with a symbolic polynomial evaluation lemma from [bkr]. a decision problem involving several algebraic numbers is reduced to a problem involving a single algebraic number or primitive element, which rationally generates all the given algebraic numbers.
randomness conductors and constant-degree lossless expanders. the main concrete result of this paper is the first explicit construction of constant degree "lossless" expanders. in these graphs, the expansion factor is almost as large as possible: (1-eps)d, where d is the degree and eps is an arbitrarily small constant. such graphs are known to have many applications, e.g. in constructing networks that can implement fast distributed, routing algorithms, expander-based linear codes, various storage schemes, and hard tautologies for various proof systems. the best previous explicit constructions gave expansion factor d/2, which is too weak for many applications. the d/2 bound was obtained via the eigenvalue method, and is known that that method cannot give better bounds.the main abstract contribution of this paper is the introduction and initial study of "randomness conductors," a notion which generalizes extractors, expanders, condensers and other similar objects. in all these functions, certain guarantee on the input "entropy" is converted to a guarantee on the output "entropy". for historical reasons, specific objects used specific guarantees of different flavors (e.g., in expanders entropy means "support size", and their property is satisfied whenever input entropy is small. in contrast, in extractors, entropy means "min-entropy" and their property is satisfied whenever input entropy is large). we show that the flexibility afforded by the conductor definition leads to interesting combinations of these objects, and to better constructions such as those above.the main technical tool in these constructions is a natural generalization to conductors of the zig-zag graph product, previously defined for expanders and extractors.
exponential space complete problems for petri nets and commutative semigroups: preliminary report the uniform word problem for commutative semigroups (uwcs) is the problem of determining from any given finite set of defining relations and any pair of words, whether the words describe the same element in the commutative semigroup defined by the relations. the effective decidability of this classical algebraic problem was first explicitly noted by malcev [1958] and emilichev [1958], though in retrospect this result can be seen to be contained in the earlier work of k&ouml;nig [1903] and hermann [1926] on polynomial ideals.
graph pebbling with many free pebbles can be difficult the pebble game on directed acyclic graphs can be used to model the space-time tradeoff behavior of a straight-line algorithm (sla). in this game, the maximum number of pebbles used at any one time corresponds to the number of temporary registers available and is called space. the number of moves made to reach the outputs of the graph, or the time, corresponds to the number of operations required by the sla. in this paper, it is shown that there exist infinite families of constructible graphs on n nodes which possess an extreme time-space tradeoff. for a particular set of graphs, if space is restricted to fall in the range of &thgr;(log n) to &thgr;((@@@@n/log n)), then the pebbling time necessary is superpolynomial in n. this result is obtained by deriving a lower bound on time when extra space is restricted, and then diagonalizing over the amount of this space. an extension of this argument shows that the minimum space requirement for such constructible graph families can grow as any slowly increasing function of n.