waashk/dblp huggingface dataset:
deadlock-free packet switching networks deadlock is one of the most serious system failures that can occur in a computer system or a network. deadlock states have been observed in existing computer networks emphasizing the need for carefully designed flow control procedures (controllers) to avoid deadlocks. such a deadlock-free controller is readily found if we allow it global information about the overall network state. generally, this assumption is not realistic, and we must resort to deadlock free local controllers using only packet and node information. we present here several types of such controllers, we study their relationship and give a proof of their optimality with respect to deadlock free controllers using the same set of local parameters.
non-approximability results for optimization problems on bounded degree instances. par>we prove some non-approximability results for restrictions of basic combinatorial optimization problems to instances of bounded &ldquo;degree&r dquo;or bounded &ldquo;width.&rdquo; specifically:we prove that the max 3sat problem on instances where each variable occurs in at most b clauses, is hard to approximate to within a factor $7/8 + o(1/\sqrt{b})$, unless $rp = np$. h\aa stad [18] proved that the problem is approximable to within a factor $7/8 + 1/64b$ in polynomial time, and that is hard to approximate to within a factor $7/8 +1/(\log b)^{&ohgr;(1)}$. our result uses a new randomized reduction from general instances of max 3sat to bounded-occurrences instances. the randomized reduction applies to other max snp problems as well.we observe that the set cover problem on instances where each set has size at most b is hard to approximate to within a factor $\ln b - o(\ln\ln b)$ unless $p=np$. the result follows from an appropriate setting of parameters in feige's reduction [11]. this is essentially tight in light of the existence of $(1+\ln b)$-approximate algorithms [20, 23, 9]we present a new pcp construction, based on applying parallel repetition to the ``inner verifier,'' and we provide a tight analysis for it. using the new construction, and some modifications to known reductions from pcp to hitting set, we prove that hitting set with sets of size b is hard to approximate to within a factor $b^{1/19}$. the problem can be approximated to within a factor b [19], and it is the vertex cover problem for b=2. the relationship between hardness of approximation and set size seems to have not been explored before. we observe that the independent set problem on graphs having degree at most b is hard to approximate to within a factor $b/2^{o(sqrt{\log b})}$, unless p = np. this follows from a comination of results by clementi and trevisan [28] and reingold, vadhan and wigderson [27]. it had been observed that the problem is hard to approximate to within a factor $b^{&ohgr; (1)}$ unless p=np [1]. an algorithm achieving factor $o (b)$ is also known [21, 2, 30, 16}.
on uniform amplification of hardness in np. we continue the study of amplification of average-case complexity within np, and we focus on the uniform case.we prove that if every problem in np admits an efficient uniform algorithm that (averaged over random inputs and over the internal coin tosses of the algorithm) succeeds with probability at least 1 ⁄ 2 +1 (log n )α, then for every problem in np there is an efficient uniform algorithm that succeeds with probability at least 1 - 1 poly(n). above, α > 0 is an absolute constant.previously, trevisan (focs'03) presented a similar redution between success 3⁄4 + 1 (log n) and 1 - 1 (log n)α stronger reductions, due to o'donnell (stoc'02) and healy, vadhan and viola (focs'04) are known in the non-uniform case.
an o(log n log log n) space algorithm for undirected st-connectivity. we present a deterministic o(log n log log n) space algorithm for undirected st-connectivity. it is based on the deterministic erew algorithm of chong and lam [6] and uses the universal exploration sequences for trees constructed by koucký [13]. our result improves the o(log4/3 n) bound of armoni et al.\ [2] and is a big step towards the optimal o(log n). independently of our result and using a different set of techniques, the optimal bound was achieved by reingold [18].
probabilistic analysis of bandwidth minimization algorithms we study the probabilistic performance of heuristic algorithms for the np-complete bandwidth minimization problem. let (equation) be a graph with (equation). define the bandwidth of g by (equation) where &tgr; ranges over all permutations on v. let a be a bandwidth minimization algorithm and let a (g) denote the bandwidth of the layout produced by a on the graph g. we say that a is a level algorithm if for all graphs (equation) the layout &tgr; produced by a on g satisfies (equation) the level algorithms were first introduced by cuthill and mckee [1] and have proved quite successful in practice. however, it is easy to construct examples that cause the level algorithms to perform poorly. consequently worst-case analysis provides no insight to their practical success. in this paper we use probabilistic analysis in order to gain an understanding of these algorithms and to help us design better algorithms. let (equation) be the graph defined by (equation) and let g be a random spanning subgraph of bn&darr; in which the vertices have been randomly re-labelled. we show that if a, is a level algorithm and (equation) then (equation) almost always holds, where &egr; is any positive constant. we also introduce a class of algorithms called the modified level algorithms and show that if a ' is a modified level algorithm and (equation) then (equation) almost always holds. a particular modified level algorithm mla1 is analyzed and we show that when (equation). we also study several other properties of random subgraphs of bn&darr;.
a decision method for the equivalence of some non-real-time deterministic pushdown automata a generalization of the alternate stacking procedure of valiant for deciding the equivalence of some deterministic pushdown automata (dpda) is introduced. to analyze the power of the generalized procedure we define a subclass of dpda's, called the proper dpda's. this class properly contains the non-singular dpda's and the real time strict dpda's, and the corresponding class of languages properly contains the real time strict deterministic languages. the equivalence problem for proper automata is reducible to the problem of deciding whether or not an automaton is proper. the main result of the paper is that the generalized procedure yields an equivalence test for proper dpda's, at least one of which is also a finite-turn machine.
lalr(k) testing is pspace-complete the problem of testing whether or not an arbitrary context-free grammar is lalr(k) for a fixed integer k &ge; 1 (i.e. only the subject grammar is a problem parameter) is shown to be pspace-complete. the result is in contrast with testing the membership in several other easily parsed classes of grammars, such as lr(k), slr(k), lc(k) and ll(k) grammars, for which deterministic polynomial time membership tests are known. the pspace-hardness of the problem is proved using a transformation from the finite state automaton non-universality problem. a nondeterministic algorithm for constructing sets of lr(k) items leads to a polynomially space bounded algorithm for lalr(k) testing.
the inherent ambiguity partial algorithm problem for context free languages it is shown that there is no &ldquo;partial algorithm&rdquo; (effective procedure that may fail to terminate) by which, given a context free grammar, one can always find an unambiguous context free grammar generating the same language if such an unambiguous grammar exists. the argument turns on the degree of unsolvability of the inherent ambiguity problem for context free languages.
three theorems on abstract families of languages (1) if every set in @@@@ is a subset of a* and the empty word belongs to one of them, then 7(@@@@)&equil;&7circ; (@@@@). one consequence is that &7circ;(l) is always principal for l &le; a*. (2) on the other hand, there is a language l &le; a*b* such that &7circ;(l) is not principal. (3) there are subsets j and k of a* such that 7(j) @@@@ 7(k) is not principal.
pseudo-random generators for all hardnesses. we construct the first pseudo-random generators with logarithmic seed length that convert s bits of hardness into s^{\omega(1)} bits of 2-sided pseudo-randomness, for any s. this improves [isw00] and gives a direct proof of the optimal hardness vs. randomness tradeoff in [su01]. a key element in our construction is an augmentation of the standard low-degree extension encoding that exploits the field structure of the underlying space in a new way.
parallel scheduling of programs in a restricted model of computation the purpose of this paper is to present the basis of an automata-theoretic model which treats the concept of &ldquo;schedule&rdquo; for programs which admit a (predefined) degree of parallelism. after a brief review of notational conventions (section 2), the class of representing automata will be introduced as a device for treating a program's control structure. in section 4, since the definition of schedules is non-constructive in the sense that no procedure is given for passing from a representing automaton to a schedule, a particular kind of schedule with such an effective presentation is given and shown to be optimal in the natural sense of optimality defined in section 6. section 5 presents one of the many possible interpretation schemes for our model; this scheme is used to justify some of the claims we have made in this section. finally, we examine some elementary conditions, on a program's control structure which affect the existence of optimal schedules which have finite, explicit presentation.
the recognition of series parallel digraphs we present an algorithm that recognizes the class of general series parallel digraphs and runs in time proportional to the size of its input. to perform this recognition task it is necessary to compute the transitive reduction and transitive closure of any general series parallel digraph. our analysis is based on the relationship between general series parallel digraphs and a class of well known models of electrical networks.
quantum computers that can be simulated classically in polynomial time. a model of quantum computation based on unitary matrix operations was introduced by feynman and deutsch. it has been asked whether the power of this model exceeds that of classical turing machines. we show here that a significant class of these quantum computations can be simulated classically in polynomial time. in particular we show that two-bit operations characterized by 4 \times 4 matrices in which the sixteen entries obey a set of five polynomial relations can be composed according to certain rules to yield a class of circuits that can be simulated classically in polynomial time. this contrasts with the known universality of two-bit operations, and demonstrates that efficient quantum computation of restricted classes is reconcilable with the polynomial time turing hypothesis. in other words it is possible that quantum phenomena can be used in a scalable fashion to make computers but that they do not have superpolynomial speedups compared to turing machines for any problem. the techniques introduced bring the quantum computational model within the realm of algebraic complexity theory. in a manner consistent will one view of quantum physics, the wave function is simulated deterministically, and randomization arises only in the course of making measurements. the results generalize the quantum model in that they do not require the matrices to be unitary. in a different direction these techniques also yield deterministic polynomial time algorithms for the decision and parity problems for certain classes of read-twice boolean formulae. all our results are based on the use of gates that are defined in terms of their graph matching properties.
the decidability of equivalence for deterministic finite-turn pushdown automata a deterministic pushdown automaton (dpda) is described as finite-turn if there is a bound on the number of times the direction of the stack movement can change in the set of all derivations from the starting configuration. the purpose of this paper is to show that there exists a procedure for deciding whether two such finite-turn machines recognize the same language. by virtue of a direct correspondence between a restricted class of one-turn dpda and deterministic two-tape acceptors (valiant (1973)), our proof also provides a solution to the equivalence problem for the latter, alternative to that of bird (1973). since some of the ideas we introduce are not related exclusively to the finite-turn property, or even pushdown machines, it is hoped that our methods can be adapted for constructing equivalence tests for other classes of deterministic automata. our main technique can be regarded as a generalization in several directions of one introduced by rosenkrantz and stearns (1970). they consider a class of pushdown automata for which a natural valuation can be placed on each stack segment, and deduce that for any input word, two equivalent machines in that class must have closely related stack movements. they show how, under such circumstances, for any two machines a single pushdown automaton can be constructed to simulate them both, and used to decide their equivalence. what we shall show is that even for a class with no such stack valuation known, and in which two equivalent machines can have totally dissimilar stack movements, pushdown automata, now nondeterministic, can be found to perform the required simulations.
on non-linear lower bounds in computational complexity the purpose of this paper is to explore the possibility that purely graph-theoretic reasons may account for the superlinear complexity of wide classes of computational problems. the results are therefore of two kinds: reductions to graph theoretic conjectures on the one hand, and graph theoretic results on the other. we show that the graph of any algorithm for any one of a number of arithmetic problems (e.g. polynomial multiplication, discrete fourier transforms, matrix multiplication) must have properties closely related to concentration networks.
universal circuits (preliminary report) we show that there is a combinational (acyclic) boolean circuit of complexity 0(slog s), that can be made to compute any boolean function of complexity s by setting its specially designated set of control inputs to appropriate fixed values. we investigate the construction of such &ldquo;universal circuits&rdquo; further so as to exhibit directions in which refinements of the asymptotic multiplicative constant factor in the complexity bound can be found. in this pursuit useful detailed guidance is provided by available lower bound arguments. in the final section we discuss some other problems in computational complexity that can be related directly to the graph-theoretic ideas behind our constructions. for motivation we start by illustrating some of the applications of universal circuits themselves.
negation can be exponentially powerful among the most remarkable algorithms in algebra are strassen's algorithm for the multiplication of matrices and the fast fourier transform method for the convolution of vectors. for both of these problems the definition suggests an obvious algorithm that uses just the monotone operations + and &times;. schnorr [18] has shown that these algorithms, which use &thgr;(n3) and &thgr;(n2) operations respectively, are essentially optimal among algorithms that use only these monotone operations. by using subtraction as an additional operation and exploiting cancellations of computed terms in a very intricate way strassen showed that a faster algorithm requiring only o(n2.81) operations is possible. the fft method for convolution achieves o(nlog n) complexity in a similar fashion. the question arises as to whether we can expect even greater gains in computational efficiency by such judicious use of cancellations. in this paper we give a positive answer to this, by exhibiting a problem for which an exponential speedup can be attained using {+,&minus;,&times;} rather than just {+,&times;} as operations. the problem in question is the multivariate polynomial associated with perfect matchings in planar graphs. for this a fast algorithm is implicit in the pfaffian technique of fisher and kasteleyn [6,8]. the main result we provide here is the exponential lower bound in the monotone case.
completeness classes in algebra in the theory of recursive functions and computational complexity it has been demonstrated repeatedly that the natural problems tend to cluster together in &ldquo;completeness classes&rdquo;. these are families of problems that (a) are computationally interreducible and (b) are the hardest members of some computationally defined class. the aim of this paper is to demonstrate that for both algebraic and combinatorial problems this phenomenon exists in a form that is purely algebraic in both of the respects (a) and (b). such computational consequences as np-completeness are particular manifestations of something more fundamental. the core of the paper is self-contained, consisting as it does essentially of the two notions of &ldquo;p-definability&rdquo; and the five algebraic relations that are proved as theorems. in the remainder our aim is to elucidate the computational consequences of these basic results. hence in the auxiliary propositions and discussion for convenience we do assume familiarity with algebraic and boolean complexity theory.
exponential lower bounds for restricted monotone circuits in this paper we consider monotone boolean circuits with three alternations, in the order &ldquo;or&rdquo;, &ldquo;and&rdquo;, &ldquo;or.&rdquo; whenever the number of alternations is limited to a fixed constant the formula and circuit size measures are polynomially related to each other. we shall therefore refer to this measure interchangeably as &sgr;&pgr;&sgr;-formula size or &sgr;&pgr;&sgr;-circuit size. we shall prove that any such circuit or formula for detecting the existence of cliques in an n-node graph has at least 2&ohgr;(n&egr;) gates for some &egr; > 0 independent of n.
a theory of the learnable humans appear to be able to learn new concepts without needing to be programmed explicitly in any conventional sense. in this paper we regard learning as the phenomenon of knowledge acquisition in the absence of explicit programming. we give a precise methodology for studying this phenomenon from a computational viewpoint. it consists of choosing an appropriate information gathering mechanism, the learning protocol, and exploring the class of concepts that can be learnt using it in a reasonable (polynomial) number of steps. we find that inherent algorithmic complexity appears to set serious limits to the range of concepts that can be so learnt. the methodology and results suggest concrete principles for designing realistic learning systems.
universal schemes for parallel communication in this paper we isolate a combinatorial problem that, we believe, lies at the heart of this question and provide some encouragingly positive solutions to it. we show that there exists an n-processor realistic computer that can simulate arbitrary idealistic n-processor parallel computations with only a factor of o(log n) loss of runtime efficiency. the main innovation is an o(log n) time randomized routing algorithm. previous approaches were based on sorting or permutation networks, and implied loss factors of order at least (log n)2.
np is as easy as detecting unique solutions for all known np-complete problems the number of solutions in instances having solutions may vary over an exponentially large range. furthermore, most of the well-known ones, such as satisfiability, are parsimoniously interreducible, and these can have any number of solutions between zero and an exponentially large number. it is natural to ask whether the inherent intractability of np-complete problems is caused by this wide variation. in this paper we give a negative answer to this using randomized reductions. we show that the problems of distinguishing between instances of sat having zero or one solution, or finding solutions to instances of sat having unique solutions, are as hard as sat itself. several corollaries about the difficulty of specific problems follow. for example if the parity of the number of solutions of sat can be computed in rp then np = rp. some further problems can be shown to be hard for np or dp via randomized reductions.
provably fast integer factoring with quasi-uniform small quadratic residues finding small quadratic residues modulo n, when n is a large composite number of unknown factorisation is almost certainly a computationally hard problem. this problem arises in a natural way when factoring n by the use of congruences of squares. we construct here a polynomial-time algorithm based on the use of lattices, which finds in a near uniform way quadratic residues mod n that are smaller than o(n2/3). in this way, we derive a class of integer factorisation algorithms, the fastest of which provides the best rigorously established probabilistic complexity bound for integer factorisation algorithms.
the complexity of relational query languages (extended abstract) two complexity measures for query languages are proposed. data complexity is the complexity of evaluating a query in the language as a function of the size of the database, and expression complexity is the complexity of evaluating a query in the language as a function of the size of the expression defining the query. we study the data and expression complexity of logical languages - relational calculus and its extensions by transitive closure, fixpoint and second order existential quantification - and algebraic languages - relational algebra and its extensions by bounded and unbounded looping. the pattern which will be shown is that the expression complexity of the investigated languages is one exponential higher then their data complexity, and for both types of complexity we show completeness in some complexity class.
automata theoretic techniques for modal logics of programs (extended abstract) we present a new technique for obtaining decision procedures for modal logics of programs. the technique centers around a new class of finite automata on infinite trees for which the emptiness problem can be solved in polynomial time. the decision procedures then consist of constructing an automaton af for a given formula f, such that af accepts some tree if and only if f is satisfiable. we illustrate our technique by giving an exponential decision procedure for deterministic propositional dynamic logic and a variant of the &mgr-calculus of kozen.
distribution functions of probabilistic automata. each probabilistic automaton m over an alphabet $\cal a$ defines a probability measure $\prob_m$ on the set of all finite and infinite words over $\cal a$. we can identify a k letter alphabet $\cal a$ with the set {0,1,&hellip;,k-1}, and, hence, we can consider every finite or infinite word w over $\cal a$ as a radix k expansion of a real number x(w) in the interval [0,1]. this makes x(w) a random variable and the distribution function of m is defined as usual: f(x):=\prob_m{w : x(w)}. utilizing the fixed--point semantics (denotational semantics), extended to probabilistic computations, we investigate the distribution functions of probabilistic automata in detail. automata with continuous distribution functions are characterized. by a new, and much more easier method, it is shown that the distribution function f(x) is an analytic function if it is a polynomial. finally, answering a question posed by d. knuth and a. yao, we show that a polynomial distribution function f(x) on [0,1] can be generated by a probabilistic automaton iff all the roots of f'(x)=0 in this interval, if any, are rational numbers. for this, we define two dynamical systems on the set of polynomial distributions and study attracting fixed points of random composition of these two systems.