waashk/dblp huggingface dataset:
lower bounds on communication complexity we prove the following four results on communication complexity: 1) for every k &ge; 2, the language lk of encodings of directed graphs of out degree one that contain a path of length k+1 from the first vertex to the last vertex and can be recognized by exchanging o(k log n) bits using a simple k-round protocol requires exchanging &ohgr;(n1/2/k4log3n) bits if any (k&minus;1)- round protocol is used. 2) for every k &ge; 1 and for infinitely many n &ge; 1, there exists a collection of sets lnk @@@@ {0,1}2n that can be recognized by exchanging o(k log n) bits using a k-round protocol, and any (k&minus;1)-round protocol recognizing lnk requires exchanging &ohgr;(n/k) bits. 3) given a set l @@@@ {0,1}2n, there is a set l@@@@{0,1}8n such that any (k-round) protocol recognizing l@@@@ can be transformed to a (k-round) fixed partition protocol recognizing l with the same communication complexity, and vice versa. 4) for every integer function f, 1 &le;f(n) &le; n, there are languages recognized by a one round deterministic protocol exchanging f(n) bits, but not by any nondeterministic protocol exchanging f(n)&minus;1 bits. the first two results show in an incomparable way an exponential gap between (k&minus;1)-round and k-round protocols, settling a conjecture by papadimitriou and sipser. the third result shows that as long as we are interested in existence proofs, a fixed partition of the input is not a restriction. the fourth result extends a result by papadimitriou and sipser who showed that for every integer function f, 1 &le; f(n) &le; n, there is a language accepted by a deterministic protocol exchanging f(n) bits but not by any deterministic protocol exchanging f(n) &minus; 1 bits.
locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits. in this work we study two, seemingly unrelated, notions. locally decodable codes (ldcs) are codes that allow the recovery of each message bit from a constant number of entries of the codeword. polynomial identity testing (pit) is one of the fundamental problems of algebraic complexity: we are given a circuit computing a multivariate polynomial and we have to determine whether the polynomial is identically zero. we improve known results on locally decodable codes and on polynomial identity testing and show a relation between the two notions. in particular we obtain the following results:we show that if e: fn → fm is a linear ldc with 2 queries then m = exp(ω(n)). previously this was only known for fields of size << 2n [18].we show that from every depth 3 arithmetic circuit (σπς circuit), c, with a bounded (constant) top fan-in that computes the zero polynomial, one can construct a locally decodeable code. more formally: assume that c is minimal (no subset of the multiplication gates sums to zero) and simple (no linear function appears in all the multiplication gates). denote by d the degree of the polynomial computed by c and by r the rank of the linear functions appearing in c. then we can construct a linear ldc with 2 queries, that encodes messages of length r/polylog(d) by codewords of length o(d).we prove a structural theorem for σπς circuits, with a bounded top fan-in, that compute the zero polynomial. in particular we show that if such a circuit is simple and minimal and of polynomial size then its rank, r, is only polylogarithmic in the number of variables (a priory it could have been linear).we give new pit algorithms for σπς circuits with a bounded top fan-in:a deterministic algorithm that runs in quasi polynomial time.a randomized algorithm that runs in polynomial time and uses only polylogarithmic number of random bits..moreover, when the circuit is multilinear our deterministic algorithm runs in polynomial time. previously, deterministic subexponential time algorithms for pit in bounded depth circuits were known only for depth 2 circuits (in the black box model)[22, 9, 28]. in particular, for the special case of depth 3 circuits with 3 multiplication gates our result resolves an open question asked by klivans and spielman [28].
contention in shared memory algorithms. most complexity measures for concurrent algorithms for asynchronous shared-memory architectures focus on process steps and memory consumption. in practice, however, performance of multiprocessor algorithms is heavily influenced by contention, the extent to which processess access the same location at the same time. nevertheless, even though contention is one of the principal considerations affecting the performance of real algorithms on real multiprocessors, there are no formal tools for analyzing the contention of asynchronous shared-memory algorithms.this paper introduces the first formal complexity model for contention in shared-memory multiprocessors. we focus on the standard multiprocessor architecture in which n asynchronous processes communicate by applying read, write, and read-modify-write operations to a shared memory. to illustrate the utility of our model, we use it to derive two kinds of results: (1) lower bounds on contention for well-known basic problems such as agreement and mutual exclusion, and (2) trade-offs between the length of the critical path (maximal number of accesses to shared variables performed by a single process in executing the algorithm) and contention for these algorithms. furthermore, we give the first formal contention analysis of a variety of counting networks, a class of concurrent data structures inplementing shared counters. experiments indicate that certain counting networks outperform conventional single-variable counters at high levels of contention. our analysis provides the first formal model explaining this phenomenon.
concurrent zero-knowledge. concurrent executions of a zero-knowledge protocol by a single prover (with one or more verifiers) may leak information and may not be zero-knowledge in toto. in this article, we study the problem of maintaining zero-knowledge.we introduce the notion of an (&alpha;, &beta;) timing constraint: for any two processors p1 and p2, if p1 measures &alpha; elapsed time on its local clock and p2 measures &beta; elapsed time on its local clock, and p2 starts after p1 does, then p2 will finish after p1 does. we show that if the adversary is constrained by an (&alpha;, &beta;) assumption then there exist four-round almost concurrent zero-knowledge interactive proofs and perfect concurrent zero-knowledge arguments for every language in np. we also address the more specific problem of deniable authentication, for which we propose several particularly efficient solutions. deniable authentication is of independent interest, even in the sequential case; our concurrent solutions yield sequential solutions without recourse to timing, that is, in the standard model.
2-round zero knowledge and proof auditors. we construct 2-round (ie, 2-message), public-coin, black-box (concurrent) zero-knowledge proof systems and arguments for any language in np under the assumption that the prover is resource-bounded during the execution of the protocol.
approximate counting by dynamic programming. we give efficient algorithms to sample uniformly, and count approximately, the solutions to a zero-one knapsack problem. the algorithm is based on using dynamic programming to provide a deterministic relative approximation. then "dart throwing" techniques are used to give arbitrary approximation ratios. we also indicate how further improvements can be obtained using randomized rounding. we extend the approach to several related problems: the m-constraint zero-one knapsack, the general integer knapsack (including its m-constraint version) and contingency tables with constantly many rows.
a random polynomial time algorithm for approximating the volume of convex bodies a randomized polynomial-time algorithm for approximating the volume of a convex body k in n-dimensional euclidean space is presented. the proof of correctness of the algorithm relies on recent theory of rapidly mixing markov chains and isoperimetric inequalities to show that a certain random walk can be used to sample nearly uniformly from within k.
speedups of deterministic machines by synchronous parallel machines this paper presents the new speedups dtime(t) @@@@ atime(t/log t) and dtime(t) @@@@ pram-time(@@@@t). these improve the results of hopcroft, paul, and valiant that dtime(t) @@@@ dspace(t/log t), and of paul and reischuk that dtime(t) @@@@ atime(t log log t/log t). the new approach unifies not only these two previous results, but also the result of paterson and valiant that size(t) @@@@ depth(o(t/log t)).
tight security proofs for the bounded-storage model. (math) in the bounded-storage model for information-theoretically secure encryption and key-agreement one can prove the security of a cipher based on the sole assumption that the adversary's storage capacity is bounded, say by s bits, even if her computational power is unlimited. assume that a random t-bit string r is either publicly available (e.g. the signal of a deep space radio source) or broadcast by one of the legitimate parties. if s$xi;t, the adversary can store only partial information about r. the legitimate sender alice and receiver bob, sharing a short secret key k initially, can therefore potentially generate a very long n-bit one-time pad x with n&raquo;|k| about which the adversary has essentially no information, thus at first glance apparently contradicting shannon's bound on the key size of a perfect cipher.all previous results in the bounded-storage model were partial or far from optimal, for one of the following reasons: either the secret key k had in fact to be longer than the derived one-time pad, or t had to be extremely large (t&rho;ns), or the adversary was assumed to be able to store only actual bits of r rather than arbitrary s bits of information about r, or the adversary could obtain a non-negligible amount of information about x.in this paper we prove the first non-restricted security result in the bounded-storage model, exploiting the full potential of the model: k is short, x is very long (e.g. gigabytes), t needs to be only moderately larger than s, and the security proof is optimally strong. in fact, we prove that s/t can be arbitrarily close to 1 and hence the storage bound is essentially optimal.
computability concepts for programming language semantics this paper is about mathematical problems in programming language semantics and their influence on recursive function theory. we define a notion of computability on continuous higher types (for all types) and show its equivalence to effective operators. this result shows that our computable operators can model mathematically (i.e. extensionally) everything that can be done in an operational semantics. these new recursion theoretic concepts which are appropriate to semantics also allow us to construct scott models for the &lgr;-calculus which contain all and only computable elements. depending on the choice of the initial cpo, our general theory yields a theory for either strictly determinate or else arbitrary non-deterministic objects (parallelism). the formal theory is developed in part ii of this paper. part i gives motivation and comparison with related work.
on (un)predictability of formal languages (extended abstract) formal language theory deals with a variety of classes of languages. some of these are abstracting features of languages used for communication (as e.g., natural languages, programming languages or languages used in logic), some of them are abstracting features of languages used for description of processes (as e.g. basic classes of l languages) and still others are considered for mathematical reasons. can we have a criterion for deciding whether a language can serve as a &ldquo;communication language&rdquo; (e.g. for man-to-man or man-to-machine communication) ? our main result (the basic unpredictability inequality) displays a connection between the &ldquo;rate of unpredictability&rdquo; and the relative number of subpatterns occurring in a language. after establishing this result we investigate (as samples) two classes of languages: regular languages and dol languages
complexity of implementations on the level of algebraic specifications the aim of this paper is to study implementations of abstract data types and their complexity within the framework of algebraic specifications. an implementation of an abstract data type adto by an abstract data type adt1 is defined on a syntactical and on a semantical level where data and operations of adto are simulated by those of adt1. in order to investigate complexity of implemented operations and to compair different implementations we axiomatically introduce complexity measures for the operations in adto with respect to a given implementation of adto by adt1. a most natural interesting class of complexity measures which satisfy our axioms is compatible with time complexity of turing machines. this is shown by specification and implementation of timebounded turing machines within our algebraic framework and the simulation of a general nondeterministic interpreter for algebraic implementations by a nondeterministic turing machine. this relationship allows to show the existence of solutions and of upper and lower bounds for the complexity of a broad class of implementation problems in our sense. a corollary shows that there are algebraic specifications for all those recursive functions which are bounded in time by algebraically specifyable functions. since the complexity measure for adto-operations in a given implementation impl1 of adto by adt1 in general depends on the complexity of the adt1-operations it is possible to substitute the complexity of the adt1-operations which may be obtained from an implementation impl2 of adt1 by adt2. on the other hand the composite implementation impl3 of adto by adt2 can be constructed and it is shown that the composite complexity of impl3 is less or equal to the substituted complexity considered above provided that some natural consistency conditions are satisfied.
classes of semigroups and classes of sets let a be a subset of &sgr;+, the free semigroup generated by a finite set &sgr;. in &sgr;+ we consider congruences satisfying the condition x&ntilde;y & x&egr;a@@@@y&egr; a among all such congruences there is a largest one, and the quotient monoid by this congruence is denoted by sa and is called the syntactic semigroup of a. this semigroup is finite if and only if the set a is recognizable (by a finite automaton). the semigroup sa can then easily be described using the minimal automaton of a. it is reasonable to expect that reasonable properties of the recognizable set a will be reflected by reasonable properties of the finite semigroups sa and vice-versa. in trying to establish such a dialog, one is handicapped by the fact that there are finite semigroups which are not syntactic monoids of any set. the objective of this note is to state a theorem showing that the above inconvenience disappears if one considers classes of sets (rather than individual sets) and classes of semigroups.
new results on monotone dualization and generating hypergraph transversals. we consider the problem of dualizing a monotone cnf (equivalently, computing all minimal transversals of a hypergraph) whose associated decision problem is a prominent open problem in np-completeness. we present a number of new polynomial time, respectively, output-polynomial time results for significant cases, which largely advance the tractability frontier and improve on previous results. furthermore, we show that duality of two monotone cnfs can be disproved with limited nondeterminism. more precisely, this is feasible in polynomial time with o(log2 n/\log log n) suitably guessed bits. this result sheds new light on the complexity of this important problem.
excellent codes from modular curves. we introduce a new construction of error-correcting codes from algebraic curves over finite fields. modular curves of genus g\ra\infty over a field of size q_0^2 yield nonlinear codes more efficient than the linear goppa codes obtained from the same curves. these new codes now have the highest asymptotic transmission rates known for certain ranges of alphabet size and error rate. both the theory and possible practical use of these new record codes require the development of new tools. on the theoretical side, establishing the transmission rate depends on an error estimate for a theorem of schanuel applied to the function field of an asymptotically optimal curve. on the computational side, actual use of the codes will hinge on the solution of new problems in the computational algebraic geometry of curves.
unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. the design of distributed approximation protocols is a relatively new rapidly developing area of research. however, so far little progress was done in the study of the hardness of distributed approximation. in this paper we initiate the systematic study of this subject, and show strong unconditional lower bounds on the time-approximation tradeoff of the distributed minimum spanning tree problem, and some of its variants.
lower-stretch spanning trees. we show that every weighted connected graph g contains as a subgraph a spanning tree into which the edges of g can be embedded with average stretch o (log2 n log log n). moreover, we show that this tree can be constructed in time o (m log2n) in general, and in time o (mlog n) if the input graph is unweighted. the main ingredient in our construction is a novel graph decomposition technique.our new algorithm can be immediately used to improve the running time of the recent solver for symmetric diagonally dominant linear systems of spielman and teng from m2(o√lognlog log n) to m log o(1)n and to o (n log2n log log n) when the system is planar. our result can also be used to improve several earlier approximation algorithms that use low-stretch spanning trees.
combinatorial logarithmic approximation algorithm for directed telephone broadcast problem. (math) consider a synchronous network of processors, modeled by directed or undirected graph g = (v,e), in which on each round every processor is allowed to choose one of its neighbors and to send him a message. given a processor s &egr; v, and a subset t &sube; v of processors, the telephone multicast problem requires to compute the shortest schedule (in terms of the number of rounds) that delivers a message from s to all the processors of t. the particular case t = v is called telephone broadcast problem.these problems have multiple applications in distributed computing. several approximation algorithms with polylogarithmic ratio, including one with logarithmic ratio, for the undirected variants of these problems are known. however, all these algorithms involve solving large linear programs. devising a polylogarithmic approximation algorithm for the directed variants of these problems is anopen problem, posed in [15].we devise a combinatorial logarithmic approximation algorithm for these problems, that applies also for the directed broadcast problem. our algorithm has significantly smaller running time, and seems to reveal more information about the combinatorial structure of the solution, than the previous algorithms, that are based on linear programming.(math) we also improve the lower bounds on the approximation threshold of these problems. both problems are known to be 3/2-inapproximable. for the undirected (resp., directed) broadcast problem we show that it is np-hard (resp., impossible unless $np &supe; dtime(no(log n))) to approximate it within a ratio of 3 &mdash;&egr; for any &egr; &rho; 0 (resp., &omega;(\sqrt log n)).finally, we study the radio broadcast problem. its setting is similar to the telephone broadcast problem, but in every round every processor may either send a message to all its neighbors or may not send it at all. a processor is informed in a certain round if and only if it receives a message from precisely one neighbor.(math) this problem was known to admit o(log2 n)-approximation algorithm, but no hardness of approximation was known. in this paper we show that the problem is &omega;(log n)-inapproximable unless np &sube; bptime(nlog log n}).
(1+epsilon, beta)-spanner constructions for general graphs. an {\em $(\alpha,\beta)$-spanner} of a graph g is a subgraph h such that $\mathit{dist}_h(u,w)\le \alpha\cdot \mathit{dist}t_g(u,w)+\beta$ for every pair of vertices u,w, where distg'(u,w) denotes the distance between two vertices u and v in g'. it is known that every graph g has a polynomially constructible $(2\kappa-1,0)$-spanner (also known as multiplicative $(2\kappa-1)$-spanner) of size $o(n^{1+1/\kappa})$ for every integer $\kappa\ge 1$, and a polynomially constructible (1,2)-spanner (also known as additive 2-spanner) of size ${\tilde o}(n^{3/2})$. this paper explores hybrid spanner constructions (involving both multiplicative and additive factors) for general graphs and shows that the multiplicative factor can be made arbitrarily close to 1 while keeping the spanner size arbitrarily close to o(n), at the cost of allowing the additive term to be a sufficiently large constant. more formally, we show that for any constant $\epsilon, \lambda > 0$ there exists a constant $\beta = \beta(\epsilon, \lambda)$ such that for every $n$-vertex graph g there is an efficiently constructible $(1+ \epsilon, \beta)$-spanner of size $o(n^{1 + \lambda})$.
probabilistic tree automata the purpose of this paper is meant to be three-fold. first it will introduce the reader to the concepts of probabilistic languages and probabilistic grammars. second, it indicates that previous definitions of probabilistic finite automaton have always been restricted to 1 of 8 classes of automaton and shows that other classes are useful. third, the probabilistic concept is extended from finite automata to higher level automata (such as probabilistic pdas and probabilistic turing automata). a specific application of this theory is given in the development of probabilistic tree automata. theorems concerning these automata and operations on them are presented. it is indicated that this type of automaton is relevant because it characterizes probabilistic context free languages. the results are taken from the author's phd thesis.4
decision procedures and expressiveness in the temporal logic of branching time in this paper we consider the computation tree logic (ctl) proposed in [ce] which extends the unified branching time logic (ub) of [bmp] by adding an until operator. we establish that ctl has the small property by showing that any satisfiable ctl formulae is satisfiable in a small finite model obtained from a small -&-ldquo;pseudo-model-&-rdquo; resulting from the fischer ladner quotient construction. we then give an exponential time algorithm for deciding satisfiability in ctl, and extend the axiomatization of ub given in [bmp] to a complete axiomatization for ctl. lastly, we study the relative expressive power of a family of temporal logics obtained by extending or restricting the syntax of ub and ctl.
deciding branching time logic in this paper we study the full branching time logic (ctl*) in which a path quantifier, either a (&ldquo;for all paths-&-rdquo;) or e (-&-ldquo;for some path&rdquo;), prefixes an assertion composed of arbitrary combinations of the usual linear time operators f (&ldquo;sometime&rdquo;), g (&ldquo;always&rdquo;), x (&ldquo;nexttime&rdquo;), and u (&ldquo;until&rdquo;). we show that the problem of determining if a ctl* formula is satisfiable in structure generated by a binary relation is decidable in triple exponential time. the decision procedure exploits the special structure of the finite state &ohgr;-automata for linear temporal formulae which allows them to be determinized with only a single exponential blowup in size. we also compare the expressive power of tree automata with ctl* augmented by quantified auxillary propositions.