waashk/dblp huggingface dataset:
time-space trade-offs for asynchronous parallel models: reducibilities and equivalences the question of relative efficiencies is studied in the context of a simple model of communicating aynchronous processes. the fundamental problem is whether a simple distributed system, with arbitrary size variables, is any more powerful than a system where only binary valued variables are permitted. the answer was (surprisingly) found to be negative, with an intuitive definition of the power of systems. the development of these notions required formalization of concepts such as equivalence of models, and the reduction of systems between models. it was discovered that requiring a strong definition of equivalence which decreased time apparently results in an increase in space. the trade-offs involved are seen to be tight in one approach to the problem.
economical solutions for the critical section problem in a distributed system (extended abstract) a solution to the critical section problem, first posed by dijkstra [1], is a fundamental requirement for concurrent program control. the problem is to ensure that no two processes are in a specified area of their programs (the critical section) at the same time. improvements to dijkstra's solution were made by knuth [2], debruijn [3], and eisenberg and mcguire [4]. the situation, for a distributed system was considered by lamport [5]. rivest and pratt [6] presented a solution for a distributed system where processes may repeatedly fail. the algorithms to be presented will be further improvements, where the comparisons will be made according to three measures: message size&mdash;the number of values the variable for interprocess communication can take on; fairness&mdash;the sequence in which waiting processes enter their critical sections; and time&mdash;the amount of time a process spends attempting to enter its critical section.
two infinite sets of primes with fast primality tests infinite sets p and q of primes are described, p &sub; q. for any natural number n it can be decided if n &isin; p in (deterministic) time &ogr;((log n)9). this answers affirmatively the question of whether there exists an infinite set of primes whose membership can be tested in polynomial time, and is the main result of the paper. also, for every n &isin; q, we show how to produce at random, in expected time &ogr;((log n)3), a certificate of length &ogr;(log n) which can be verified in (deterministic) time &ogr;((log n)3); this is less than the time needed for two exponentiations and is much faster than existing methods. finally it is important that p is relatively dense (at least cn2/3/log n elements less than n). elements of q in a given range may be generated quickly, but it would be costly for an adversary to search q in this range; this could be useful in cryptography.
the realization of monotone boolean functions (preliminary version) in this paper we study the complexity of realizing a monotone but otherwise arbitrary boolean function. we consider realizations by means of networks and formulae. in both cases the possibility exists that although a monotone function can always be realized in terms of monotone basis functions, a more economical realization may be possible if basis functions that are not themselves monotone are used. thus, we have four cases, namely: 1. the cost of realizing a monotone function with a network over a universal basis. 2. the cost of realizing a monotone function with a network over a monotone basis. 3. the cost of realizing a monotone function with a formula over a universal basis. 4. the cost of realizing a monotone function with a formula over a monotone basis. for the first case, we obtain a complete solution to the problem. for the other three cases, we obtain improvements over previous results and come within a logarithmic factor or two of a complete solution.
comparative schematology and pebbling with auxiliary pushdowns (preliminary version) this paper has three claims to interest. first, it combines comparative schematology with complexity theory. this combination is capable of distinguishing among strong's &ldquo;languages of maximal power,&rdquo; a distinction not possible when comparative schematology is based on computability considerations alone, and it is capable of establishing exponential disparities in running times, a capability not currently possessed by complexity theory alone. secondly, this paper inaugurates the study of pebbling with auxiliary pushdowns, which bears to plain pebbling the same relationship as cook's study of space-bounded machines with auxiliary pushdowns bears to plain space-bounded machines. this extension of pebbling serves as the key to the problems of comparative schematology mentioned above. finally, this paper advantageously displays the virtues of recent work by gabber and galil giving explicit constructions for certain graphs, for the availability of such explicit constructions is essential to the results of this paper.
probabilistic simulations (preliminary version) the results of this paper concern the question of how fast machines with one type of storage media can simulate machines with a different type of storage media. most work on this question has focused on the question of how fast one deterministic machine can simulate another. in this paper we shall look at the question of how fast a probabilistic machine can simulate another. this approach should be of interest in its own right, in view of the great attention that probabilistic algorithms have recently attracted.
self-routing superconcentrators. superconcentrators are switching systems that solve the generic problem of interconnecting clients and servers during sessions, in situations where either the clients or the servers are interchangable (so that it does not matter which client is connected to which server). previous constructions of superconcentrators have required an external agent to find the interconnections appropriate in each instance. we remedy this shortcoming by constructing superconcentrators that are ``self-routing'''', in the sense that they compute for themselves the required interconnections. specifically, we show how to construct, for each n, a system s_n with the following properties. (1) the system s_n has n inputs, n outputs, and o(n) components, each of which is of one of a fixed finite number of finite automata, and is connected to a fixed finite number of other components through cables, each of which carries signals from a fixed finite alphabet. (2) when some of the inputs, and an equal number of outputs, are ``marked'''' (by the presentation of a certain signal), then after o(log n) steps (a time proportional to the ``diameter'''' of the network) the system will establish a set of disjoint paths from the marked inputs to the marked outputs.
regular resolution lower bounds for the weak pigeonhole principle. we prove that any regular resolution proof for the weak pigeon hole principle, with n holes and any number of pigeons, is of length &ohgr;(2^{n^{&egr;}}), (for some global constant &egr; > 0$).
the minimum consistent dfa problem cannot be approximated within any polynomial the minimum consistent dfa problem is that of finding a dfa with as few states as possible that is consistent with a given sample (a finite collection of words, each labeled as to whether the dfa found should accept or reject). assuming that p &ne; np, it is shown that for any constant k, no polynomial time algorithm can be guaranteed to find a consistent dfa of size optk, where opt is the size of a smallest dfa consistent with the sample. this result holds even if the alphabet is of constant size two, and if the algorithm is allowed to produce an nfa, a regular grammar, or a regular expression that is consistent with the sample. similar hardness results are described for the problem of funding small consistent linear grammars.
flowchart schemata with counters the translation of a specific flowchart schema with one counter into an equivalent flowchart schema without counters is described. this result leads easily to the general translation method from one-counter flowchart schemata to zero-counter flowchart schemata. some generalizations are then presented.
on the distribution of independent formulae of number theory it follows by g&ouml;del's incompleteness theorem [6] that any effective sound system of logic for elementary arithmetic must be incomplete. we show that in any effective sound system of logic for elementary arithmetic, there exist valid unprovable formulae that are quite small relative to the complexity of the logical system. also, such formulae are quite dense. in fact, the situation is about as bad as it could possibly be. that is , no infinite axiom system for elementary arithmetic can be much more compact than a listing of all the valid formulae. the unprovable formulae we construct express predicates in the classes &sgr2 and &pgr; 2 of the kleene arithmetic hierarchy [12]. the construction yields a set of short formulae, at least one of which must be valid and unprovable, but the construction does not tell us which one is valid and unprovable. we also construct small valid unprovable formulae expressing a relation in the class &pgr; 1 of the kleene arithmetic hierarchy. these latter formulae are not as small. we do not know how small the independent formulae corresponding to the class &pgr; 1 are. the constructions are based on the concept of a restricted oracle, first introduced in [10] and further developed in [11]. the proofs make use of the recent result of matijasevic [9] concerning the relationship between recursively enumerable sets and diophantine equations.
an efficient algorithm for solving word equations. we present the first dexptime algorithm which solves word equations i.e. finds a finite representation of all solutions of an equation in a free semigroup. we show how to use our approach to solve two new problems in pspace which deal with properties of the solution set of a word equation:deciding finiteness of the solution set,deciding boundness of the set of maximal exponents of periodicity of solutions. the approach can be generalized to solve in pspace three problems for expressible relations, namely the emptiness of the relation, finiteness of the relation and boundness of the set of maximal exponents of periodicity of elements of the relation.
approximation algorithms for hierarchical location problems. we formulate and (approximately) solve hierarchical versions of two prototypical problems in discrete location theory, namely, the metric uncapacitated k-median and facility location problems. our work yields new insights into hierarchical clustering, a widely used technique in data analysis. for example, we show that every metric space admits a hierarchical clustering that is within a constant factor of optimal at every level of granularity with respect to the average (squared) distance objective. a key building block of our hierarchical facility location algorithm is a constant-factor approximation algorithm for an ''incremental'' variant of the facility location problem; the latter algorithm may be of independent interest.
a hypercubic sorting network with nearly logarithmic depth a natural class of &ldquo;hypercubic&rdquo; sorting networks is defined. the regular structure of these sorting networks allows for elegant and efficient implementations on any of the so-called hypercubic networks (e.g., the hypercube, shuffle-exchange, butterfly, and cube-connected cycles). this class of sorting networks contains batcher's o(lg2 n)-depth bitonic sort, but not the o(lg n)-depth sorting network of ajtai, komlo&acute;s, and szemere&acute;di. in fact, no o(lg2 n)-depth compare-interchange sort was previously known for any of the hypercubic networks. in this paper, we prove the existence of a family of 2o((lg lg n)1/2) lg n-depth hypercubic sorting networks. note that this depth is o(lg1+&egr; n) for any constant &egr; > 0.
on the extremely fair treatment of probabilistic algorithms a proof system based on linear temporal logic for the qualitative verification of concurrent probabilistic programs is proposed. the concept of extreme fairness is introduced as an approximation to the notion of probabilistic executions. the proof system proposed is shown to be relatively complete with respect to validity over all extremely fair computations. the proof methodology is demonstrated by proving correctness of a new probabilistic algorithm for solving the mutual exclusion problem ([clp]).
a lower bound for integer multiplication with read-once branching programs. we prove that read-once branching programs computing integer multiplication require size $2^{\omega(\sqrt{n})}$. this is the first nontrivial lower bound for multiplication on branching programs that are not oblivious. by the appropriate problem reductions, we obtain the same lower bound for other arithmetic functions.
the communication complexity of pointer chasing: applications of entropy and sampling. we study the k-round two-party communication complexity of pointer chasing problem for fixed k. damm, jukna and sgall showed an upper bound of o(n \log ^{(k-1)} n) for this problem. we prove a matching lower bound; this improves the lower bound of \omega(n) shown by nisan and wigderson. this yields a corresponding improvement in the hierarchy results for bounded-depth monotone circuits.we consider the bit version of this problem, and show upper and lower bounds. this implies that there is an abrupt jump in complexity, from linear to superlinear, when the number of rounds is reduced below k/2. we also consider the s-paths version originally studied by klauck and obtain upper and lower bounds.the lower bounds are based on arguments using entropy. one of the main contributions of this work is a transfer lemma for distributions with high entropy; this should be of independent interest.
minimum spanning ellipsoids the notion of a minimum spanning ellipsoid in any dimension is explained. basic definitions and theorems provide the ideas for an algorithm to find the minimum spanning ellipsoid of a set of points, i.e., the ellipsoid of minimum volume containing the set. the run-time of the algorithm o (n2) independent of dimension, where n is the number of points.
new notions of security: achieving universal composability without trusted setup. we propose a modification to the framework of universally composable (uc) security [3]. our new notion involves comparing the real protocol execution with an ideal execution involving ideal functionalities (just as in uc-security), but allowing the environment and adversary access to some super-polynomial computational power. we argue the meaningfulness of the new notion, which in particular subsumes many of the traditional notions of security. we generalize the universal composition theorem of [3] to the new setting. then under new computational assumptions, we realize secure multi-party computation (for static adversaries) without a common reference string or any other set-up assumptions, in the new framework. this is known to be impossible under the uc framework.
a comparison of instruction sets for stack machines suppose you are approached by a computer designer who wants to select a machine architecture and instruction set that is desirable from a compiler writers standpoint. what would you recommend, and why? we give a limited answer to the above question. we focus on the computation of arithmetic expressions like a&minus;b+c. when computing a&minus;b we need different instructions depending on where a and b are to be found. on a programmable calculator for example, a or b may be on the stack, or stored in some memory register. we also need instructions that copy values from one place to another. algorithms that generate code for arithmetic expressions tend to treat general purpose registers as a stack. moreover, results about machines that perform all arithmetic in a hardware stack are directly applicable to machines with general purpose registers. we therefore start our study of instruction sets by looking at stack machines. we compare machines based on the number of instructions needed to compute a given expression. we then turn to algorithms that generate optimal programs for computing expressions on the various machines.
computing permutations with double-ended queues, parallel stacks and parallel queues a memory may be regarded as a computer with input, output and storage facilities, but with no explicit functional capability. the only possible outputs are permutations of a multiset of its inputs. thus the natural question to ask of a class of memories is, what permutations can its members compute? we are particularly interested here in switchyard networks studied by knuth [1968], even and itai [1971], and tarjan [1972], where the permutations are of the set of inputs, rather than of a multiset of them.
the power of negative thinking in multiplying boolean matrices we are interested in combinational circuits synthesized from and-gates and or-gates. we first show that n3 distinct and-gate inputs are needed to form the product of two boolean matrices, and hence o(n3) two-input and-gates are needed to compute the transitive closure of a boolean matrix. while this result has the flavor of kerr's (achievable)lower bound [kerr 1970] of n3+-gates for computing the min/+ product of integer-valued matrices using only min-gates and +-gates, the problem turns out on closer inspection to be considerably more subtle, and in fact we have been able to come only to within a factor of two of the best known upper bound of n3and-gates. secondly we use this result to study the effect on combinational circuts of not using not-gates inverters).
a practical decision method for propositional dynamic logic: preliminary report we give a new characterization of the set of satisfiable formulae of propositional dynamic logic (pdl) based on the method of tableaux. from it we derive a heuristically efficient goal-directed proof procedure and a complete axiom system for pdl. the proof procedure illustrates a striking connection between natural deduction and symbolic execution. the completeness proof for the axiom system incorporates a method for the automatic synthesis of invariants. we also augment dl with new modalities throughout, during, and preserves, supply a new semantic foundation for dl programs, and show how to extend the satisfiability characterizations for pdl to throughout.
dynamic algebras and the nature of induction dynamic algebras constitute the variety (equationally defined class) of models of the segerberg axioms for propositional dynamic logic. we obtain the following results (to within inseparability). (i) in any dynamic algebra * is reflexive transitive closure. (ii) every free dynamic algebra can be factored into finite dynamic algebras. (iii) every finite dynamic algebra is isomorphic to a kripke structure. (ii) and (iii) imply parikh's completeness theorem for the segerberg axioms. we also present an approach to treating the inductive aspect of recursion within dynamic algebras.
a characterization of the power of vector machines random access machines (rams) are usually defined to have registers that hold integers. while this captures in part the structure of a commercial computer, it overlooks an implementation-dependent feature of most binary oriented machines, namely their ability to operate bit by bit on the bit vectors used to represent integers. typical operations are bit-wise boolean operations (and, or, not, etc.) and shifts by an amount specified in some register. these operations are ideal for certain problems, such as dealing with sets represented as bit vectors, some parsing algorithms [4], propositional calculus theorem proving, and analysis of sorting networks. a ram so implemented we shall call a vector machine.
on average distortion of embedding metrics into the line and into l1. we introduce and study the notion of the average distortion of a nonexpanding embedding of one metric space into another. less sensitive than the multiplicative metric distortion, the average distortion captures well the global picture, and, overall, is a quite interesting new measure of metric proximity, related to the concentration of measure phenomenon. we establish close mutual relations between the mincut- maxflow gap in a uniform-demand multicommodity flow, and the average distortion of embedding the suitable (dual) metric into l1. these relations are exploited to show that the shortest-path metrics of special (e.g., planar, bounded treewidth, etc.) graphs embed into l1 with constant average distortion. the main result of the paper claims that this remains true even if l1 is replaced with the line. this result is further sharpened for graphs of a bounded treewidth.
relativized questions involving probabilistic algorithms let r @@@@ np be the collection of languages l such that for some polynomial time computable predicate p(x,y) and constant k, l &equil; {x|@@@@y, |y|&equil;|x|k,p(x,y)} &equil; {x|@@@@ at least 2|x|k&minus;1 values of y, |y|&equil;|x|k,p(x,y)}. let u @@@@ np be the collection of languages l such that for some polynomial time computable predicate p(x,y) and constant k, l &equil; {x|@@@@y,|y|&equil;|x|k,p(x,y)}&equil; {x|@@@@ unique y, |y|&equil;|x|k,p(x,y)}. let ra,ua, pa,npa,co-npa be the relativization of these classes with respect to an oracle a as in [ 5 ]. then for some oracle e (npe @@@@ co-npe) &equil; ue &equil; re &equil; pe @@@@ npe while for some other oracle d co-npd &equil; npd &equil; ud &equil; rd @@@@ pd.
provably good routing in graphs: regular arrays we examine the problem of routing wires on a vlsi chip where the nodes to be connected are arranged in a two-dimensional array. we develop provably good algorithms that find a solution close to the optimal one with high probability. our approximation algorithms solve the relevant 0-1 integer optimization problems by solving their relaxed versions and then rounding by an interesting probabilistic technique. one of our algorithms, using multicommodity flow, has applications to routing in circuit switching networks.
efficient routing in all-optical networks. communication in all-optical networks requires novel routing paradigms. the high bandwidth of the optic fiber is utilized through wavelength-division multiplexing : a single physical optical link can carry several logical signals, provided that they are transmitted on different wavelengths. we study the problem of routing a set of requests (each of which is a pair of nodes to be connected by a path) on sparse networks using a limited number of wavelengths, ensuring that different paths using the same wavelength never use the same physical link.
stochastic contention resolution with short delays. we study contention resolution protocols under a stochastic model of continuous request generation from a set of contenders. the performance of such a protocol is characterized by two parameters: the maximum arrival rate for which the protocol is stable and the expected delay of a request from arrival to service. known solutions are either unstable for any constant injection rate, or have polynomial (in the number of contenders) expected delay. our main contribution is a protocol that is stable for a constant injection rate, while achieving logarithmic expected delay. we extend our results to the case of multiple servers, with each request being targeted for a specific server. this is related to the optically connected parallel computer (or ocpc ) model. finally, we prove a lower bound showing that long delays are inevitable in a class of protocols including backoff-style protocols, if the arrival rate is large enough (but still smaller than 1).
absolutely parallel grammars and two-way deterministic finite-state transducers absolutely parallel grammars are defined and it is shown that the family of languages generated is equal to the family of languages generated by two-way deterministic finite-state transducers. furthermore it is shown that this family forms a full afl [4], is properly contained in the family of languages generated by two-way nondeterministic finite-state transducers (which is equal to the family of checking automata languages [8]) and properly contains the family of nonexpansive context-free languages [7].