waashk/dblp huggingface dataset:
private approximation of np-hard functions. the notion of private approximation was introduced recently by feigenbaum, fong, strauss and wright. informally, a private approximation of a function f is another function f that approximates f in the usual sense, but does not yield any information on x other than what can be deduced from f(x). as such, f(x) is useful for private computation of f(x) (assuming that f can be computed more efficiently than f.in this work we examine the properties and limitations of this new notion. specifically, we show that for many np-hard problems, the privacy requirement precludes non-trivial approximation. this is the case even for problems that otherwise admit very good approximation (e.g., problems with ptas). on the other hand, we show that slightly relaxing the privacy requirement, by means of leaking &ldquo;just a few bits of informationrdquo; about x, again permits good approximation.
polynomial-time quantum algorithms for pell's equation and the principal ideal problem. we give polynomial-time quantum algorithms for three problems from computational algebraic number theory. the first is pell's equation. given a positive nonsquare integer d, pell's equation is x2 &minus; dy2 &equals; 1 and the goal is to find its integer solutions. factoring integers reduces to finding integer solutions of pell's equation, but a reduction in the other direction is not known and appears more difficult. the second problem we solve is the principal ideal problem in real quadratic number fields. this problem, which is at least as hard as solving pell's equation, is the one-way function underlying the buchmann--williams key exchange system, which is therefore broken by our quantum algorithm. finally, assuming the generalized riemann hypothesis, this algorithm can be used to compute the class group of a real quadratic number field.
fast quantum algorithms for computing the unit group and class group of a number field. computing the unit group and class group of a number field are two of the main tasks in computational algebraic number theory. factoring integers reduces to solving pell's equation, which is a special case of computing the unit group, but a reduction in the other direction is not known and appears more difficult. we give polynomial-time quantum algorithms for computing the unit group and class group when the number field has constant degree.
limitations of quantum coset states for graph isomorphism. it has been known for some time that graph isomorphism reduces to the hidden subgroup problem (hsp). what is more, most exponential speedups in quantum computation are obtained by solving instances of the hsp. a common feature of the resulting algorithms is the use of quantum coset states, which encode the hidden subgroup. an open question has been how hard it is to use these states to solve graph isomorphism. it was recently shown by moore, russell, and schulman [30] that only an exponentially small amount of information is available from one, or a pair of coset states. a potential source of power to exploit are entangled quantum measurements that act jointly on many states at once. we show that entangled quantum measurements on at least ω(n log n) coset states are necessary to get useful information for the case of graph isomorphism, matching an information theoretic upper bound. this may be viewed as a negative result because highly entangled measurements seem hard to implement in general. our main theorem is very general and also rules out using joint measurements on few coset states for some other groups, such as gl(n,fpm) and gn where g is finite and satisfies a suitable property.
polylogarithmic inapproximability. we provide the first hardness result of a polylogarithmic approximation ratio for a natural np-hard optimization problem. we show that for every fixed ε>0, the group-steiner-tree problem admits no efficient log2-ε k approximation, where k denotes the number of groups (or, alternatively, the input size), unless np has quasi polynomial las-vegas algorithms. this hardness result holds even for input graphs which are hierarchically well-separated trees, introduced by bartal [focs, 1996]. for these trees (and also for general trees), our bound is nearly tight with the log-squared approximation currently known. our results imply that for every fixed ε>0, the directed-steiner tree problem admits no log2-ε n--approximation, where n is the number of vertices in the graph, under the same complexity assumption.
a logic to reason about likelihood we present a logic ll which uses a modal operator l to help capture the notion of likely. despite the fact that no use is made of numbers, ll can capture many of the properties of likelihood in an intuitively appealing way. using standard techniques of modal logic, we give a complete axiomatization for ll and show that satisfiability of ll formulas can be decided in exponential time. we discuss how the logic might be used in areas where decision making is crucial, such as management and medical diagnosis, and conclude by using ll to give a formal proof of correctness of a protocol for exchanging secrets.
rational secret sharing and multiparty computation: extended abstract. we consider the problems of secret sharing and multiparty computation, assuming that agents prefer to get the secret (resp., function value) to not getting it, and secondarily, prefer that as few as possible of the other agents get it. we show that, under these assumptions, neither secret sharing nor multiparty function computation is possible using a mechanism that has a fixed running time. however, we show that both are possible using randomized mechanisms with constant expected running time.
a patent problem for abstract programming languages: machine-independent computations a programming language may be viewed as an acceptable numbering of the partial recursive functions, with &ldquo;semantics&rdquo; the mapping from programs onto the functions computed [1]. (in this view, syntax receives little attention, although it is best to consider it as a characteristic function of a recursive set of indices instead of allowing all natural numbers. such a view is natural for the usual arithmetizations, and eliminates some possible confusions, for example in interpreting the recursion theorem for pairs of numberings.) the virtue of functional semantics is that the semantic range is a machine-independent class. the abstract view in which details of the semantic mapping are ignored, in which the function assigned to a program is &ldquo;the one it computes,&rdquo; with the enumeration and s-m-n theorems assumed to compensate for the lost detail, has found only a restricted application to programning-language problems. computational complexity, in the successful abstraction by blum [2], is an attempt to provide more semantic structure without introducing a tenacious machine-dependence. the blum measures are not themselves suitable as a semantic range. two programs may have the same measure function, yet compute wildly different functions in widly different ways; other programs, intuitively very similar, may have wildly different measure functions [3]. a composite semantics of a function computed and a measure function is much like the approach suggested here: using formal computation functions as the semantic range.
a new grammatical transformation into ll(k) form (extended abstract) for some time, it has been recognized that left-to-right deterministic top-down parsing has a number of features to recommend it. the logic of such a parser is easily expressed as a one-state pushdown machine, and very flexible translations can readily be performed in conjunction with top-down processing. the major difficulty with this style of parsing is that there are relatively few grammars which satisfy the rather restrictive requirements to admit of top-down parsing (the ll(k) grammars), in comparsion with grammars that can be parsed deterministically bottom-up (the lr(k) grammars). there has been some research along the lines of trying to apply transformations to non-ll(k) grammars in order to convert them into equivalent ll(k) form [1,2,3]; the most successful approach has been that of rosenkrantz and lewis [4]. they define class of grammars, the lc(k) grammars, which can be parsed in a mixed hybrid of top-down bottom-up techniques; this class strictly includes the ll(k) grammars, as well as many interesting but non-ll(k) grammars. they then provide a deterministic algorithm for converting any lc(k) grammar into an equivalent ll(k) grammar. this work is a generalization of, and in the same spirit as, the lewis and rosenkrantz program. we investigate a new hybrid parsing method, basically bottom-up in character, but which contains a minimal infusion of top-down ideas. we consider the class of grammars which can be parsed by this method, and observe that it strictly includes the class of lc(k) grammars. then we exhibit an algorithm for deriving from any such grammar an equivalent ll(k) grammar; this derived grammar is also as &ldquo;useful&rdquo; as the original one in directing compilation activities, for it can support translations equivalent to those supportable by the original grammar.
transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals. genomes frequently evolve by reversals &rgr;(i,j) that transform a gene order &pgr;1 &hellip; &pgr;i&pgr;i+1 &hellip; &pgr;j-1&pgr;j &hellip; &pgr;n into &pgr;1 &hellip; &pgr;i&pgr;j-1 &hellip; &pgr;i+1&pgr;j &hellip; &pgr;n. reversal distance between permutations &pgr; and &sgr;is the minimum number of reversals to transform &pgr; into &agr;. analysis of genome rearrangements in molecular biology started in the late 1930's, when dobzhansky and sturtevant published a milestone paper presenting a rearrangement scenario with 17 inversions between the species of drosophilia. analysis of genomes evolving by inversions leads to a combinatorial problem of sorting by reversals studied in detail recently. we study sorting of signed permutations by reversals, a problem that adequately models rearrangements in a small genomes like chloroplast or mitochondrial dna. the previously suggested approximation algorithms for sorting signed permutations by reversals compute the reversal distance between permutations with an astonishing accuracy for both simulated and biological data. we prove a duality theorem explaining this intriguing performance and show that there exists a &ldquo;hidden&rdquo; parameter that allows one to compute the reversal distance between signed permutations in polynomial time.
on coresets for k-means and k-median clustering. in this paper, we show the existence of small coresets for the problems of computing k-median and k-means clustering for points in low dimension. in other words, we show that given a point set p in rd, one can compute a weighted set s ⊆ p, of size o(k ε-d log n), such that one can compute the k-median/means clustering on s instead of on p, and get an (1+ε)-approximation. as a result, we improve the fastest known algorithms for (1+ε)-approximate k-means and k-median. our algorithms have linear running time for a fixed k and ε. in addition, we can maintain the (1+ε)-approximate k-median or k-means clustering of a stream when points are being only inserted, using polylogarithmic space and update time.
computability and completeness in logics of programs (preliminary report) dynamic logic is a generalization of first order logic in which quantifiers of the form &ldquo;for all &khgr;...&rdquo; are replaced by phrases of the form &ldquo;after executing program &agr;...&rdquo;. this logic subsumes most existing first-order logics of programs that manipulate their environment, including floyd's and hoare's logics of partial correctness and manna and waldinger's logic of total correctness, yet is more closely related to classical first-order logic than any other proposed logic of programs. we consider two issues: how hard is the validity problem for the formulae of dynamic logic, and how might one axiomatize dynamic logic? we give bounds on the validity problem for some special cases, including a &pgr;02-completeness result for the partial correctness theories of uninterpreted flowchart programs. we also demonstrate the completeness of an axiomatization of dynamic logic relative to arithmetic.
a complete axiomatic system for proving deductions about recursive programs denoting a version of hoare's system for proving partial correctness of recursive programs by h, we present an extension d which may be thought of as h &ugr; {@@@@,@@@@,@@@@,@@@@} &ugr; h-1, including the rules of h, four special purpose rules and inverse rules to those of hoare. d is shown to be a complete system (in cook's sense) for proving deductions of the form &sgr;1,....&sgr;n @@@@ &sgr; over a language, the wff's of which are assertions in some assertion language l and partial correctness specifications of the form p(&agr;)q. all valid formulae of l are taken as axioms of d. it is shown that d is sufficient for proving partial correctness, total correctness and program equivalence as well as other important properties of programs, the proofs of which are impossible in h. the entire presentation is worked out in the framework of nondeterministic programs employing iteration and mutually recursive procedures.
completeness in two-party secure computation: a computational view. a secure function evaluation (sfe) of a two-variable function f(·,·) is a protocol that allows two parties with inputs x and y to evaluate f(x,y) in a manner where neither party learns "more than is necessary". a rich body of work deals with the study of completeness for secure two-party computation. a function f is complete for sfe if a protocol for securely evaluating f allows the secure evaluation of all (efficiently computable) functions. the questions investigated are which functions are complete for sfe, which functions have sfe protocols unconditionally and whether there are functions that are neither complete nor have efficient sfe protocols.the previous study of these questions was mainly conducted from an information theoretic point of view and provided strong answers in the form of combinatorial properties. however, we show that there are major differences between the information theoretic and computational settings. in particular, we show functions that are considered as having sfe unconditionally by the combinatorial criteria but are actually complete in the computational setting. we initiate the fully computational study of these fundamental questions. somewhat surprisingly, we manage to provide an almost full characterization of the complete functions in this model as well. more precisely, we present a computational criterion (called computational row non-transitivity) for a function f to be complete for the asymmetric case. furthermore, we show a matching criterion called computational row transitivity for f to have a simple sfe (based on no additional assumptions). this criterion is close to the negation of the computational row non-transitivity and thus we essentially characterize all "nice" functions as either complete or having sfe unconditionally.
probabilistic temporal logics for finite and bounded models we present two (closely-related) propositional probabilistic temporal logics based on temporal logics of branching time as introduced by ben-ari, pnueli and manna and by clarke and emerson. the first logic, ptlf, is interpreted over finite models, while the second logic, ptlb, which is an extension of the first one, is interpreted over infinite models with transition probabilities bounded away from 0. the logic ptlf allows us to reason about finite-state sequential probabilistic programs, and the logic ptlb allows us to reason about (finite-state) concurrent probabilistic programs, without any explicit reference to the actual values of their state-transition probabilities. a generalization of the tableau method yields exponential-time decision procedures for our logics, and complete axiomatizations of them are given. several meta-results, including the absence of a finite-model property for ptlb, and the connection between satisfiable formulae of ptlb and finite state concurrent probabilistic programs, are also discussed.
on isomorphisms and density of np and other complete sets if all np complete sets are isomorphic under deterministic polynomial time mappings (p-isomorphic) then p @@@@ np and if all ptape complete sets are p-isomorphic then p @@@@ ptape. we show that all np complete sets known (in the literature) are indeed p-isomorphic and so are the known ptape complete sets. thus showing that, inspite of the radically different origins and attempted simplification of these sets, all the known np complete sets are identical but for polynomially time bounded permutations. furthermore, if all np complete sets are p-isomorphic then they all must have similar densities and, for example, no language over a single letter alphabet can be np complete, nor can any sparse language over an arbitrary alphabet be np complete. we show that complete sets in exptime and exptape cannot be sparse and therefore they cannot be over a single letter alphabet. similarly, we show that the hardest context-sensitive languages cannot be sparse. we also relate the existence of sparse complete sets to the existence of simple combinatorial circuits for the corresponding truncated recognition problem of these languages.
sparse sets in np-p: exptime versus nexptime this paper investigates the structural properties of sets in np-p and shows that the computational difficulty of lower density sets in np depends explicitly on the relations between higher deterministic and nondeterministic time-bounded complexity classes. the paper exploits the recently discovered upward separation method, which shows for example that there exist sparse sets in np-pif and only if exptime @@@@ nexptime. in addition, the paper uses relativization techniques to determine logical possibilities, limitations of these proof techniques, and, for the first time, to exhibit structural differences between relativized np and conp.
every 2-csp allows nontrivial approximation. we use semidefinite programming to prove that any constraint satisfaction problem in two variables over any domain allows an efficient approximation algorithm that does provably better than picking a random assignment. to be more precise assume that each variable can take values in [d] and that each constraint rejects t out of the d2 possible input pairs. then, for some universal constant c, we can, in probabilistic polynomial time, find an assignment whose objective value is, on expectation, within a factor (1- t/d2(1- c/d2 log d)) of optimal.
some optimal inapproximability results. we prove optimal, up to an arbitrary &epsilon; > 0, inapproximability results for max-e k-sat for k &ge; 3, maximizing the number of satisfied linear equations in an over-determined system of linear equations modulo a prime p and set splitting. as a consequence of these results we get improved lower bounds for the efficient approximability of many optimization problems studied previously. in particular, for max-e2-sat, max-cut, max-di-cut, and vertex cover.
the cryptographic security of truncated linearly related variables in this paper we describe a polynomial time algorithm for computing the values of variables x1, &hellip; xk when some of their bits and some linear relationships between them are known. the algorithm is essentially optimal in its use of information in the sense that it can be applied as soon as the values of the xi become uniquely determined by the constraints. its cryptanalytic significance is demonstrated by two applications: breaking linear congruential generators whose outputs are truncated, and breaking blum's protocol for exchanging secrets.
on the advantage over a random assignment. we initiate the study of a new measure of approximation. this measure compares the performance of an approximation algorithm to the random assignment algorithm. this is a useful measure for optimization problems where the random assignment algorithm is known to give essentially the best possible polynomial time approximation. in this paper, we focus on this measure for the optimization problems max-lin-2 in which we need to maximize the number of satisfied linear equations in a system of linear equations modulo 2, and max-k-lin-2, a special case of the above problem in which each equation has at most k variables. the main techniques we use, in our approximation algorithms and inapproximability results for this measure, are from fourier analysis and derandomization.
classes of functions for computing on binary trees (extended abstract) this paper constitutes part of a general investigation into abstract computability on finitely generated free algebras (term algebras). the general idea is to determine an abstract computational process appropriate for computing on term algebras, the effectiveness of which should be apparent from the inductive structure of that domain, without reference to computability on the natural numbers (say, via coding).
randomly coloring graphs of girth at least five. we improve rapid mixing results for the simple glauber dynamics designed to generate a random k-coloring of a bounded-degree graph.let g be a graph with maximum degree δ = ω(log n), and girth ≥ 5. we prove that if k > α δ, where α ≈ 1.763 then glauber dynamics has mixing time o(n log n). if girth(g) ≥ 6 and k > β δ, where β ≈ 1.489 then glauber dynamics has mixing time o(n log n). this improves a recent result of molloy, who proved the same conclusion under the stronger assumptions that δ=ω(log n) and girth ω(log δ). our work suggests that rapid mixing results for high girth and degree graphs may extend to general graphs.analogous results hold for random graphs of average degree up to n¼, compared with polylog(n), which was the best previously known.some of our proofs rely on a new chernoff-hoeffding type bound, which only requires the random variables to be well-behaved with high probability. this tail inequality may be of independent interest.
the effect of collusion in congestion games. in this paper we initiate the study of how collusion alters the quality of solutions obtained in competitive games. the price of anarchy aims to measure the cost of the lack of coordination by comparing the quality of a nash equilibrium to that of a centrally designed optimal solution. this notion assumes that players act not only selfishly, but also independently. we propose a framework for modeling groups of colluding players, in which members of a coalition cooperate so as to selfishly maximize their collective welfare. clearly, such coalitions can improve the social welfare of the participants, but they can also harm the welfare of those outside the coalition. one might hope that the improvement for the coalition participants outweighs the negative effects on the others. this would imply that increased cooperation can only improved the overall solution quality of stable outcomes. however, increases in coordination can actually lead to significant decreases in total social welfare. in light of this, we propose the price of collusion as a measure of the possible negative effect of collusion, specifying the factor by which solution quality can deteriorate in the presence of coalitions. we give examples to show that the price of collusion can be arbitrarily high even in convex games. our main results show that in the context of load-balancing games, the price of collusion depends upon the disparity in market power among the game participants. we show that in some symmetric nonatomic games (where all users have access to the same set of strategies) increased cooperation always improves the solution quality, and in the discrete analogs of such games, the price of collusion is bounded by two.