waashk/dblp huggingface dataset:
lower bounds for local search by quantum arguments. the problem of finding a local minimum of a black-box function is central for understanding local search as well as quantum adiabatic algorithms. for functions on the boolean hypercube $\left\{0,1\right\}^n$, we show a lower bound of $\omega\left(2^{n/4}/n\right)$ on the number of queries needed by a quantum computer to solve this problem. more surprisingly, our approach, based on ambainis's quantum adversary method, also yields a lower bound of $\omega\left(2^{n/2}/n^2\right)$ on the problem's classical randomized query complexity. this improves and simplifies a 1983 result of aldous. finally, in both the randomized and quantum cases, we give the first nontrivial lower bounds for finding local minima on grids of constant dimension $d\geq3$.
representing hard lattices with o(n log n) bits. we present a variant of the ajtai-dwork public-key cryptosystem where the size of the public-key is only o(nlog n) bits and the encrypted text/clear text ratio is also o(nlog n). this is true with the assumption that all of the participants in the cryptosystem share o(n2log n) random bits which has to be picked only once and the users of the cryptosystem get them e.g. together with the software implementing the protocol. the public key is a random lattice with an nc-unique nonzero shortest vector, where the constant c>1‾2 can be picked arbitrarily close to 1‾2, and we pick the lattice according to a distribution described in the paper. we do not prove a worst-case average-case equivalence but the security of the system follows from the hardness of a randomized diophantine approximation problem related to a well-known theorem of dirichlet.
the complexity of agreement. a celebrated 1976 theorem of aumann asserts that bayesian agents with common priors can never "agree to disagree": if their opinions about any topic are common knowledge, then those opinions must be equal. but two key questions went unaddressed: first, can the agents reach agreement after a conversation of reasonable length? second, can the computations needed for that conversation be performed efficiently? this paper answers both questions in the affirmative, thereby strengthening aumann's original conclusion.we show that for two agents with a common prior to agree within ε about the expectation of a [0,1] variable with high probability over their prior, it suffices for them to exchange o(1/ε2) bits. this bound is completely independent of the number of bits n of relevant knowledge that the agents have. we also extend the bound to three or more agents; and we give an example where the "standard protocol" (which consists of repeatedly announcing one's current expectation) nearly saturates the bound, while a new "attenuated protocol" does better. finally, we give a protocol that would cause two bayesians to agree within ε after exchanging o(1/ε2) messages, and that can be simulated by agents with limited computational resources. by this we mean that, after examining the agents' knowledge and a transcript of their conversation, no one would be able to distinguish the agents from perfect bayesians. the time used by the simulation procedure is exponential in 1/ε6 but not in n.
optimal code generation for expression trees we discuss the problem of generating code for a wide class of machines, restricting ourselves to the computation of expression trees. after defining a broad class of machines and discussing the properties of optimal programs on these machines, we derive a necessary and sufficient condition which can be used to prove the optimality of any code generation algorithm for expression trees on this class. we then present a dynamic programming algorithm which produces optimal code for any machine in the class; this algorithm runs in time which is linearly proportional to the number of vertices in an expression tree.
a sharp threshold in proof complexity. we give the first example of a sharp threshold in proof complexity. more precisely, we show that for any sufficiently small &egr;>0 and &dgr;>2.28, random formulas consisting of (1-&egr;)n 2-clauses and &dgr n 3-clauses, which are known to be unsatisfiable almost certainly, almost certainly require resolution and davis-putnam proofs of unsatisfiability of exponential size, whereas it is easily seen that random formulas with (1+&egr;)n 2-clauses (and &dgr; n 3 clauses) have linear size proofs of unsatisfiability almost certainly.a consequence of our result also yields the first proof that typical random 3-cnf formulas at ratios below the generally accepted range of the satisfiability threshold (and thus expected to be satisfiable almost certainly) cause natural davis-putnam algorithms to take exponential time to find satisfying assignments.
a conjecture about polynomial time computable lattice-lattice functions. we formulate a conjecture which describes all of the polynomial time computable (p. t. c. ) functions f with domain(f)=lattice n, range(f) ⊆ lattice m, m ≤ nc, where latticen is the set of lattices in rn with determinant 1. a former conjecture, the 0-1-conjecture, of the author states that all 0,1-valued functions defined on latticen are constant almost everywhere. since the n-dimensional lattices as abelian groups are pairwise isomorphic we can say that, according to this conjecture, the value of a p. t. c. 0,1-function may depend only on the algebraic structure of the lattice and not on the metric defined on it. the new conjecture generalizes this statement for functions where the value is also a lattice. as a typical example we can think of the function f(l)=l′, where l′ is the dual of l. when both the domain and the range of the functions are n-dimensional lattices with determinants 1 then, according to the conjecture, every p. c. t. functions are either constant or identical almost everywhere to f(l)=al, or f(l)=al′, where a is a suitably chosen linear transformation with determinant one.there is a striking analogy between the new conjecture and theorems describing the uniquely definable functions which assign for each n-dimensional vectorspace an m-dimensional vectorspace. these theorems are closely related to questions about the axiom of choice. in this analogy polynomial time computation corresponds to definability (in set theory) and lattices to finite dimensional vectorspaces.
parallel computation over hyperbolic groups hyperbolic groups are a rich class of groups frequently encountered in mathematical research, particularly in topology. it has been the focus of intense study by many combinatorial group theorists and topologists recently. we present some computational results for infinite groups, especially for hyperbolic groups. it is shown that the word problem for hyperbolic groups is solvable in nc2. this is the first nc algorithm for a class of groups in combinatorial group theory. we also consider the isomorphism problem of randomly generated groups using a novel technique: the alexander polynomial from knot theory. these randomly generated groups are almost always hyperbolic groups.
on the bias of traceroute sampling: or, power-law degree distributions in regular graphs. understanding the graph structure of the internet is a crucial step for building accurate network models and designing efficient algorithms for internet applications. yet, obtaining this graph structure can be a surprisingly difficult task, as edges cannot be explicitly queried. for instance, empirical studies of the network of internet protocol (ip) addresses typically rely on indirect methods like traceroute to build what are approximately single-source, all-destinations, shortest-path trees. these trees only sample a fraction of the network's edges, and a paper by lakhina et al. [2003] found empirically that the resulting sample is intrinsically biased. further, in simulations, they observed that the degree distribution under traceroute sampling exhibits a power law even when the underlying degree distribution is poisson. in this article, we study the bias of traceroute sampling mathematically and, for a very general class of underlying degree distributions, explicitly calculate the distribution that will be observed. as example applications of our machinery, we prove that traceroute sampling finds power-law degree distributions in both &delta;-regular and poisson-distributed random graphs. thus, our work puts the observations of lakhina et al. on a rigorous footing, and extends them to nearly arbitrary degree distributions.
almost all graphs with average degree 4 are 3-colorable. we analyze a randomized version of the brelaz heuristic on sparse random graphs. we prove that almost all graphs with average degree d ≤ 4.03, i.e., g(n,p = d/n), are 3-colorable and that a constant fraction of all 4-regular graphs are 3-colorable.
the two possible values of the chromatic number of a random graph. for every d > 0, let kd be the smallest integer k such that d < 2k log k. we prove that the chromatic number of a random graph g(n,d/n) is either kd or kd+1 almost surely. if d ∈ (2k log k - log k, 2k log k) we further prove that the chromatic number almost surely equals k+1.
approximate counting of inversions in a data stream. (math) inversions are used as a fundamental quantity to measure the sortedness of data, to evaluate different ranking methods for databases, and in the context of rank aggregation. considering the volume of the data sets in these applications, the data stream model {14, 2] is a natural setting to design efficient algorithms.we obtain a suite of space-efficient streaming algorithms for approximating the number of inversions in a permutation. the best space bound we achieve is $o(\log n \log \log n)$ through a deterministic algorithm. in contrast, we derive an $\omega(n)$ lower bound for randomized exact computation for this problem; thus approximation is essential.(math) we also consider two generalizations of this problem: (1) approximating the number of inversions between two permutations, for which we obtain a randomized $o(\sqrt{n} \log n)$-space algorithm, and (2) approximating the number of inversions in a general list, for which we obtain a randomized $o(\sqrt{n} \log^2 n)$-space two-pass algorithm. in contrast, we derive $\omega(n)$-space lower bounds for deterministic approximate computation for these problems; thus both randomization and approximation are essential.all our algorithms use only o(log n) time per data item.
the threshold for random k-sat is 2 (ln 2 - o(k)). let fk(n,m) be a random k-sat formula on n variables formed by selecting uniformly and independently m out of all possible k-clauses. it is well-known that for r ≥ 2k ln 2, fk(n,rn) is unsatisfiable with probability 1-o(1). we prove that there exists a sequence tk = o(k) such that for r ≥ 2k ln 2 - tk, fk(n,rn) is satisfiable with probability 1-o(1).our technique yields an explicit lower bound for every k which for k > 3 improves upon all previously known bounds. for example, when k=10 our lower bound is 704.94 while the upper bound is 708.94.
a sieve algorithm for the shortest lattice vector problem. we present a randomized 2^{o(n)} time algorithm to compute a shortest non-zero vector in an n-dimensional rational lattice. the best known time upper bound for this problem was 2^{o(n\log n)} first given by kannan [7] in 1983. we obtain several consequences of this algorithm for related problems on lattices and codes, including an improvement for polynomial time approximations to the shortest vector problem. in this improvement we gain a factor of log log n in the exponent of the approximating factor.
on the solution-space geometry of random constraint satisfaction problems. for a number of random constraint satisfaction problems, such as random k-sat and random graph/hypergraph coloring, there are very good estimates of the largest constraint density for which solutions exist. yet, all known polynomial-time algorithms for these problems fail to find solutions even at much lower densities. to understand the origin of this gap we study how the structure of the space of solutions evolves in such problems as constraints are added. in particular, we prove that much before solutions disappear, they organize into an exponential number of clusters, each of which is relatively small and far apart from all other clusters. moreover, inside each cluster most variables are frozen, i.e., take only one value. the existence of such frozen variables gives a satisfying intuitive explanation for the failure of the polynomial-time algorithms analyzed so far. at the same time, our results establish rigorously one of the two main hypotheses underlying survey propagation, a heuristic introduced by physicists in recent years that appears to perform extraordinarily well on random constraint satisfaction problems.
low level complexity for combinatorial games there have been numerous attempts to discuss the time complexity of problems and classify them into hierarchical classes such as p, np, pspace, exp, etc. a great number of familiar problems have been reported which are complete in np (nondeterministic polynomial time). even and tarjan considered generalized hex and showed that the problem to determine who wins the game if each player plays perfectly is complete in polynomial space. shaefer derived some two-person game from np complete problems which are complete in polynomial space. a rough discussion such as to determine whether or not a given problem belongs to np is independent of the machine model and the way of defining the size of problems, since any of the commonly used machine models can be simulated by any other with a polynomial loss in running time and by no matter what criteria the size is defined, they differ from each other by polynomial order. however, in precise discussion, for example, in the discussion whether the computation of a problem requires o(n k) time or o(nk+l) time, the complexity heavily depends on machine models and the definition of size of problems. from these points, we introduce somewhat stronger notion of the reducibility.
deterministic simulation in logspace in this paper we show that a wide class of probabilistic algorithms can be simulated by deterministic algorithms. namely if there is a test in logspace so that a random sequence of length (log n)2 / log log n passes the test with probability at least 1/n then a deterministic sequence can be constructed in logspace which also passes the test. it is important that the machine performing the test gets each bit of the sequence only once. the theorem remains valid if both the test and the machine constructing the satisfying sequence have access to the same oracle of polynomial size. the sequence that we construct does not really depend on the test, in the sense that a polynomial family of sequences is constructed so that at least one of them passes any test. this family is the same even if the test is allowed to use an oracle of polynomial size, and it can be constructed in logspace (without using an oracle).
a deterministic poly(log log n)-time n-processor algorithm for linear programming in fixed dimension it is shown that for any fixed number of variables, the linear programming problems with n linear inequalities can be solved deterministically by n parallel processors in sub-logarithmic time. the parallel time bound is o((log log n)d) where d is the number of variables. in the one-dimensional case this bound is optimal.
running time and program size for self-assembled squares. recently rothemund and winfree [6] have considered the program size complexity of constructing squares by self-assembly. here, we consider the time complexity of such constructions using a natural generalization of the tile assembly model defined in [6]. in the generalized model, the rothemund-winfree construction of n \times n squares requires time &thgr;(n log n) and program size &thgr;(log n). we present a new construction for assembling n \times n squares which uses optimal time &thgr;(n) and program size &thgr;(\frac{log n}{log log n}). this program size is also optimal since it matches the bound dictated by kolmogorov complexity. our improved time is achieved by demonstrating a set of tiles for parallel self-assembly of binary counters. our improved program size is achieved by demonstrating that self-assembling systems can compute changes in the base representation of numbers. self-assembly is emerging as a useful paradigm for computation. in addition the development of a computational theory of self-assembly promises to provide a new conduit by which results and methods of theoretical computer science might be applied to problems of interest in biology and the physical sciences.
translations on a context free grammar two schemes for the specification of translations on a context-free grammar are proposed. the first scheme, called a generalized syntax directed translation (gsdt), consists of a context free grammar with a set of semantic rules associated with each production of the grammar. in a gsdt an input word is parsed according to the underlying context free grammar, and at each node of the tree, a finite number of translation strings are computed in terms of the translation strings defined at the descendants of that node. the functional relationship between the length of input and length of output for translations defined by gsdt's is investigated. the second method for the specification of translations is in terms of tree automata - finite automata with output, operating on derivation trees of a context free grammar. it is shown that tree automata provide an exact characterization for those gsdt's with a linear relationship between input and output length.
combinatorial optimization problems in self-assembly. self-assembly is the ubiquitous process by which simple objects autonomously assemble into intricate complexes. it has been suggested that intricate self-assembly processes will ultimately be used in circuit fabrication, nano-robotics, dna computation, and amorphous computing. in this paper, we study two combinatorial optimization problems related to efficient self-assembly of shapes in the tile assembly model of self-assembly proposed by rothemund and winfree [18]. the first is the minimum tile set problem, where the goal is to find the smallest tile system that uniquely produces a given shape. the second is the tile concentrations problem, where the goal is to decide on the relative concentrations of different types of tiles so that a tile system assembles as quickly as possible. the first problem is akin to finding optimum program size, and the second to finding optimum running time for a "program" to assemble the shape.self-assembly is the ubiquitous process by which simple objects autonomously assemble into intricate complexes. it has been suggested that intricate self-assembly processes will ultimately be used in circuit fabrication, nano-robotics, dna computation, and amorphous computing. in this paper, we study two combinatorial optimization problems related to efficient self-assembly of shapes in the tile assembly model of self-assembly proposed by rothemund and winfree [18]. the first is the minimum tile set problem, where the goal is to find the smallest tile system that uniquely produces a given shape. the second is the tile concentrations problem, where the goal is to decide on the relative concentrations of different types of tiles so that a tile system assembles as quickly as possible. the first problem is akin to finding optimum program size, and the second to finding optimum running time for a "program" to assemble the shape.we prove that the first problem is np-complete in general, and polynomial time solvable on trees and squares. in order to prove that the problem is in np, we present a polynomial time algorithm to verify whether a given tile system uniquely produces a given shape. this algorithm is analogous to a program verifier for traditional computational systems, and may well be of independent interest. for the second problem, we present a polynomial time $o(\log n)$-approximation algorithm that works for a large class of tile systems that we call partial order systems.
on basing one-way functions on np-hardness. we consider the possibility of basing one-way functions on np-hardness; that is, we study possible reductions from a worst-case decision problem to the task of average-case inverting a polynomial-time computable function f. our main findings are the following two negative results:if given y one can efficiently compute |f-1(y)| then the existence of a (randomized) reduction of np to the task of inverting f implies that conp ⊆ am. thus, it follows that such reductions cannot exist unless conp ⊆ am. for any function f, the existence of a (randomized) non-adaptive reduction of np to the task of average-case inverting f implies that conp ⊆ am.our work builds upon and improves on the previous works of feigenbaum and fortnow (siam journal on computing, 1993) and bogdanov and trevisan (44th focs, 2003), while capitalizing on the additional "computational structure" of the search problem associated with the task of inverting polynomial-time computable functions. we believe that our results illustrate the gain of directly studying the context of one-way functions rather than inferring results for it from a the general study of worst-case to average-case reductions.
recognizing primes in random polynomial time this paper is the first in a sequence of papers which will prove the existence of a random polynomial time algorithm for the set of primes. the techniques used are from arithmetic algebraic geometry and to a lesser extent algebraic and analytic number theory. the result complements the well known result of strassen and soloway that there exists a random polynomial time algorithm for the set of composites.
on randomized online scheduling. (math) we study one of the most basic problems in online scheduling. a sequence of jobs has to be scheduled on $m$ identical parallel machines so as to minimize the makespan. whenever a new job arrives, its processing time is known in advance. the job has to be scheduled immediately on one of the machines without knowledge of any future jobs. in the sixties graham presented the famous list scheduling algorithm which is $(2-{1\over m})$-competitive. in the last ten years deterministic online algorithms with an improved competitiveness have been developed. the first algorithm with a performance guarantee asymptotically smaller than 2 was 1.986- competitive. the competitive ratio was first improved to 1.945 and then to 1.923 and 1.9201. randomized competitive algorithms that are better than (known) deterministic algorithms were proposed for specific values of $m$, i.e. for $m\in\{2,\ldots,7\}$.(math) in this paper we present the first randomized online algorithm that performs better than known deterministic algorithms for general $m$. the algorithm is a combination of two deterministic scheduling strategies $a_1$ and $a_2$. initially, when starting the scheduling process, a scheduler chooses $a_i$, $i\in\{1,2\}$, with probability ${1\over 2}$ and then serves the entire job sequence using the chosen algorithm. the new randomized algorithm is 1.916-competitive. we prove that this performance cannot be achieved by a deterministic algorithm based on analysis techniques that have been used in the literature so far: using know techniques (or generalizations) it is impossible to prove a competitiveness smaller than 1.919 for any deterministic online algorithm. our results strictly limit the performance that can be achieved with existing techniques.