waashk/dblp huggingface dataset:
conditions on input vectors for consensus solvability in asynchronous distributed systems. this article introduces and explores the condition-based approach to solve the consensus problem in asynchronous systems. the approach studies conditions that identify sets of input vectors for which it is possible to solve consensus despite the occurrence of up to f process crashes. the first main result defines acceptable conditions and shows that these are exactly the conditions for which a consensus protocol exists. two examples of realistic acceptable conditions are presented, and proved to be maximal, in the sense that they cannot be extended and remain acceptable. the second main result is a generic consensus shared-memory protocol for any acceptable condition. the protocol always guarantees agreement and validity, and terminates (at least) when the inputs satisfy the condition with which the protocol has been instantiated, or when there are no crashes. an efficient version of the protocol is then designed for the message passing model that works when f < n/2, and it is shown that no such protocol exists when f &ge; n/2. it is also shown how the protocol's safety can be traded for its liveness.
expanding graphs and the average-case analysis of algorithms for matchings and related problems hall's theorem states that a bipartite graph has a perfect matching if and only if every set of vertices has an equal number of neighbours. equivalently, it states that every non-maximum matching has an augmenting path if the graph is an expander with expansion 1. we use this insight to demonstrate that if a graph is an expander with expansion more than one than every non-maximum matching has a short augmenting path and, therefore, the bipartite matching algorithm performs much better on such graphs than in the worst case. we then apply this idea to the average case analysis of various augmenting path algorithms and to the approximation of the permanent. in particular, we demonstrate that the following algorithms perform much better on the average than in the worst case. in fact, they will rarely exhibit their worst-case running times. hopcroft-karp's algorithm for bipartite matchings. micali-vazirani's and even-kariv's algorithms for non-bipartite matchings. gabow-tarjan's parallel algorithm for bipartite matchings. dinic's algorithm for k-factors and 0-1 network flows. jerrum-sinclair's approximation scheme for the permanent. it seems rather surprising that the algorithms which are the fastest known for worst-case inputs also do exceedingly on almost every graph.
on optimal slicing of parallel programs. optimal program slicing determines for a statement s in a program &pgr; whether or not s affects a specified set of statements, given that all conditionals in &pgr; are interpreted as non-deterministic choices.only recently, it has been shown that reachability of program points and hence also optimal slicing is undecidable for multi-threaded programs with (parameterless) procedures and synchronization [23]. here, we sharpen this result by proving that slicing remains undecidable if synchronization is abandoned---although reachability becomes polynomial. moreover, we show for multi-threaded programs without synchronization, that slicing stays pspace-hard when procedure calls are forbidden, and becomes np-hard for loop-free programs. since the latter two problems can be solved in pspace and np, respectively, even in presence of synchronization, our new lower bounds are tight.finally, we show that the above decidability and lower bound properties equally apply to other simple program analysis problems like copy constant propagation and true liveness of variables. this should be contrasted to the problems of strong copy constant propagation and (ordinary) liveness of variables for which polynomial algorithms have been designed [15, 14, 24].
pushdown automata, graphs, ends, second-order logic, and reachability problems we have discovered a very strong connection between certain areas of theoretical computer science&mdash;the theory of context-free languages and pushdown automata, tiling problems, cellular automata, and vector addition systems&mdash;and certain concepts from group theory, topology, and second-order logic. we use these concepts to investigate a rather wide class of graphs which we call context-free graphs. using the results obtained and rabin's theorem that the monadic second-order theory of the infinite binary tree is decidable, we are able to show that the monadic second-order theory of any context-free graph is decidable. cellular automata and vector addition systems are usually considered as involving the grid of integer lattice points in n-dimensional space. we show that such systems make sense on a very general class of graphs and, in contrast to the classical case, all the relevant algorithmic problems concerning such systems are solvable on context-free graphs.
searching a two key table under a single key we present a method for arranging an arbitrary 2-key table as an n by 2 array such that a search can be performed under either key in o(lg2n lglg n) time. this is in sharp contrast with an &ohgr;(&radic;n) lower bound for the problem under a model in which all comparisons must involve the value being searched for.
implicit data structures (preliminary draft) we consider representations of data structures in which the relative ordering of the values stored is implicit in the pattern in which the elements are retained, rather than explicit in pointers. several implicit schemes for storing data are introduced to permit efficient implementation of the instructions insert, delete and find. &thgr;(@@@@n) basic operations are shown to be necessary and sufficient, in the worst case, to perform these instructions provided that the data elements are kept in some fixed partial order. we demonstrate, however, that further improvements can be made if an arrangement other than a fixed partial order is used. a structure, based on a fixed partial order, is introduced to facilitate multiple key searches. this structure, together with the retrieval scheme based upon it, is shown to be within a constant factor of the optimal one based on a partial order.
communication preserving protocols for secure function evaluation. a secure function evaluation protocol allows two parties to jointly compute a function f(x,y) of their inputs in a manner not leaking more information than necessary. a major result in this field is: &ldquo;any function f that can be computed using polynomial resources can be computed securely using polynomial resources&rdquo; (where &ldquo;resources&rdquo; refers to communication and computation). this result follows by a general transformation from any circuit for f to a secure protocol that evaluates f. although the resources used by protocols resulting from this transformation are polynomial in the circuit size, they are much higher (in general) than those required for an insecure computation of f.we propose a new methodology for designing secure protocols, utilizing the communication complexity tree (or branching program) representation of f. we start with an efficient (insecure) protocol for f and transform it into a secure protocol. in other words, ``any function f that can be computed using communication complexity c can be can be computed securely using communication complexity that is polynomial in c and a security parameter''. we show several simple applications of this new methodology resulting in protocols efficient either in communication or in computation. in particular, we exemplify a protocol for the millionaires problem, where two participants want to compare their values but reveal no other information. our protocol is more efficient than previously known ones in either communication or computation.
balanced metric labeling. we define the balanced metric labeling problem, a generalization of the metric labeling problem, in which each label has a capacity, i.e., at most l vertices can be assigned to it. the balanced metric labeling problem is a generalization of fundamental problems in the area of approximation algorithms, e.g., arrangements and balanced partitions of graphs. it is also motivated by resource limitations in certain practical scenarios. we focus on the case where the given metric is uniform and note that this case alone encompasses various well-known graph partitioning problems. we present the first (pseudo) approximation algorithm for this problem, achieving for any ε, 0 < ε < 1, an approximation factor of o((ln n)/ε), while assigning at most min {o(ln k)/1 - ε, l + 1| ( 1 + ε) l vertices to each label (k is the number of labels). our approximation algorithm is based on a novel randomized rounding of a linear programming formulation that combines an embedding of the graph in a simplex together with spreading metrics and additional constraints that strengthen the formulation. our randomized rounding technique uses both a randomized metric decomposition technique and a randomized label assignment technique. at the heart of our approach is the fact that only limited dependency is created between the labels assigned to different vertices, allowing us to bound the expected cost of the solution and the number of vertices assigned to each label, simultaneously. we note that the number of vertices assigned to each label is bounded via a new inequality of janson[15] for tail bounds of (partly) dependent random variables.
what can be computed locally? the purpose of this paper is a study of computation that can be done locally in a distributed network, where "locally" means within time (or distance) independent of the size of the network. locally checkable labeling (lcl) problems are considered, where the legality of a labeling can be checked locally (e.g., coloring). the results include the following: there are nontrivial lcl problems that have local algorithms. there is a variant of the dining philosophers problem that can be solved locally. randomization cannot make an lcl problem local; i.e., if a problem has a local randomized algorithm then it has a local deterministic algorithm. it is undecidable, in general, whether a given lcl has a local algorithm. however, it is decidable whether a given lcl has an algorithm that operates in a given time $t$. any lcl problem that has a local algorithm has one that is order-invariant (the algorithm depends only on the order of the processor ids).
anti-presistence: history independent data structures. many data structures give away much more information than they were intended to. whenever privacy is important, we need to be concerned that it might be possible to infer information from the memory representation of a data structure that is not available through its &ldquo;legitimate&rdquo; interface. word processors that quietly maintain old versions of a document are merely the most egregious example of a general problem.we deal with data structures whose current memory representation does not reveal their history. we focus on dictionaries, where this means revealing nothing about the order of insertions or deletions. our first algorithm is a hash table based on open addressing, allowing o(1) insertion and search. we also present a history independent dynamic perfect hash table that uses space linear in the number of elements inserted and has expected amortized insertion and deletion time o(1). to solve the dynamic perfect hashing problem we devise a general scheme for history independent memory allocation. for fixed-size records this is quite efficient, with insertion and deletion both linear in the size of the record. our variable-size record scheme is efficient enough for dynamic perfect hashing but not for general use. the main open problem we leave is whether it is possible to implement a variable-size record scheme with low overhead.
universal one-way hash functions and their cryptographic applications we define a universal one-way hash function family, a new primitive which enables the compression of elements in the function domain. the main property of this primitive is that given an element x. we prove constructively that universal one-way hash functions exist if any 1-1 one-way functions exist. among the various applications of the primitive is a one-way based secure digital signature scheme, a system which is based on the existence of any 1-1 one-way functions and is secure against the most general attack known. previously, all provably secure signature schemes were based on the stronger mathematical assumption that trapdoor one-way functions exist.
a polynomial approximation algorithm for the minimum fill-in problem. in the minimum fill-in problem, one wishes to find a set of edges of smallest size, whose addition to a given graph will make it chordal. the problem has important applications in numerical algebra and has been studied intensively since the 1970s. we give the first polynomial approximation algorithm for the problem. our algorithm constructs a triangulation whose size is at most eight times the optimum size squared. the algorithm builds on the recent parameterized algorithm of kaplan, shamir, and tarjan for the same problem.for bounded degree graphs we give a polynomial approximation algorithm with a polylogarithmic approximation ratio. we also improve the parameterized algorithm.
on learning boolean functions this paper deals with the learnability of boolean functions. an intuitively appealing notion of dimensionality is developed and used to identify the most general class of boolean function families that are learnable from polynomially many positive examples with one-sided error. it is then argued that although bounded dnf expressions lie outside this class, they must have efficient learning algorithms as they are well suited for expressing many human concepts. a framework that permits efficient learning of bounded dnf functions is identified.
on communication over an entanglement-assisted quantum channel. shared entanglement is a resource available to parties communicating over a quantum channel, much akin to public coins in classical communication protocols: the two parties may be given some number of quantum bits jointly prepared in a fixed superposition, prior to communicating with each other. the quantum channel is then said to be "entanglement-assisted."shared randomness does not help in the transmission of information from one party to another. moreover, it does not significantly reduce the classical complexity of computing functions vis-a-vis private-coin protocols. on the other hand, prior entanglement leads to startling phenomena such as "quantum teleportation" and "superdense coding." the problem of characterising the power of prior entanglement has baffled many researchers, especially in the setting of bounded-error protocols. it is open whether it leads to more than a factor of two savings (using superdense coding) or more than an additive~o(\log n) savings (when used to create shared randomness). few lower bounds are known for communication problems in this setting, and are all derived using sophisticated information-theoretic techniques.in this paper, we focus on the most basic problem in the setting of communication over an entanglement-assisted quantum channel, that of communicating classical bits from one party to another. we derive optimal bounds on the number of quantum bits required for this task, for any given probability of error.
linear time low tree-width partitions and algorithmic consequences. classes of graphs with bounded expansion have been introduced in [15], [12]. they generalize both proper minor closed classes and classes with bounded degree.for any class with bounded expansion c and any integer p there exists a constant n(c,p) so that the vertex set of any graph g ∈ c may be partitioned into at most n(c,p) parts, any i ≤ p parts of them induce a subgraph of tree-width at most (i-1) [12] (actually, of tree-depth [16] at most i, what is sensibly stronger). such partitions are central to the resolution of homomorphism problems like restricted homomorphism dualities [14].we give here a simple algorithm to compute such partitions and prove that if we restrict the input graph to some fixed class c with bounded expansion, the running time of the algorithm is bounded by a linear function of the order of the graph (for fixed c and p).this result is applied to get a linear time algorithm for the subgraph isomorphism problem with fixed pattern and input graphs in a fixed class with bounded expansion.more generally, let φ be a first order logic sentence. we prove that any fixed graph property of type "∃x: (|x| ≤ p) ⇿(g[x]=φ)" may be decided in linear time for input graphs in a fixed class with bounded expansion.
zero knowledge with efficient provers. we prove that every problem in np that has a zero-knowledge proof also has a zero-knowledge proof where the prover can be implemented in probabilistic polynomial time given an np witness. moreover, if the original proof system is statistical zero knowledge, so is the resulting efficient-prover proof system. an equivalence of zero knowledge and efficient-prover zero knowledge was previously known only under the assumption that one-way functions exist (whereas our result is unconditional), and no such equivalence was known for statistical zero knowledge. our results allow us to translate the many general results and characterizations known for zero knowledge with inefficient provers to zero knowledge with efficient provers.
binary search trees of bounded balance a new class of binary search trees, called trees of bounded balance, is introduced. these trees are easy to maintain in their form despite insertions and deletions of nodes, and the search time is only moderately longer than in completely balanced trees. trees of bounded balance differ from other classes of binary search trees in that they contain a parameter which can be varied so the compromise between short search time and infrequent restructuring can be chosen arbitrarily.
crew prams and decision trees this paper gives a full characterization of the time needed to compute a boolean function on a crew pram with an unlimited number of processors. the characterization is given in terms of a new complexity measure of boolean functions: the &ldquo;block sensitivity&rdquo;. this measure is a generalization of the well know &ldquo;critical sensitivity&rdquo; measure (see [w], [cdr], [si]). the block sensitivity is also shown to relate to the boolean decision tree complexity, and the implication is that the decision tree complexity also fully characterizes the crew pram complexity. this solves an open problem of [w]. our results imply that changes in the instruction set of the processors or in the capacity of the shared memory cells do not change by more than a constant factor the time required by a crew pram to compute any boolean function. moreover, we even show that a seemingly weaker version of a crew pram, the crow pram ([dr]), can compute functions as quickly as a general crew pram. this solves an open problem of [dr]. finally, our results have implications regarding the power of randomization in the boolean decision tree model. we show that in this model, randomization may only achieve a polynomial speedup over deterministic computation. this was known for las-vegas randomized computation; we prove it also for 1-sided error computation (a quadratic bound) and 2-sided error (a cubic bound).
on the degree of boolean functions as real polynomials every boolean function may be represented as a real polynomial. in this paper we characterize the degree of this polynomial in terms of certain combinatorial properties of the boolean function. our first result is a tight lower bound of &ohgr;(log n) on the degree needed to represent any boolean function that depends on n variables. our second result states that for every boolean function f the following measures are all polynomially related:(1) the decision tree complexity of f. (2) the degree of the polynomial representing f. (3) the smallest degree of a polynomial approximating f in the lmax norm.
symmetric logspace is closed under complement. we present a logspace, many-one reduction from the undirected s-t connectivity problem to its complement. this shows that sl=cosl.
on some families of languages related to the dyck language we recall that the dyck language on the alphabet of 2n letters x &equil; {x1,...,xn,&xmarc;1,...,&xmarc;n} is the equivalence class of the empty word 1 &egr; x@@@@ modulo the thue congruence generated on x@@@@ by the 2n relations xi&xmarc;i &equil; &xmarc;ixi &equil; 1 i &egr; {1,...,n}. indeed for all n &egr; x@@@@ the equivalence class of n modulo this congruence is a non ambiguous algebraic (ie. context-free) language, the complement of which is also a non ambiguous algebraic language. the same situation is true for the congruence generated on x@@@@ by the n relations xi&xmarc;i &equil; 1 i &egr; {1,...,n}. the author convinced himself that many other congruences have the same property [ni 1], and undertook the task of finding them systematically. here is presented a part of the results of this undertaking. an important family of congruences is brought to light which have interesting decidability properties: in the constructions leading to these decidability properties we used as a guide line the nice paper of mac naughton [mcn]. sufficient conditions are given in order that the equivalence classes (and their complements) of such a congruence be an algebraic language. we do not study in this paper the properties of these languages, this will be done elsewhere [ni 2].
ensembles reconnaissables de mots biinfinis the purpose of automata theory is to study and classify those properties of words that may be defined by a finite structure, say a finite automaton or a finite monoid. it seems natural to consider the same problem for infinite words. this amounts to studying the asymptotic behaviour of finite automata. as is well-known, this breaks the equivalence between determinism and non-determinism of finite automata. the study of the infinite behaviour of finite automata is based on a deep theorem due to b-&-uuml;chi and mc naughton: the recognizable sets of infinite words are the finite boolean combinations of deterministic ones (i.e. recognized by deterministic automata). the aim of this paper is to build an analogous theorem for two-sided infinite sequences. we define a biinfinite word as the equivalence class under the shift of a two-sided infinite sequence. the recognizable sets of biinfinite words are defined in a natural way and one is led to a two-sided notion of determinism. this notion seems to be new and justifies the consideration of biinfinite words. the main result of this paper is the extension to biinfinite words of the theorem of b-&-uuml;chi and mc naughton: the recognizable sets of biinfinite words are the finite boolean combinations of deterministic ones (theorem 3.1). there exist three available proofs of b-&-uuml;chi-mc naughton's theorem. the original one by mc naughton [4] is hard to read. the proof given by eilenberg in his book [2] has been constructed by sch-&-uuml;tzenberger and eilenberg from mc naughton's proof; it is similar to that of rabin [5]. finally, sch-&-uuml;tzenberger gave a further proof in [6], which makes the argument more direct by using the methods of the theory of finite monoids. the proof of our main result follows closely sch-&-uuml;tzenberger's method. this method allows to reduce the two-sided case to the one-sided case, although this seems very difficult to obtain directly. in the first section, we briefly recall the theory of the one-sided infinite behaviour of finite automata. in particular, we give sch-&-uuml;tzenberger's proof of b-&-uuml;chi-mc naughton's theorem. the elements of this proof are used in the proof of our main result. in the second section we define the notions of biinfinite word, biautomaton and deterministic biautomaton. the last section contains the proof of our main result.