waashk/dblp huggingface dataset:
local zero knowledge. we put forward the notion of local zero knowledge and provide its first implementations in a variety of settings under standard complexity assumptions.whereas the classical notion of zero knowledge guarantees the secrecy only of information that is hard to compute, the new one meaningfully guarantees the secrecy of any information (in case of perfect zero-knowledge, and asymptotically in all other cases). consequently, local zero knowledge remains very meaningful even if dp = np.
improved cryptographic hash functions with worst-case/average-case connection. we define a new family of collision resistant hash functions whose security is based on the worst case hardness of approximating the covering radius of a lattice within a factor o(t n^2 log n), where t is a value between 1 and sqrt(n) that depends on the solution of the closest vector problem in certain "almost perfect" lattices. using standard transference theorems from the geometry of numbers, our result immediately gives a connection between the worst-case and average-case complexity of the shortest vector problem with connection factor o(t n^3 log n).
construction with parallel derivatives of the closure of a parallel program schema the parallel derivative of a set of strings is introduced. given a serial, repetition-free parallel program schema, its closure is constructed by taking parallel derivatives of its set of computations. the construction resembles the construction of a state diagram from a regular expression by means of derivatives.
toward mechanical verification of properties of roundoff error propagation in this paper we will be concerned with portions of roundoff analysis which can be automated. conditions are given under which proofs of numerical stability can be performed completely automatically and very economically (in particular, in polynomial time). we also discuss the use of &ldquo;numerical heuristics&rdquo; which apply &ldquo;hill-climbing&rdquo; methods to functionals measuring contamination from roundoff. in section 2 we will relate this work to the extensive literature on roundoff error. two properties of error propagation in straight-line programs are defined in section 3, and their relationship demonstrated in theorem 1. the properties are guaranteed to be effectively decidable since they can be formulated in the first-order theory of real-closed fields. in section 4 we present sufficient conditions for the properties to hold; conditions which can be checked in time bounded by a polynomial in the size of the given straight-line program.
computational complexity and numerical stability limiting consideration to algorithms satisfying various numerical stability requirements may change lower bounds for computational complexity and/or make lower bounds easier to prove. we will show that, under a sufficiently strong restriction upon numerical stability, any algorithm for multiplying two n&times;n matrices using only +, &minus; and &times; requires at least n3 multiplications. we conclude with a survey of results concerning the numerical stability of several algorithms which have been considered by complexity theorists.
riemann's hypothesis and tests for primality the purpose of this paper is to present new upper bounds on the complexity of algorithms for testing the primality of a number. the first upper bound is 0(n&frac17;); it improves the previously best known bound of 0(n&frac14;) due to pollard [11]. the second upper bound is dependent on the extended riemann hypothesis (erh): assuming erh, we produce an algorithm which tests primality and runs in time 0((log n)4) steps. thus we show that primality is testable in time a polynomial in the length of the binary representation of a number. finally, we give a partial solution to the relationship between the complexity of computing the prime factorization of a number, computing the euler phi function, and computing other related functions.
graph isomorphism, general remarks an open question is the computational complexity of recognizing when two graphs are isomorphic. in an attempt to answer this question we shall analyze the relative computational complexity of generalizations and restrictions of the graph isomorphism problem. in the first section we show graph isomorphism of regular undirected graphs is complete over isomorphism of explicitly given structures (say tarski models from logic). then we show that valence seems to be important. finally we analyze symmetric cubic graphs.
isomorphism testing for graphs of bounded genus we present an algorithm which determines isomorphism of graphs in vo(g)steps where v is the number of vertices and g is the genus of the graphs. in [fmr 79] an algorithm was presented for embedding graph on surfaces of genus g in vo(g) steps. here we show how to extend this algorithm to isomorphism testing for graphs of small genus. this result is noteworthy for at least two reasons. first, this extends the polynomial time isomorphism results for the plane [ht 72] and also the projective plane [l 80] to arbitrary surfaces. second, this gives one of the few known natural decompositions of the isomorphism problem into an infinite hierarchy of problems po,p1,... such that isomorphism testing of problems in p1 is decidable in time vo(i).
finding small simple cycle separators for 2-connected planar graphs we show that every 2-connected triangulated planar graph with n vertices has a simple cycle c of length at most 4@@@@n which separates the interior vertices a from the exterior vertices b such that neither a nor b contains more than 2/3n vertices. the method also gives a linear time algorithm for finding the simple cycle. in general, if the maximum face size is d then we exhibit a cycle c as above of size at most 2@@@@2d&bull;n.
a new graph triconnectivity algorithm and its parallelization we present a new algorithm for finding the tri-connected components of an undirected graph. the algorithm is based on ear decomposition and has linear sequential running time. it also has a parallel implementation on a crcw pram with o(log2n) parallel time using a linear number of processors, where n is the number of vertices in the graph. this is the first efficient parallel algorithm for graph tri-connectivity.
dynamic parallel complexity of computational circuits the dynamic parallel complexity of general computational circuits (defined in introduction) is discussed. we exhibit some relationships between parallel circuit evaluation and some uniform closure properties of a certain class of unary functions and present a systematic method for the design of processor efficient parallel algorithms for circuit evaluation. using this method: (1) we improve the algorithm for parallel boolean circuit evaluation; (2) we give a nontrivial upper bound for parallel min-max-plus circuit evaluation; (3) we partially answer the first open question raised in [mirk85] by showing that all circuits over finite noncommutative semi-ring and circuits over infinite non-commutative semi-ring which has finite dimension over a commutative semi-ring can be evaluated in polylogarithmic time in its size and degree using m(n) processors. moreover, we develop a theory for determining closure properties of certain classes of unary functions.
on formulating simultaneity for studying parallelism and synchronization when studying parallel computation and synchronization one is faced with the problem of modeling the simultaneous execution of processes. although there has been a multitude of formal means for representing such problems [2, 6, 9, 10, 13, 14, 15], invariably, when all the other complexities of the models have been stripped away, the parallelism or synchronization is studied via sequences of events. in all of these studies simultaneity of events is not studied directly. rather, it is represented by the interleaving of the separate events into sequences, and by studying properties of the set of all such sequences.
lower bounds for union-split-find related problems on random access machines. we prove =(clog logn ) lower bounds on the random access machine complexity of several dynamic, partially dynamic and static data structure problems, including the union-split-find problem, dynamic prefix problems and one-dimensional range query problems. the proof techniques include a general technique using perfect hashing for reducing static data structure problems (with a restriction of the size of the structure) into partially dynamic data structure problems (with no such restriction), thus providing a way to transfer lower bounds. we use a generalization of a method due to ajtai for proving the lower bounds on the static problems, but describe the proof in terms of communication complexity, revealing a striking similarity to the proof used by karchmer and wigderson for proving lower bounds on the monotone circuit depth of connectivity.
complete axiomatization of algorithmic properties of program schemes with bounded nondeterministic interpretations propositional algorithmic logic pal is a propositional counterpart of algorithmic logics. it investigates properties of program connectives: begin...end, while...do, if..then..else, or .... pal supplies tools for reasoning about programs constructed from program variables by means of program connectives and about their algorithmic properties. sound rules of inference and tautologies of pal are as important in analysis of programs (e.g. verification) as tautologies of classical propositional calculus. on the other hand propositional algorithmic theories are of highest interest, since they can capture properties of data structures and also algorithmic properties of behaviours of concurrent systems. we proved that the semantical and the syntactical consequence operations coincide (completeness property) and that the model existence theorem holds.
fast computation of gcds an integer greatest common divisor (gcd) algorithm due to sch&ouml;nhage is generalized to hold in all euclidean domains which possess a fast multiplication algorithm. it is shown that if two n precision elements can be multiplied in o(n loga n), then their gcd can be computed in o(n loga+1 n). as a consequence, a new faster algorithm for multivariate polynomial gcd's can be derived and with that new bounds for rational function manipulation.
the glauber dynamics on colourings of a graph with high girth and maximum degree. we prove that the glauber dynamics on the c-colorings of a graph g on n vertices with girth g and maximum degree $\delta$ mixes rapidly if (i) $c=q\delta$ and $q>q^*$, where $q^*=1.4890\ldots$ is the root of $(1-{\rm e}^{-1/q})^2+q{\rm e}^{-1/q}=1$; and (ii) $\delta\geq d\log n$ and $g\geq d\log\delta$ for some constant d=d(q). this improves the bound of roughly $1.763\delta$ obtained by dyer and frieze [ proceedings of the 32nd annual symposium on foundations of computer science, 2001] for the same class of graphs. our bound on this class of graphs is lower than the bound of $11\delta/6\approx1.833\delta$ obtained by vigoda [j. math. phys., 41 (2000), pp. 1555--1569] for general graphs.
models and thresholds for random constraint satisfaction problems. we introduce a class of models for random constraint satisfaction problems. this class includes and generalizes many previously studied models. we characterize those models from our class which exhibit thresholds for satisfiability in the sense that the limiting probability of satisfiability changes significantly as the number of constraints increases. we also discuss models which exhibit sharp thresholds in the sense that the limiting probability jumps from 0 to 1 suddenly.
colouring graphs when the number of colours is nearly the maximum degree. we consider for graphs of maximum degree &dgr;, the problem of determining whether &khgr;g) > &dgr;-k for various values of k. we obtain sharp theorems characterizing when the barrier to &dgr;-k colourability must be a local condition, i.e. a small subgraph, and when it can be global. we also show that for large fixed &dgr;, this problem is either np-complete or can be solved in linear time, and we determine precisely which values of k correspond to each case prove that hitting set with sets of size b is hard to approximate to within a factor $b^{1/19}$. the problem can be approximated to within a factor b [19], and it is the vertex cover problem for b=2. the relationship between hardness of approximation and set size seems to have not been explored before.
bandwidth constrained np-complete problems bandwidth restrictions are considered on several np-complete problems, including the following problems: (1) 3-satisfiability, (2) independent set and vertex cover, (3) simple max cut (4) partition into triangles, (5) 3-dimensional matching, (6) exact cover by 3 sets, (7) dominating set, (8) graph grundy numbering (for graphs of finite degree), (9) 3-colorability, (10) directed and undirected hamiltonian circuit, (11) bandwidth minimization, and (12) feedback vertex set and feedback arc set. it is shown that each of the problems (1)-(12) when restricted to graphs (formulas, triples, or sets) of bandwidth bounded by a function f is log space hard for the complexity class ntisp (poly,f(n)). (ntisp(poly,f(n)) denotes the family of problems solvable nondeterministically in polynomial time and simultaneous f(n) space, e.g., ntisp(poly,poly) &equil; np and ntisp(poly, log n) &equil; nspace(log n).). in fact, (1)-(9) are log space complete for ntisp(poly,f(n)) when the bandwidth is bounded by the function f. this means, for example, that (1)-(9) provide several new examples of problems complete for nspace(log n), and hence solvable in polynomial time deterministically, when restricted to bandwidth log2n. in general, for a function f, if any of the problems (1)-(12), when restricted to bandwidth f(n), could be solved deterministically in polynomial time, then ntisp(poly, f(n)) @@@@ p. (this does not seem particularly likely even when f(n) &equil; log2n.) this indicates that several np-complete problems become easier with diminishing bandwidth. however, they remain intractable unless the bandwidth is restricted to c-log2n, for some c>0.
edge isoperimetry and rapid mixing on matroids and geometric markov chains. we show how to bound the mixing time and log-sobolev constants of markov chains by bounding the edge-isoperimetry of their underlying graphs. to do this we use two recent techniques, one involving average conductance and the other log-sobolev constants. we show a sort of strong conductance bound on a family of geometric markov chains, give improved bounds for the mixing time of a markov chain on balanced matroids, and in both cases find lower bounds on the log-sobolev constants of these chains.
the mixing time of the thorp shuffle. the thorp shuffle is defined as follows. cut the deck into two equal piles. drop the first card from the left pile or the right pile according to the outcome of a fair coin flip; then drop from the other pile. continue this way until both piles are empty. we show that the mixing time for the thorp shuffle with 2d cards is polynomial in d.
a result on the relationship between simple precedence languages and reducing transition languages two of the more recently published systems for the efficient parsing of subclasses of deterministic, context-free languages are the backwards-deterministic, (or unambiguous, as they were originally called) simple precedence languages due to wirth and weber, and the reducing transition languages due to eickel, paul, bauer, and samelson. the main result demonstrated in this paper is that the backwards-deterministic, simple precedence languages are a proper subclass of the reducing transition languages. the reducing transition languages are certainly a subclass of the deterministic, context-free (lr(1)) languages but it is not known if this inclusion is proper. the major complaint against the reducing transition languages is the large amount of memory required when this technique is utilized with large grammars, such as the algol 60 grammar. with memory costs and physical memory sizes decreasing at a rapid rate, it is very possible that this disadvantage will not exist in the not-too-distant future. when this becomes true, the advantage of reducing transition languages, i.e., the relatively small amount of time required for their parsing, may result in their significance being substantially increased. thus it is of some import that we study their relationship to other languages. the main result is based on two theorems: (1) if g is a backwards-deterministic simple precedence grammar, then g is a reducing transition grammar; and (2) the language l1 &equil; {a0n1n2m&brvbar;m,n &ge; 1} &ugr; {b0n1m2n&brvbar;m,n &ge; 1} is a reducing transition language but is not a backwards-deterministic simple precedence language.
recursion schemes with lists scheme translation is used to compare the abilities of languages obtained by augmenting recursion schemes with lists, markers, and functional values. it is shown that the first two additions make orthogonal contributions to the language's power. theorems 4 and 5 appear to be new results.
evolving sets and mixin. we show that a new probabilistic technique, recently introduced by the first author, yields the sharpest bounds obtained to date on mixing times in terms of isoperimetric properties of the state space (also known as conductance bounds or cheeger inequalities). we prove that the bounds for mixing time in total variation obtained by lovasz and kannan, can be refined to apply to the maximum relative deviation |pn(x,y)/π(y)-1| of the distribution at time n from the stationary distribution π. our approach also yields a direct link between isoperimetric inequalities and heat kernel bounds; previously, this link rested on analytic estimates known as nash inequalities.
on dynamic range reporting in one dimension. we consider the problem of maintaining a dynamic set of integers and answering queries of the form: report a point (equivalently, all points) in a given interval. range searching is a natural and fundamental variant of integer search, and can be solved using predecessor search. however, for a ram with w-bit words, we show how to perform updates in o(lg w) time and answer queries in o(lg lg w) time. the update time is identical to the van emde boas structure, but the query time is exponentially faster. existing lower bounds show that achieving our query time for predecessor search requires doubly-exponentially slower updates. we present some arguments supporting the conjecture that our solution is optimal.our solution is based on a new and interesting recursion idea which is "more extreme" that the van emde boas recursion. whereas van emde boas uses a simple recursion (repeated halving) on each path in a trie, we use a nontrivial, van emde boas-like recursion on every such path. despite this, our algorithm is quite clean when seen from the right angle. to achieve linear space for our data structure, we solve a problem which is of independent interest. we develop the first scheme for dynamic perfect hashing requiring sublinear space. this gives a dynamic bloomier filter (a storage scheme for sparse vectors) which uses low space. we strengthen previous lower bounds to show that these results are optimal.
sub-constant error low degree test of almost-linear size. given a function f:fm→f over a finite field f, a low degree tester tests its agreement with an m-variate polynomial of total degree at most d over f. the tester is usually given access to an oracle a providing the supposed restrictions of f to affine subspaces of constant dimension (e.g., lines, planes, etc.). the tester makes very few (probabilistic) queries to f and to a (say, one query to f and one query to a), and decides whether to accept or reject based on the replies.we wish to minimize two parameters of a tester: its error and its size. the error bounds the probability that the tester accepts although the function is far from a low degree polynomial. the size is the number of bits required to write the oracle replies on all possible tester's queries.low degree testing is a central ingredient in most constructions of probabilistically checkable proofs (pcps) and locally testable codes (ltcs). the error of the low degree tester is related to the soundness of the pcp and its size is related to the size of the pcp (or the length of the ltc).we design and analyze new low degree testers that have both sub-constant error o(1) and almost-linear size n1+o(1) (where n=|f|m). previous constructions of sub-constant error testers had polynomial size [13, 16]. these testers enabled the construction of pcps with sub-constant soundness, but polynomial size [13, 16, 9]. previous constructions of almost-linear size testers obtained only constant error [13, 7]. these testers were used to construct almost-linear size ltcs and almost-linear size pcps with constant soundness [13, 7, 5, 6, 8].
approximation algorithms for constrained for constrained node weighted steiner tree problems. we consider a class of optimization problems, where the input is an undirected graph with two weight functions defined for each node, namely the node's profit and its cost. the goal is to find a connected set of nodes of low cost and high profit. we present approximation algorithms for three natural optimization criteria that arise in this context, all of which are np-hard. the budget problem asks for maximizing the profit of the set subject to a budget constraint on its cost. the quota problem requires minimizing the cost of the set subject to a quota constraint on its profit. finally, the prize collecting problem calls for minimizing the cost of the set plus the profit (here interpreted as a penalty) of the complement set. for all three problems, our algorithms give an approximation guarantee of o(\log n), where n is the number of nodes. to the best of our knowledge, these are the first approximation results for the quota problem and for the prize collecting problem, both of which are at least as hard to approximate as set cover. for the budget problem, our results improve on a previous o(\log^2 n) result of guha, moss, naor, and schieber. our methods involve new theorems relating tree packings to (node) cut conditions. we also show similar theorems (with better bounds) using edge cut conditions. these imply bounds for the analogous budget and quota problems with edge costs which are comparable to known (constant factor) bounds.
learning juntas. we consider a fundamental problem in computational learning theory: learning an arbitrary boolean function which depends on an unknown set of k out of n boolean variables. we give an algorithm for learning such functions from uniform random examples which runs in time roughly (nk)ω/(ω + 1), where ω < 2.376 is the matrix multiplication exponent. we thus obtain the first polynomial factor improvement on the naive nk time bound which can be achieved via exhaustive search. our algorithm and analysis exploit new structural properties of boolean functions.
learning nonsingular phylogenies and hidden markov models. in this paper, we study the problem of learning phylogenies and hidden markov models. we call a markov model nonsingular if all transition matrices have determinants bounded away from 0 (and 1). we highlight the role of the nonsingularity condition for the learning problem. learning hidden markov models without the nonsingularity condition is at least as hard as learning parity with noise. on the other hand, we give a polynomial-time algorithm for learning nonsingular phylogenies and hidden markov models.