waashk/dblp huggingface dataset:
the computational complexity of some julia sets. although numerous computer programs have been written to compute sets of points which claim to approximate julia sets, no reliable high precision pictures of non-trivial julia sets are currently known. usually, no error estimates are added and even those algorithms which work reliably in theory, become unreliable in practice due to rounding errors and the use of fixed length floating point numbers.in this paper we prove the existence of polynomial time algorithms to approximate the julia sets of complex functions f(z)=z2+c for |c|<1/4. we will give a strict computable error estimation w.r.t. the hausdorff metric dh which means that the set is recursive [10]. although these and many more julia sets j are proven to be recursive [12] and furthermore recursive compact subsets of the euclidean plane are known to have a computable turing machine time complexity [10], hardly anything is known about the computational complexity of non-trivial examples. the algorithms given in this paper compute the julia sets locally in time o(k2• m(k)) (where m(k) is a time bound for multiplication of two k-bit integers). roughly speaking, the local time complexity is the number of turing machine steps to decide for a single point whether it belongs to a grid kk⊆ (2-k• z)2 such that dh(kk,j)≤ 2-k.
how to reuse a ``write-once'' memory (preliminary version) storage media such as digital optical disks, proms, or paper tape consist of a number of -&-ldquo;write-once-&-rdquo; bit positions (wits); each wit initially contains a -&-ldquo;0-&-rdquo; that may later be irreversibly overwritten with a -&-ldquo;i-&-rdquo;. we demonstrate that such -&-ldquo;write-once memories-&-rdquo; (woms) can be -&-ldquo;rewritten-&-rdquo; to a surprising degree. for example, only 3 wits suffice to represent any 2-bit value in a way that can later be updated to represent any other 2-bit value. for large k, 1.29... k wits suffice to represent a k-bit value in a way that can be similarly updated. most surprising, allowing t writes of a k-bit value requires only t + o(t) wits, for any fixed k. for fixed t, approximately k.t/log(t) wits are required as k -&-rarr; @@@@. an n-wit wom is shown to have a -&-ldquo;capacity-&-rdquo; (i.e. k.t when writing a k-bit value t times) of up to n.log(n) bits.
a generalization and proof of the aanderaa-rosenberg conjecture we investigate the maximum number c(p) of arguments of p that must be tested in order to compute p, a boolean function of d boolean arguments. we present evidence for the general conjecture that c(p)&equil;d whenever p(0d) @@@@ p(1d) and p is left invariant by a transitive permutation group acting on the arguments. a non-constructive argument (not based on the construction of an &ldquo;oracle&rdquo;) proves the generalized conjecture for d a prime power. we use this result to prove the aanderaa-rosenberg conjecture by showing that at least v2/9 entries of the adjacency matrix of a v-vertex undirected graph g must be examined in the worst case to determine if g has any given non-trivial monotone graph property.
complexity classes of partial recursive functions (preliminary version) this paper studies possible extensions of the concept of complexity class of recursive functions to partial recursive functions. many of the well-known results for total complexity classes are shown to have corresponding, though not exactly identical, statements for partial classes. in particular, with two important exceptions, all results on the presentation and decision problems of membership for the two most reasonable definitions of partial classes are the same as for total classes. the exceptions concern presentations of the complements and maximum difficulty for decision problems of the more restricted form of partial classes. the last section of this paper shows that it is not possible to have an &ldquo;intersection theorem&rdquo;, corresponding to the union theorem of mccreight and meyer, either for complexity classes or complexity index sets.
structure of complexity in the weak monadic second-order theories of the natural numbers the complexity of decision procedures for the weak monadic second-order theories of the natural numbers are considered. if only successor is allowed as a primitive, then every alternation of second-order quantifiers causes an exponential increase in the complexity of deciding the validity of a formula. thus a heirarchy similar in form to kleene's arithmetic heirarchy may be shown to correspond to the ritchie functions. on the other hand, if first-order less-than is allowed as a primitive, one existential quantifier suffices for arbitrarily complex (in the ritchie heirarchy) decision problems. this leads to a normal form, in which every sentence in the theory is equivalent in polynomial time to a sentence with less-than but only one existential second-order quantifier.
the decidability of the reachability problem for vector addition systems (preliminary version) let v be a finite set of integral vectors in euclidian n-space, and let &abarbelow; be an integral point in the first orthant of n-space. the reachability set r(&abarbelow;,v) is the set of integral points &bbarbelow; in the first orthant such that there is a polygonal path &ggr; from &abarbelow; to &bbarbelow; satisfying (i) all of &ggr; lies in the first orthant, and (ii) the edges of &ggr; are translates of the vectors in v. the reachability problem for the vector addition system (&abarbelow;,v) asks for an algorithm to decide which integral points &bbarbelow; are in r(&abarbelow;,v). in this paper we give an algorithm to solve this problem.
a complete axiomatization for a large class of dependencies in relational databases relational database theory has discovered complete axiomatizations for functional and multivalued dependencies. however, a database design system that makes use of dependencies declared by the user must deal with some more general kinds of dependencies than these&mdash; at least with embedded multivalued dependencies. yet no axiomatization for embedded multivalued dependencies is known. in this paper, we define a more general class of dependencies, called &ldquo;template dependencies&rdquo; and give a complete axiomatization for these. we then discuss the interaction between functional dependencies and template dependencies.
algorithmic derandomization via complexity theory. we point out how the methods of nisan (1990, 1992), originally developed for derandomizing space-bounded computations, may be applied to obtain polynomial-time and nc derandomizations of several probabilistic algorithms. our list includes the randomized rounding steps of linear and semi-definite programming relaxations of optimization problems, parallel derandomization of discrepancy-type problems, and the johnson--lindenstrauss lemma, to name a few.a fascinating aspect of this style of derandomization is the fact that we often carry out the derandomizations directly from the statements about the correctness of probabilistic algorithms, rather than carefully mimicking their proofs.
exponential determinization for omega-automata with strong-fairness acceptance condition (extended abstract) in [saf88] an exponential determination procedure for bu&uml;chi automata was shown, yielding tight bounds for decision procedures of some logics ([ej88, saf88, sv89, kt89]). in [sv89] the complexity of determinization and complementation of &ohgr;-automata was further investigated, leaving as an open question the complexity of the determinization of a single class of &ohgr;-automata. for this class of &ohgr;-automata with strong fairness as acceptance condition (street automata), [sv89] managed to show an exponential complementation procedure, but showed that the blow-up of the translation of these automata to any of the classes known to admit exponential determinization is inherently exponential. this might suggest that the blow-up of the determinization of street automata is inherently doubly exponential. surprisingly, we show an exponential determinization construction for any streett automaton. in fact, the complexity of our construction is roughly the same as the complexity achieved in [saf88] for bu&uml;chi automata. moreover, a simple observation extends this upper bound to the complexity of the complementation problem. since any &ohgr;-automaton that admits exponential determinization can be easily converted into a streett automaton, we get one procedure that can be used for all of these conversions. this construction is optimal (up to a constant factor in the exponent) for all of these conversions. our results imply that streett automata (with strong fairness as acceptance condition) can be used instead of bu&uml;chi automata (with the weaker acceptance condition) without any loss of efficiency.
on decomposing languages defined by parallel devices in this paper we give a method for decomposing subclasses of different families of languages, into other possibly smaller families. this method can be used to produce languages not in a family by using known examples of languages not belonging to other families.
a data structure for dynamic trees we propose a data structure to maintain a collection of vertex-disjoint trees under a sequence of two kinds of operations: a link operation that combines two trees into one by adding an edge, and a cut operation that divides one tree into two by deleting an edge. our data structure requires o(log n) time per operation when the time is amortized over a sequence of operations. using our data structure, we obtain new fast algorithms for the following problems: (1) computing deepest common ancestors. (2) solving various network flow problems including finding maximum flows, blocking flows, and acyclic flows. (3) computing certain kinds of constrained minimum spanning trees. (4) implementing the network simplex algorithm for the transshipment problem. our most significant application is (2); we obtain an o(mn log n)-time algorithm to find a maximum flow in a network of n vertices and m edges, beating by a factor of log n the fastest algorithm previously known for sparse graphs.
space lower bounds for distance approximation in the data stream model. (math) we consider the problem of approximating the distance of two d-dimensional vectors x and y in the data stream model. in this model, the 2d coordinates are presented as a "stream" of data in some arbitrary order, where each data item includes the index and value of some coordinate and a bit that identifies the vector (x or y) to which it belongs. the goal is to minimize the amount of memory needed to approximate the distance. for the case of lp-distance with p &egr; [1,2], there are good approximation algorithms that run in polylogarithmic space in d (here we assume that each coordinate is an integer with o(log d) bits). here we prove that they do not exist for p&rho;2. in particular, we prove an optimal approximation-space tradeoff of approximating l&infty; distance of two vectors. we show that any randomized algorithm that approximates l&infty; distance of two length d vectors within factor of d&dgr; requires &omega;(d1&mdash;4&dgr;) space. as a consequence we show that for p&rho;2/(1&mdash;4&dgr;), any randomized algorithm that approximate lp distance of two length d vectors within a factor d&dgr; requires &omega;(d 1&mdash; 2< \over p&mdash;4&dgr;) space.the lower bound follows from a lower bound on the two-party one-round communication complexity of this problem. this lower bound is proved using a combination of information theory and fourier analysis.
self-adjusting binary trees we use the idea of self-adjusting trees to create new, simple data structures for priority queues (which we call heaps) and search trees. unlike other efficient implementations of these data structures, self-adjusting trees have no balance condition. instead, whenever the tree is accessed, certain adjustments take place. (in the case of heaps, the adjustment is a sequence of exchanges of children, in the case of search trees the adjustment is a sequence of rotations.) self-adjusting trees are efficient in an amortized sense: any particular operation may be slow but any sequence of operations must be fast. self-adjusting trees have two advantages over the corresponding balanced trees in both applications. first, they are simpler to implement because there are fewer cases in the algorithms. second, they are more storage-efficient because no balance information needs to be stored. furthermore, a self-adjusting search tree has the remarkable property that its running time (for any sufficiently long sequence of search operations) is within a constant factor of the running time for the same set of searches on any fixed binary tree. it follows that a self-adjusting tree is (up to a constant factor) as fast as the optimal fixed tree for a particular probability distribution of search requests, even though the distribution is unknown.
wait-free k-set agreement is impossible: the topology of public knowledge. in the classical consensus problem, each of n processors receives a private input value and produces a decision value which is one of the original input values, with the requirement that all processors decide the same value. a central result in distributed computing is that, in several standard models including the asynchronous shared-memory model, this problem has no deterministic solution. the k-set agreement problem is a generalization of the classical consensus proposed by chaudhuri [ inform. and comput., 105 (1993), pp. 132--158], where the agreement condition is weakened so that the decision values produced may be different, as long as the number of distinct values is at most k. for $n>k\geq 2$ it was not known whether this problem is solvable deterministically in the asynchronous shared memory model. in this paper, we resolve this question by showing that for any k < n, there is no deterministic wait-free protocol for n processors that solves the k-set agreement problem. the proof technique is new: it is based on the development of a topological structure on the set of possible processor schedules of a protocol. this topological structure has a natural interpretation in terms of the knowledge of the processors of the state of the system. this structure reveals a close analogy between the impossibility of wait-free k-set agreement and the brouwer fixed point theorem for the k-dimensional ball.
correct and optimal implementations of recursion in a simple programming language the object of this paper is to study the mechanism of recursion in a simple, lisp-like programming language, where the only mean of iteration is through recursion. the theory of computation developped in scott [4] provides the framework of our study. we show how the implementations of recursion which deserve to be called &ldquo;correct&rdquo; can be characterized semantically, and demonstrate a general criterion for the correctness of an implementation. we then describe an implementation of recursion which is both correct and optimal in a general class of sequential languages, and therefore constitutes an attractive alternative to both &ldquo;call-by-name&rdquo; and &ldquo;call-by-value&rdquo;.
spectral norm of random matrices. in this paper, we present a new upper bound for the spectral norm of symmetric random matrices with independent (but not necessarily identical) entries. our results improve an earlier result of f&#x00fc;redi and koml&#x00f3;s.
a complexity theoretic approach to randomness we study a time bounded variant of kolmogorov complexity. this notion, together with universal hashing, can be used to show that problems solvable probabilistically in polynomial time are all within the second level of the polynomial time hierarchy. we also discuss applications to the theory of probabilistic constructions.
on obfuscating point functions. we investigate the possibility of obfuscating point functions in the framework of barak et al. from crypto '01. a point function is a boolean function that assumes the value 1 at exactly one point. our main results are as follows:we provide a simple construction of efficient obfuscators for point functions for a slightly relaxed notion of obfuscation, for which obfuscating general circuits is nonetheless impossible. our construction relies on the existence of a very strong one-way permutation, and yields the first non-trivial obfuscator under general assumptions in the standard model. we also obtain obfuscators for point functions with multi-bit output and for prefix matching.our assumption is that there is a one-way permutation wherein any polynomial-sized circuit inverts the permutation on at most a polynomial number of inputs. we show that a similar assumption is in fact necessary, and that our assumption holds relative to a random permutation oracle.finally, we establish two impossibility results which indicate that the limitations on our construction, namely simulating only adversaries with single-bit output and using nonuniform advice in our simulator, are in some sense inherent.previous work gave negative results for the general class of circuits (barak et al., crypto '01) and positive results in the random oracle model (lynn et al., eurocrypt '04) or under non-standard number-theoretic assumptions (canetti, crypto '97). this work represents the first effort to bridge the gap between the two for a natural class of functionalities.
gowers uniformity, influence of variables, and pcps. we study the relation of query complexity and soundness in probabilistically checkable proofs (pcps). we present a pcp verifier for languages that are unique-games-hard and such that the verifier makes $q$ queries, has almost perfect completeness, and has soundness error at most $2q/2^q+\varepsilon$ for arbitrarily small $\varepsilon>0$. for values of $q$ of the form $2^t-1$, the soundness error is $(q+1)/2^q+\varepsilon$. charikar, makarychev, and makarychev show that there is a constant $\beta$ such that every language that has a verifier of query complexity $q$ and a ratio of soundness error to completeness smaller than $\beta q/2^q$ is decidable in polynomial time. up to the value of the multiplicative constant and to the validity of the unique games conjecture, our result is therefore tight. as a corollary, we show that approximating the maximum independent set problem in graphs of degree $\delta$ within a factor better than $\delta/(\log\delta)^\alpha$ is unique-games-hard for a certain constant $\alpha>0$. our main technical results are (i) a connection between the gowers uniformity of a boolean function and the influence of its variables and (ii) the proof that &ldquo;gowers uniform&rdquo; functions pass the &ldquo;hypergraph linearity test&rdquo; approximately with the same probability of a random function. the connection between gowers uniformity and influence might have other applications.
the round complexity of two-party random selection. we study the round complexity of two-party protocols for generating a random n-bit string such that the output is guaranteed to have bounded bias (according to some measure) even if one of the two parties deviates from the protocol (even using unlimited computational resources). specifically, we require that the output's statistical difference from the uniform distribution on zon is bounded by a constant less than 1.we present a protocol for the above problem that has 2 log*n+o(1) rounds, improving a 2n-round protocol that follows from the work of goldreich, goldwasser, and linial (focs'91). like the ggl protocol, our protocol actually provides a stronger guarantee, ensuring that the output lands in any set t⊆zon of density μ with probability at most o(√μ+δ), where δ is an arbitarily small constant.we then prove a matching lower bound, showing that any protocol guaranteeing bounded statistical difference requires at least log*n - log* log*n-o(1) rounds. as far as we know, this is the first nontrivial lower bound on the round complexity of random selection protocols (of any type) that does not impose additional constraints (e.g. on communication or "simulatability").we also state several results for the case when the output's bias is measured by the maximum multiplicative factor by which a party can increase the probability of a set t ⊆ zon.
on tape versus core; an application of space efficient perfect hash functions to the invariance of space in complexity theory the use of informal estimates can be justified by appealing to the invariance thesis which states that all standard models of computing devices are sufficiently equivalent. this thesis would require, among others, that a ram can be simulated by a turingmachine with constant factor overhead in space. such a simulation is hard to obtain if the traditional spacemeasure for ram-space is used. the simulation uses a new method for condensing space, based on perfect hashing.
algebraic methods in the theory of lower bounds for boolean circuit complexity we use algebraic methods to get lower bounds for complexity of different functions based on constant depth unbounded fan-in circuits with the given set of basic operations. in particular, we prove that depth k circuits with gates not, or and modp where p is a prime require exp(&ogr;(n1/2k)) gates to calculate modr functions for any r &ne; pm. this statement contains as special cases yao's parity result [ ya 85 ] and razborov's new majority result [ra 86] (modm gate is an oracle which outputs zero, if the number of ones is divisible by m).
quantum and classical query complexities of local search are polynomially related. let f be an integer valued function on a finite set v. we call an undirected graph g(v,e) a neighborhood structure for f. the problem of finding a local minimum for f can be phrased as: for a fixed neighborhood structure g(v,e) find a vertex x ∈ v such that f(x) is not bigger than any value that f takes on some neighbor of x. the complexity of the algorithm is measured by the number of questions of the form "what is the value of f on x?" we show that the deterministic, randomized and quantum query complexities of the problem are polynomially related. this generalizes earlier results of aldous[4] ald and aaronson [1] aar and solves the main open problem in aar.
reimer's inequality and tardos' conjecture. (math) let f: {0,1}n &rarr; {0,1} be a boolean function. for &egr;&roe; 0 de(f) be the minimum depth of a decision tree for f that makes an error for &xie;&egr; fraction of the inputs &khar; &egr; {0,1}n. we also make an appropriate definition of the approximate certificate complexity of f, c&egr;(f). in particular, d0(f) and c0(f) are the ordinary decision and certificate complexities of f. it is known that $d_0(f) \leq (c_0(f))^2$. answering a question of tardos from 1989, we show that for all $\ge > 0$ there exists a $\gd' > 0$ such that for all $0 \leq \gd < \gd'$, we have $d_\ge(f) \leq k (c_\gd(f))^2$ where $k = k(\ge,\gd) > 0$ is a constant independent of f. the algorithm used in the proof is modeled after those developed by r. impagliazzo and s. rudich for use in other problems.
algebraic structure theory of stochastic machines in the present paper, an algebraic structure theory of stochastic machines is developed which contains both bacon's theory [1] and hartmanis' theory for deterministic machines [5] as special cases. although the present theory is patterned after both theories, it exhibits many interesting features which are here-to-fore unknown. among other things, it is shown that the basic concepts involved, e.g., partitions with substitution property, partition pairs, state-behavior realizations, are all equivalent to well-known concepts in linear algebra. section ii introduces the model of stochastic machines to be used in subsequent developments. in section iii, various types of realizations and assignments are introduced. the concepts of partitions with substitution property, partition pairs, etc. are introduced in section iii. the last section gives a formulation of a network of concurrently operating qsms.