waashk/dblp huggingface dataset:
operational and semantic equivalence between recursive programs in this paper, we show that two widely different notions of program equivalence coincide for the language of recursive definitions with simplification rules. the first one is the now classical equivalence for fixed-point semantics. the other one is purely operational in nature and is much closer to a programmer's intuition of program equivalence.
a fully dynamic reachability algorithm for directed graphs with an almost linear update time. we obtain a new fully dynamic algorithm for the reachability problem in directed graphs. our algorithm has an amortized update time of o(m+n log n) and a worst-case query time of o(n), where m is the current number of edges in the graph, and n is the number of vertices in the graph. each update operation either inserts a set of edges that touch the same vertex, or deletes an arbitrary set of edges. the algorithm is deterministic and uses fairly simple data structures. this is the first algorithm that breaks the o(n2) update barrier for all graphs with o(n2) edges.one of the ingredients used by this new algorithm may be interesting in its own right. it is a new dynamic algorithm for strong connectivity in directed graphs with an interesting persistency property. each insert operation creates a new version of the graph. a delete operation deletes edges from emphall versions. strong connectivity queries can be made on each version of the graph. the algorithm handles each update in o(mα(m,n)) amortized time, and each query in o(1) time, where α(m,n) is a functional inverse of ackermann's function appearing in the analysis of the union-find data structure. note that the update time of o(mα(m,n)), in case of a delete operation, is the time needed for updating all versions of the graph.
improved data structures for fully dynamic biconnectivity. we present fully dynamic algorithms for maintaining the biconnected components in general and plane graphs. a fully dynamic algorithm maintains a graph during a sequence of insertions and and deletions of edges or isolated vertices. let $m$ be the number of edges and $n$ be the number of vertices in a graph. the time per operation of the best known algorithms are $o(\sqrt{n})$ in general graphs and $o(\log n)$ in plane graphs for fully dynamic connectivity and $o(\min\{m^{2/3}, n\})$ in general graphs and $o(\sqrt{n})$ in plane graphs for fully dynamic biconnectivity. we improve the later running times to $(\min\{\sqrt{m}\log n, n \})$ in general graphs and $o(\log^{2}n)$ in plane graphs. our algorithm for general graphs can also find the biconnected components of all vertices in time $o(n)$. the update times in general graphs are amortized. this shows that the biconnected components of a graph can be dynamically maintained almost as efficiently as the connected components.
simple algebras are difficult let f be a finite field or an algebraic number field. in previous work we have shown how to find the basic building blocks (the radical and the simple components) of a finite dimensional algebra over f in polynomial time (deterministically in characteristic zero and las vegas in the finite case). here we address the more general problem of finding zero divisors in a. this problem is equivalent to finding a nontrivial common invariant subspace of a set of linear operators and includes, as a subcase, the problem of factoring polynomials over the field in question. in [fr] the problem of zero divisors has been reduced, in polynomial time (las vegas in the finite case), to the case of simple algebras. we show that, while zero divisors can be found in las vegas polynomial time if f is finite, the problem over the rationals might be substantially more difficult. we link the problem to hard number theoretic problems such as quadratic residuosity modulo a composite number. we show that assuming the generalized riemann hypothesis, there exists a randomized polynomial time reduction from quadratic residuosity to determining whether or not a given 4-dimensional algebra over q has zero divisors. it will follow that finding a pair of zero divisors is at least as hard as factoring squarefree integers. as for the finite case, we give a polynomial time las vegas method to construct explicit isomorphisms of matrix algebras. applications include an algorithm to solve the problem of finding common invariant subspaces for a set of linear operators. another application answers a question of w. m. kantor on permutation groups. finally, as another application of the grh, we mention a partial result on deterministic factoring over finite fields.
many birds with one stone: multi-objective approximation algorithms. we study network-design problems with multiple design objectives. in particular, we look at two cost measures to be minimized simultaneously: the total cost of the network and the maximum degree of any node in the network. our main result can be roughly stated as follows: given an integer $b$, we present approximation algorithms for a variety of network-design problems on an $n$-node graph in which the degree of the output network is $o(b \log (\frac{n}{b}))$ and the cost of this network is $o(\log n)$ times that of the minimum-cost degree-$b$-bounded network. these algorithms can handle costs on nodes as well as edges. moreover, we can construct such networks so as to satisfy a variety of connectivity specifications including spanning trees, steiner trees and generalized steiner forests. the performance guarantee on the cost of the output network is nearly best-possible unless $np = \tilde{p}$. we also address the special case in which the costs obey the triangle inequality. in this case, we obtain a polynomial-time approximation algorithm with a stronger performance guarantee. given a bound $b$ on the degree, the algorithm finds a degree-$b$-bounded network of cost at most a constant time optimum. there is no algorithm that does as well in the absence of triangle inequality unless $p = np$. we also show that in the case of spanning networks, we can simultaneously approximate within a constant factor yet another objective: the maximum cost of any edge in the network, also called the bottleneck cost of the network. we extend our algorithms to find tsp tours and $k$-connected spanning networks for any fixed $k$ that simultaneously approximate all these three cost measures.
abstract families of processors a &ldquo;processor&rdquo; is a turing-like automaton with auxiliary storage. an &ldquo;abstract family&rdquo; of processors (afp) consists of all processors that use the storage in the same way. properties common to all afp are derived. for a family of operations to be the output functions of some afp, it is necessary and sufficient that certain word-sets representing its members form a full afl (in the sense of ginsburg and greibach) closed under intersection and iterated finite substitution.2 for a family of word-sets to be the accepted languages of some afp, it is necessary and sufficient that it be a full afl closed under intersection and iterated finite substitution. the smallest full afl of this kind is the family of all recursively enumerable sets.
resolution lower bounds for the weak pigeonhole principle. we prove that any resolution proof for the weak pigeon hole principle, with n holes and any number of pigeons, is of length \omega(2^{n^{\epsilon}}), (for some constant \epsilon > 0). one corollary is that a certain propositional formulation of the statement np \not \subset p/poly does not have short resolution proofs.
a parallel repetition theorem. we show that a parallel repetition of any two-prover one-round proof system (mip(2,1)) decreases the probability of error at an exponential rate. no constructive bound was previously known. the constant in the exponent (in our analysis) depends only on the original probability of error and on the total number of possible answers of the two provers. the dependency on the total number of possible answers is logarithmic, which was recently proved to be almost the best possible [u. feige and o. verbitsky, proc.11th annual ieee conference on computational complexity, ieee computer society press, los alamitos, ca, 1996, pp. 70--76].
algorithmic aspects of vertex elimination we consider a graph-theoretic elimination process which is related to performing gaussian elimination on sparse symmetric and unsymmetric systems of linear equations. we discuss good algorithms for finding elimination orderings, showing that a generalization of breadth-first search, called lexicographic search, can be used to find perfect orderings in 0(n+e) time and minimal orderings in 0(ne) time, if the problem graph is undirected and has n vertices and e edges. we also give efficient (though slower) algorithms for generating such orderings on directed graphs. we claim that the minimum ordering problem for directed graphs is np-complete, and conjecture that it is also np-complete for undirected graphs. we include a brief discussion of the relation of elimination to transitive closure and discuss some unresolved, more general, issues.
tree-manipulating systems and church-rosser theorems we define a general class of tree-manipulating systems that includes many of the special cases from logic, linguistics, and automata theory. systems possessing what we call the &ldquo;church-rosser property&rdquo; are appropriate for evaluation or translation processes: the end result of a complete sequence of applications of the rules does not depend on the order in which the rules were applied. we sketch the theoretical and practical advantages of such flexibility. we derive general sufficient conditions for the church-rosser property and apply them to some important tree-manipulating systems. applications include tree transducers, the mccarthy formalism for recursive computation, and the classical church-rosser theorem for the full lambda-calculus.
extracting all the randomness and reducing the error in trevisan's extractors. we give explicit constructions of extractors which work for a source of any min-entropy on strings of length n. these extractors can extract any constant fraction of the min-entropy using o(log2 n) additional random bits, and can extract all the min-entropy using o(log3 n) additional random bits. both of these constructions use fewer truly random bits than any previous construction which works for all min-entropies and extracts a constant fraction of the min-entropy. we then improve our second construction and show that we can reduce the entropy loss to 2log(1/ε)+o(1) bits, while still using o(log3n) truly random bits (where entropy loss is defined as [(source min-entropy)+(# truly random bits used)-(# output bits)], and ε is the statistical difference from uniform achieved). this entropy loss is optimal up to a constant additive term. our extractors are obtained by observing that a weaker notion of "combinatorial design" suffices for the nisan-wigderson pseudorandom generator, which underlies the recent extractor of trevisan. we give near-optimal constructions of such "weak designs" which achieve much better parameters than possible with the notion of designs used by nisan-wigderson and trevisan. we also show how to improve our constructions (and trevisan's construction) when the required statistical difference ε from the uniform distribution is relatively small. this improvement is obtained by using multilinear error-correcting codes over finite fields, rather than the arbitrary error-correcting codes used by trevisan.
data graphs and addressing schemes: extended abstract a data graph is obtained from a data structure by masking out the specific data items at the nodes of the structure and concentrating only on the linkages in the structure. structural uniformities in data graphs can often be exploited to facilitate and systematize the accessing of nodes in the graph and the implementation of the graph in a computer. this paper presents a model for data graphs which can be used to study such uniformities. the main results reported characterize, in terms of structural uniformities, those classes of data graphs which can be implemented by &ldquo;relative addressing&rdquo; and by &ldquo;relocatable relative addressing&rdquo;.
lower bounds for matrix product, in bounded depth circuits with arbitrary gates. we prove super-linear lower bounds for the number of edges in constant depth circuits with n inputs and up to n outputs. our lower bounds are proved for all types of constant depth circuits, e.g., constant depth arithmetic circuits and constant depth boolean circuits with arbitrary gates. the bounds apply for several explicit functions, and, most importantly, for matrix product. in particular, we obtain the following results:we show that the number of edges in any constant depth arithmetic circuit for matrix product (over any field is super-linear in m^2 (where m \times m is the size of each matrix). that is, the lower bound is super-linear in the number of input variables. moreover, if the circuit is bilinear the result applies also for the case where the circuit gets for free any product of two linear functions.we show that the number of edges in any constant depth arithmetic circuit for the trace of the product of 3 matrices (over fields with characteristic~0) is super-linear in m^2. (note that the trace is a single-output function).we give explicit examples for n boolean functions f_1,\dots,f_ , such that any constant depth for f_1,...,f_n has a super-linear number of edges. the lower bound is proved also for circuits with arbitrary gates over any finite field. the bound applies for matrix product over finite fields as well as for several other explicit functions.
addressable data graphs: extended abstract this paper continues the study of the classes of data graphs which are implementable in a random access memory using &ldquo;relative addressing&rdquo; and &ldquo;relocatable realization&rdquo;, which was initiated in [1]. a new characterization of the class of rooted (&equil;relative addressable) data graphs yields simple and natural proofs of the preservation of rootedness under broad families of operations for composing data graphs. these positive results somewhat diminish the impact of the general unsolvability of detecting rootedness and free-rootedness (&equil;relocatability) in data graphs.
monotone circuits for matching require linear depth it is proven that monotone circuits computing the perfect matching function on n-vertex graphs require &ohgr;(n) depth. this implies an exponential gap between the depth of monotone and nonmonotone circuits.
hashing schemes for extendible arrays (extended arrays) the use of hashing schemes for storing extendible arrays is investigated. it is shown that extendible hashing schemes whose worst-case access behavior is close to optimal must utilize storage inefficiently; conversely, hashing schemes that utilize storage too conservatively are inevitably poor in expected access time. if requirements on the utilization of storage are relaxed slightly, then one can find rather efficient extendible hashing schemes. specifically, for any dimensionality of arrays, one can find extendible hashing schemes which at once utilize storage well [fewer than 2p storage locations need be set aside for storing arrays having p or fewer positions] and enjoy good access characteristics [expected access time is 0(1), and worst-case access time is 0(log log p) for p- or fewer-position arrays]. moreover, at the cost of only an additive increase in access time, storage demands can be decreased to (l+&egr;)p locations for arbitrary &egr;>0. in fact, if one will abide a more drastic degradation of access efficiency, one can lower storage demands to p+o(p) locations.
storage representations for tree-like data structures we review the motivation underlying the study of data encodings and the formal framework of the study. we then present a series of results whose main message is that (complete) trees are materially less congenial storage representations for tree-like data structures than they have been shown to be for array-like data structures. in response to these results, we propose a new data structure, called a dree, which we show to share the advantages of trees, but not to suffer their disadvantages, when used as a storage structure.
properties of deterministic top down grammars the class of context free grammars that can be deterministically parsed in a top down manner with a fixed amount of look-ahead is investigated. these grammars, called ll(k) grammars where k is the amount of look-ahead are first defined and a procedure is given for determining if a context free grammar is ll(k) for a given value of k. it is shown that &egr;-rules can be eliminated from an ll(k) grammar, at the cost of increasing the value of k by one, and a description is given of a canonical pushdown machine for recognizing ll(k) languages. it is shown that for each value of k there are ll(k+l) languages that are not ll(k) languages. it is shown that the equivalence problem is decidable for ll(k) grammars. additional properties are also given.
read-once branching programs, rectangular proofs of the pigeonhole principle and the transversal calculus. we investigate read-once branching programs for the following search problem: given a boolean m &#x00d7; n matrix with m > n, &#xfb01;nd either an all-zero row, or two 1&#x2019;s in some column. our primary motivation is that this models regular resolution proofs of the pigeonhole principle $$php^{m}_{n}$$, and that for m > n2 no lower bounds are known for the length of such proofs. we prove exponential lower bounds (for arbitrarily large m!) if we further restrict this model by requiring the branching program either to finish one row of queries before asking queries about another row (the row model) or put the dual column restriction (the column model).then we investigate a special class of resolution proofs for $$php^{m}_{n}$$ that operate with positive clauses of rectangular shape; we call this fragment the rectangular calculus. we show that all known upper bounds on the size of resolution proofs of $$php^{m}_{n}$$ actually give rise to proofs in this calculus and, inspired by this fact, also give a remarkably simple &#x201c;rectangular&#x201d; reformulation of the haken&#x2013;buss&#x2013;tur&#x00e1;n lower bound for the case m &#x226a; n2. finally we show that the rectangular calculus is equivalent to the column model on the one hand, and to transversal calculus on the other hand, where the latter is a natural proof system for estimating from below the transversal size of set families. in particular, our exponential lower bound for the column model translates both to the rectangular and transversal calculi.
nonserial dynamic programming is optimal we show that nonserial dynamic programming is optimal among one class of algorithms for an important class of discrete optimization problems. we consider discrete, multivariate, optimization problems in which the objective function is given as a sum of terms. each term is a function of only a subset of the variables. we first consider a class of optimization algorithms which eliminate suboptimal solutions by comparing the objective function on &ldquo;comparable&rdquo; partial solutions. a large, natural subclass of comparison algorithms in which the subproblems considered are either nested or nonadjacent (i.e., noninteracting) is then defined. it is shown that a variable-elimination procedure, nonserial dynamic programming, is optimal in an extremely strong sense among all algorithms in the subclass. the results' strong implications for choosing deterministic, adaptive, and nondeterministic algorithms for the optimization problem, for defining a complexity measure for a pattern of interactions, and for describing general classes of decomposition procedures are discussed. several possible extensions and unsolved problems are mentioned.
presburger arithmetic with bounded quantifier alternation this paper concerns both the complexity aspects of pa and the pragmatics of improving algorithms for dealing with restricted subcases of pa for uses such as program verification. we improve the cooper-presburger decision procedure and show that the improved version permits us to obtain time and space upper bounds for pa classes restricted to a bounded number of alternations of quantifiers. the improvement is one exponent less than the upper bounds for the decision problem for full pa. the pragmatists not interested in complexity bounds can read the results as substantiation of the intuitive feeling that the improvement to the cooper-presburger algorithm is a real, rather than ineffectual, improvement. (it can be easily shown that the bounds obtained here are not achievable using the cooper-presburger procedure).
uniform definability on finite structures with successor we study inductive and second-order definability on finite structures with successor and relate these notions to complexity theory. we introduce the dimension d of an inductive definition, directly related to the time complexity, representing the number of variables necessary to carry an induction. we will prove the following: connectivity is not uniformly unary &sgr;11 definable on graphs with successor, generalizing a similar result of fagin on graphs without successor. we will mention that similarly, hamiltonicity is neither unary-&sgr;11 nor unary-&pgr;11 on graphs with successor. these results show that disconnectivity is not inductive of dimension 1 although it is inductive of dimension 2, and that hamiltonicity is neither inductive nor co-inductive of dimension 1 on graphs with successor.
finding approximate separators and computing tree width quickly we show that for any fixed k, there is a linear-time algorithm which given a graph g either: (i) finds a cutset x of g with |x| &le; k such that no component of g&ndash;x contains more than 3/4|g&ndash;x| vertices, or (ii) determines that for any set x of vertices of g with |x| &le; k, there is a component of g&ndash;x which contains more than 2/3|g&ndash;x| vertices. this approximate separator algorithm can be used to develop and o(n log n algorithm for determining if g has a tree decomposition of width at most k (for fixed k) and finding such a tree decomposition if it exists.
stackelberg scheduling strategies. we study the problem of optimizing the performance of a system shared by selfish, noncooperative users. we consider the concrete setting of scheduling small jobs on a set of shared machines possessing latency functions that specify the amount of time needed to complete a job, given the machine load. we measure system performance by the total latency of the system. assigning jobs according to the selfish interests of individual users, who wish to minimize only the latency that their own jobs experience, typically results in suboptimal system performance. however, in many systems of this type there is a mixture of "selfishly controlled" and "centrally controlled" jobs. the congestion due to centrally controlled jobs will influence the actions of selfish users, and we thus aspire to contain the degradation in system performance due to selfish behavior by scheduling the centrally controlled jobs in the best possible way.we formulate this goal as an optimization problem via stackelberg games, games in which one player acts a leader (here, the centralized authority interested in optimizing system performance) and the rest as followers (the selfish users). the problem is then to compute a strategy for the leader (a stackelberg strategy) that induces the followers to react in a way that (approximately) minimizes the total latency in the system.in this paper, we prove that it is np-hard to compute an optimal stackelberg strategy and present simple strategies with provably good performance guarantees. more precisely, we give a simple algorithm that computes a strategy inducing a job assignment with total latency no more than a constant times that of the optimal assignment of all of the jobs; in the absence of centrally controlled jobs and a stackelberg strategy, no result of this type is possible. we also prove stronger performance guarantees in the special case where every machine latency function is linear in the machine load.