waashk/dblp huggingface dataset:
nondeterministic communication with a limited number of advice bits. we present a new technique for differentiating deterministic from nondeterministic communication complexity. as a consequence we give almost tight lower bounds for the nondeterministic communication complexity with a restricted number of advice bits. in particular, for any function $t : \mathbb{n} \rightarrow \mathbb{n}$ with $t(n) \leq n/2$ we construct a family $(l_{n,t(n)} : n \in \mathbb{n})$ of languages such that $l_{n,t(n)} \subseteq \{0,1\}^{2n}$, ${\rm nc}(l_{n,t(n)}) = o(t(n) \cdot \log_2 \frac{n}{t(n)})$ and ${\rm nc}(\overline{l_{n,t(n)}}) = o\bigl(\frac{n}{t(n) \cdot \log_2 \frac{n}{t(n)}} + \log_2 t(n)\bigr)$, but ${\rm nc}_{o(t(n))}(l_{n,t(n)}) = \omega\bigl(\frac{n}{\log_2 \frac{n}{t(n)}}\bigr)$. here ${\rm nc}_r(l)$ is the nondeterministic communication complexity of l, assuming that at most r advice bits are utilized. thus, in contrast to probabilistic communication complexity, a small reduction in the number of advice bits results in almost maximal communication. as a special case we obtain a family $l_n \subseteq \{0,1\}^{2n}$ of languages with {\rm nc}_{o(\sqrt{n}/\log_2 n)}(l_n) &=& \omega\biggl(\frac{n}{\log_2 n}\biggr),\\ {\rm nc}(l_n) + {\rm nc}(\overline{l_n}) &=& o(\sqrt{n}), and hence nondeterministic communication with slightly restricted access to advice bits is almost quadratically weaker than nondeterminism that always gives correct answers (from the set {yes, no, ?}). as a consequence we obtain an almost optimal separation between monte-carlo communication and "correct" nondeterminism and answer a question of beame and lawry.
factorization of polynomials over finite fields and factorization of primes in algebraic number fields based on kummer theorem, we study the deterministic complexity of two factorization problems: polynomial factorization over finite fields and prime factorization in algebraic number fields. we show that factoring polynomials of degree n in fp[x], with p prime, is polynimially equivalent to factoring p in algebraic number field of extension degree n over q, where p is &ldquo;regular&rdquo; with respect to the generating polynomials of the number fields. part of the proof also yields an efficient polynomial time algorithm for computing the factorization pattern. number theoretical methods are then developed to solve two important kinds of polynomials:&fgr;n(x) mod p where &fgr;n is the n-th cyclotomic polynomial, and xn. - &agr; mod p where &agr; &egr; n. we show that when extended riemann hypothesis is assumed, all the roots of both kinds of polynomials in fp can be found efficiently in time polynomial in n and logp. as &agr; consequence, when p &xgr; 1(n), factorization of p in the n-th cyclotomic field can be computed in polynomial time. the result on finding all roots of xn &xgr; &agr;(p) extends &agr; result of adleman, menders, and miller, which states that the least root of xn &xgr; &agr;(p) can be found in polynomial time, when extended riemann hypothesis is assumed.
riemann hypothesis and finding roots over finite fields it is shown that assuming generalized riemann hypothesis, the roots of &fnof;(x) = o mod p, where p is a prime and f(x) is an integral abilene polynomial can be found in deterministic polynomial time. the method developed for solving this problem is also applied to prime decomposition in abelian number fields, and the following result is obtained: assuming generalized riemann hypotheses, for abelian number fields k of finite extension degree over the rational number field q, the decomposition pattern of a prime p in k, i.e. the ramification index and the residue class degree, can be computed in deterministic polynomial time, providing p does not divide the extension degree of k over q. it is also shown, as a theorem fundamental to our algorithm, that for q, p prime and m the order of p mod q, there is a q-th nonresidue in the finite field fpm that can be written as ao + a1w + &hellip; + am-1wm-1, where |a1| &le; cq2 log2(pq), c is an absolute effectively computable constant, and 1, w, &hellip;, wm-1 form a basis of fpm over fp. more explicitly, w is a root of the q-th cyclotomic polynomial over fp. this result partially generalizes, to finite field extensions over fp, a classical result in number theory stating that assuming generalized riemann hypothesis, the least q-th nonresidue mod p for p,q prime and q dividing p - t is bounded by c log2p, where c is an absolute, effectively computable constant.
on the time and tape complexity of languages i we investigate the following: (1) the relationship between the classes of languages accepted by deterministic and nondeterministic polynomial time bounded turing machines; (2) the time and tape complexity of many predicates on the regular sets; (3) the relationship between the classes of languages accepted by deterministic or nondeterministic polynomial time bounded turing machines and the class of languages accepted by polynomial tape bounded turing machines; and (4) the complexity of many predicates about stack automata. we find several problems with nonpolynomial lower complexity bounds.
computational parallels between the regular and context-free languages this paper presents a complexity theory of formal languages. the main technique used is that of embedding &ldquo;&equil;{0,1}*&rdquo;, &ldquo;&equil;0*&rdquo;, and &ldquo;&equil;&fgr;&rdquo; into other linguistic predicates. in section 2, the undecidability of &ldquo;&equil;{0,1}*&rdquo; for cfl's is exploited to provide sufficient conditions for the undecidability of predicates on the cfl's. in section 3, the same techniques are applied to regular sets. predicates satisfying conditions similar to those of section 2 are shown to be hard, where how hard depends on the descriptors used to enumerate the regular sets. section 4 concentrates on the equivalence and containment problems for cfl's. for cfl's, regular sets, and linear cfl's, the complexity of determining equivalence to a fixed language is linked to whether the fixed language is finite, infinite but bounded, or unbounded. in section 5, the ability of cfg's to generate finite languages whose strings are exponential in the size of the grammar is used to obtain exponential lower bounds on several decidable problems for cfg's generating finite sets. in section 6, all nontrivial predicates for certain specific classes of languages are shown to be hard. in section 7, we show that a dpda can always be converted in polynomial time into an equivalent dpda that always halts. therefore the predicate &ldquo;&equil;{0,1}*&rdquo; is in p for dpda's, and embedding this problem into other predicates on the dpda's will not yield nonpolynomial lower bounds. in section 8, some of the preceding results are generalized to other families of languages.
on the complexity of grammar and related problems in [1] and [2] a complexity theory for formal languages and automata was developed. this theory implies most of the previously known results and yields many new results as well. here we develop an analogous theory for several classes of more practically motivated problems. two such classes, both closely related to formal language and automata theory, suggest themselves - grammar problems and program scheme problems. here, our primary emphasis is on grammar problems of interest in parsing and compiling. other problems considered include - (1) possible techniques for proving non-trivial lower complexity bounds for problems in p; (2) the relationship of the complexity of tree automaton equivalence, structural equivalence, and grammatical covering; and (3) the complexity of the equivalence problem for schemes. in each case we relate the computational complexity of a problem to its underlying combinatorial structure. the remainder of the paper is divided into four sections.
dichotomization, reachability, and the forbidden subgraph problem (extended abstract) we present several techniques for proving lower bounds that can be applied to problems about grammars, formal languages, program schemes, simple programming languages, and automata. these techniques include dichotomization, extensions of dichotomization to certain classes of relational problems, recursive analogues of the post correspondence problem, and the reachability problem. these techniques provide many new lower bounds and provide a unified framework for viewing much of the work on the complexity of problems about grammars, languages, schemes, and automata. we show how to prove the undecidability of a problem by efficiently reducing the membership problem for tms that always halt to it. we also introduce the forbidden subgraph problem.
the complexity of the equivalence problem for commutative semigroups and symmetric vector addition systems this paper shows that the equivalence problems for commutative semigroups and symmetric vector addition systems are decidable in space cnlogn for some fixed constant c, solving an open question by cardoza, lipton, mayr, and meyer. from the exponential-space completeness of the word problems, it follows that our upper bound is nearly optimal.
on the parallel evaluation of multivariate polynomials we prove that any multivariate polynomial p of degree d that can be computed with c(p) multiplications-divisions can be computed in o(log d.log c(p)) parallel steps and o(log d) parallel multiplicative steps.
the complexity of parallel evaluation of linear recurrence the concept of computers such as c.mmp and illiac iv is to achieve computational speed-up by performing several operations simultaneously with parallel processors. this type of computer organization is referred to as a parallel computer. in this paper, we prove upper bounds on speed-ups achievable by parallel computers for a particular problem, the solution of first order linear recurrences. we consider this problem because it is important in practice and also because it is simply stated so that we might obtain some insight into the nature of parallel computation by studying it.
an efficient algorithm for computing optimal desk merge patterns (extended abstract) in this paper, we present an algorithm which computes the optimal pattern for merging n equal size sorted sequences stored on a disk, in time o(log n) and constant space. the best previously known algorithm for solving this problem (knuth [4], schlumberger-vuillemin [5]) takes time o(n2) and space o(n).
a useful device for showing the solvability of some decision problems we look at a restricted model of a multihead pushdown automaton and use some of its properties to show the existence of algorithms for some decision problems concerning code sets and vector addition systems.
the complexity of the equivalence problem for straight-line programs we look at several classes of straight-line programs and show that the equivalence problem is either undecidable or computationally intractable for all but the trivial classes. for example, there is no algorithm to determine if an arbitrary program (with positive, negative, or zero integer inputs) using only constructs x &larr; 1, x &larr; x + y, x &larr; x/y (integer division) outputs 0 for all inputs. the result holds even if we consider only programs which compute total 0/1 - functions. for programs using constructs x &larr; 0, x &larr; c, x &larr; cx, x &larr; x/c, x &larr; x + y, x &larr; x &minus; y, skip l, if p(x) then skip l, and halt,1 the equivalence problem is decidable in [equation] time (&lgr; is a fixed positive constant and n is the maximum of the sizes of the programs). the bound cannot be reduced to a polynomial in n unless p &equil; np. in fact, we prove the following rather surprising result: the equivalence problem for programs with one input/output variable and one intermediate variable using only constructs x &larr; x + y and x &larr; x/2 is np-hard. we also show the decidability of the equivalence problem for a certain class of programs and use this result to prove the following: let in be the set of natural numbers and f be any total one-to-one function from in onto in &times; in. (f is called a pair generator. such functions are useful in recursive function and computability theory.) then f cannot be computed by any program using only constructs x &larr; 0, x &larr; c, x &larr; x + y, x &larr; x &minus; y, x &larr; x * y, x &larr; x/y, skip l, if p(x) then skip l, and halt.
quantifier elimination in the theory of an algebraically-closed field in this paper we develop a fast parallel procedure for deciding when a set of multivariate polynomials with coefficients in an arbitrary field k have a common algebraic solution. moreover, since the proposed algorithm is algebraic, it easily yields a procedure for quantifier elimination in the theory of an arbitrary algebraically closed field. more precisely, we show how to decide whether m polynomials in n variables, each of degree at most d, with coefficients in an arbitrary field k have a common zero in the algebraic closure of k, using sequential time (mn)&ogr;(n)d&ogr;(n)2), or parallel time &ogr;(n3 log3 d log m) with (mn)&ogr;(n)d&ogr;(n)2) processors, in the operations of the coefficient field k. using randomization, this may be improved to (mn)&ogr;(1)d&ogr;(n) time. in addition, the construction is used give a direct expspace algorithm for quantifier elimination in the theory of an algebraically-closed field, which runs in pspace or parallel polynomial time when restricted to formulas with a fixed number of alternations of quantifiers.
relational queries computable in polynomial time (extended abstract) query languages for relational databases have received considerable attention. in 1972 codd [cod72] showed that two natural mathematical languages for queries-&-mdash;one algebraic and the other a version of first order predicate calculus-&-mdash;had identical powers of expressibility. query languages which are as expressive as codd's relational calculus are sometimes called complete. this term is misleading, however, because many interesting queries are not expressible in -&-ldquo;complete-&-rdquo; languages. in this paper we show: theorem 2: the fixpoint hierarchy collapses at the first fixpoint level. that is, any query expressible with several applications of least fixpoint can already be expressed with one. we also show: theorem 1: let l be a query language consisting of relational calculus plus the least fixpoint operator. suppose that l contains a relation symbol for a total ordering relation on the domain (e.g. lexicographic ordering). then the queries expressible in l are exactly the queries computable in polynomial time. theorem 1 was discovered independantly by m. vardi [var82]. it gives a simple syntactic categorization of those queries which can be answered in polynomial time. of course queries requiring polynomial time in the size of the database are usually prohibitatively expensive. we also consider weaker languages for expressing less complex queries.
limits on the provable consequences of one-way permutations we present strong evidence that the implication, &ldquo;if one-way permutations exist, then secure secret key agreement is possible&rdquo;, is not provable by standard techniques. since both sides of this implication are widely believed true in real life, to show that the implication is false requires a new model. we consider a world where all parties have access to a black box for a randomly selected permutation. being totally random, this permutation will be strongly one-way in a provable, information-theoretic way. we show that, if p = n p, no protocol for secret key agreement is secure in such a setting. thus, to prove that a secret key agreement protocol which uses a one-way permutation as a black box is secure is as hard as proving p &ne; n p. we also obtain, as a corollary, that there is an oracle relative to which the implication is false, i.e., there is a one-way permutation, yet secret-exchange is impossible. thus, no technique which relativizes can prove that secret exchange can be based on any one-way permutation. our results present a general framework for proving statements of the form, &ldquo;cryptographic application x is not likely possible based solely on complexity assumption y.&rdquo;
optimal approximations of the frequency moments of data streams. we give a 1-pass õ(m1-2⁄k)-space algorithm for computing the k-th frequency moment of a data stream for any real k > 2. together with the lower bounds of [1, 2, 4], this resolves the main problem left open by alon et al in 1996 [1]. our algorithm also works for streams with deletions and thus gives an õ(m 1-2⁄p) space algorithm for the lp difference problem for any p > 2. this essentially matches the known ω(m1-2⁄p-o(1)) lower bound of [12, 2]. finally the update time of our algorithms is õ(1).
two-dimensional alternating turing machines this paper introduces a two-dimensional alternating turing machine (2-atm) which is an extension of an alternating turing machine to two-dimensions. this paper also introduces a three-way two-dimensional alternating turing machine (tr2-atm) which is an alternating version of a three-way two-dimensional turing machine. we first investigate a relationship between the accepting powers of space-bounded 2-atm's (or tr2-atm's) and ordinary space-bounded two-dimensional turing machines (or three-way two-dimensional turing machines). we then introduce a simple, natural complexity measure for 2-atm's (or tr2-atm's), called -&-ldquo;leaf-size-&-rdquo;, and provides a spectrum of complexity classes based on leaf-size bounded computations. we finally investigate the recognizability of connected patterns by 2-atm's (or tr2-atm's).
black-box constructions for secure computation. it is well known that the secure computation of non-trivial functionalities in the setting of no honest majority requires computational assumptions. we study the way such computational assumptions are used. specifically, we ask whether the secure protocol can use the underlying primitive (e.g., one-way trapdoor permutation) in a black-box way, or must it be nonblack-box (by referring to the code that computes this primitive)? despite the fact that many general constructions of cryptographic schemes (e.g., cpa-secure encryption) refer to the underlying primitive in a black-box way only, there are some constructions that are inherently nonblack-box. indeed, all known constructions of protocols for general secure computation that are secure in the presence of a malicious adversary and without an honest majority use the underlying primitive in a nonblack-box way (requiring to prove in zero-knowledge statements that relate to the primitive).in this paper, we study whether such nonblack-box use is essential. we present protocols that use only black-box access to a family of (enhanced) trapdoor permutations or to a homomorphic public-key encryption scheme. the result is a protocol whose communication complexity is independent of the computational complexity of the underlying primitive (e.g., a trapdoor permutation) and whose computational complexity grows only linearly with that of the underlying primitive. this is the first protocol to exhibit these properties.
batch codes and their applications. a batch code encodes a string x into an m-tuple of strings, called buckets, such that each batch of k bits from x can be decoded by reading at most one (more generally, t) bits from each bucket. batch codes can be viewed as relaxing several combinatorial objects, including expanders and locally decodable codes. we initiate the study of these codes by presenting some constructions, connections with other problems, and lower bounds. we also demonstrate the usefulness of batch codes by presenting two types of applications: trading maximal load for storage in certain load-balancing scenarios, and amortizing the computational cost of private information retrieval (pir) and related cryptographic protocols.
on the sample size of k-restricted min-wise independent permutations and other k-wise distributions. an explicit study of min-wise independent permutation families, together with their variants --- k-restricted, approximate, etc. --- was initiated by broder, et al[4]. in this paper, we give a lower bound for the size of k-restricted min-wise independent permutation family. a family f of permutations on [0,n-1]=(0,1,...,n-1) is said to be k-restricted min-wise independent if for any subset x ⊆ [0,n-1] with |x| ≤ k and any x ∈ x, pr[min(π(x))=π(x)] = 1/|x|, when π is randomly chosen from f according to a probability distribution d on the family f. for the minimum size of a family of k-restricted min-wise independent permutations, upper bounds of o(nk) for any fixed k have been shown for uniform and biased probability distributions on f. we show that if a family f of permutations on [0,n-1] is k-restricted min-wise independent, then |f| ≥ m(n-1,k-1), where m(n,d) = ∑i=0d/2(ni) if d is even; m(n,d)= ∑i=0(d-1)/2(ni) + (n-1(d-1)/2) otherwise. the lower bound for the size of f still holds when we allow an arbitrary probability distribution on f. our proof technique is based on linear algebra methods, and can be regarded as a generalization of the result by alon, babai, and itai[1], i.e., if random variables x1,x2,...,xn: ω → (0,1) are k-wise independent and pr[xi=1] = pi is neither 0 nor 1, then |ω| ≥ m(n,k). by applying our proof technique, we also derive lower bounds for the sample size of the related notions, e.g., k-wise symmetrically independent distributions, k-rankwise independent permutation families, etc.
unique decomposability of shuffled strings: a formal treatment of asynchronous time-multiplexed communication a string x is said to be decomposed into strings yl,y2,...,yn if x is in y1 @@@@ y2 @@@@ ... @@@@ yn where @@@@ is the shuffle operator. we consider the problem of decomposing x into yl,y2,...,yn such that yl,y2,...,yn belong to predetermined languages l1,l2,...,ln, respectively. conditions under which such a decomposition is unique are presented as well as uniquely decomposable l1,l2,...,ln which are of practical significance from the viewpoint of time-multiplexed communication.
optimal evaluation of pairs of bilinear forms a large class of multiplication problems in arithmetic complexity can be viewed as the simultaneous evaluation of a set of bilinear forms. this class includes the multiplication of matrices, polynomials, quaternions, cayley and complex numbers. considering bilinear algorithms, the optimal number of non-scalar multiplications can be described as the rank of a three-tensor or as the smallest number of rank one matrices necessary to include a given set of matrices in their span. in this paper, we attack a rather large subclass of three-tensors, namely that of (p, q, 2) tensors, for arbitrary p and q, and solve it completely. the complexity of a general pair of bilinear forms is determined explicitly in terms of parameters related to kronecker's theory of pencils and to the theory of invariant polynomials. this reveals unexpected results and shows explicitly the dependence on the algebraic structure of the constants; we display, for example, a pair of n x n bilinear forms whose complexity is n + 1 over infinite fields and which, however, requires exactly n+[(n-1) &brvbar;k] multiplications over a finite field with cardinality k. another consequence of our results is that any set of m, p x q, bilinear forms require at most m/2(min(p+q/2, q+p/2)) multiplications over any field.