waashk/dblp huggingface dataset:
new lattice based cryptographic constructions. we introduce the use of fourier analysis on lattices as an integral part of a lattice-based construction. the tools we develop provide an elegant description of certain gaussian distributions around lattice points. our results include two cryptographic constructions that are based on the worst-case hardness of the unique shortest vector problem. the main result is a new public key cryptosystem whose security guarantee is considerably stronger than previous results (o(n1.5) instead of o(n7)). this provides the first alternative to ajtai and dwork's original 1996 cryptosystem. our second result is a family of collision resistant hash functions with an improved security guarantee in terms of the unique shortest vector problem. surprisingly, both results are derived from one theorem that presents two indistinguishable distributions on the segment [0, 1). it seems that this theorem can have further applications; as an example, we use it to solve an open problem in quantum computation related to the dihedral hidden subgroup problem.
the price of anarchy is independent of the network topology. we study the degradation in network performance caused by the selfish behavior of noncooperative network users. we consider a model of selfish routing in which the latency experienced by network traffic on an edge of the network is a function of the edge congestion, and network users are assumed to selfishly route traffic on minimum-latency paths. the quality of a routing of traffic is measured by the sum of travel times, also called the total latency. the outcome of selfish routing--a nash equilibrium--does not in general minimize the total latency; hence, selfish behavior carries the cost of decreased network performance. we quantify this degradation in network performance via the price of anarchy, the worst-possible ratio between the total latency of a nash equilibrium and of an optimal routing of the traffic. in this paper, we show that the price of anarchy is determined only by the simplest of networks. specifically, we prove that under weak hypotheses on the class of allowable edge latency functions, the worst-case ratio between the total latency of a nash equilibrium and of a minimum-latency routing for any multicommodity flow network is achieved by a single-commodity instance in a network of parallel links. in the special case where the class of allowable latency functions includes all of the constant functions, we prove that a network with only two parallel links suffices to achieve the worst-possible ratio. our guarantee that simple networks always furnish worst-possible examples provides a powerful method for computing the price of anarchy with respect to an arbitrary class of latency functions. we apply this method to function classes that have been well studied in the literature, including degree-bounded polynomials and queuing delay functions. these are the first tight analyses of the price of anarchy for significant classes of latency functions outside the class of linear functions.
on lattices, learning with errors, random linear codes, and cryptography. our main result is a reduction from worst-case lattice problems such as svp and sivp to a certain learning problem. this learning problem is a natural extension of the 'learning from parity with error' problem to higher moduli. it can also be viewed as the problem of decoding from a random linear code. this, we believe, gives a strong indication that these problems are hard. our reduction, however, is quantum. hence, an efficient solution to the learning problem implies a quantum algorithm for svp and sivp. a main open question is whether this reduction can be made classical.using the main result, we obtain a public-key cryptosystem whose hardness is based on the worst-case quantum hardness of svp and sivp. previous lattice-based public-key cryptosystems such as the one by ajtai and dwork were only based on unique-svp, a special case of svp. the new cryptosystem is much more efficient than previous cryptosystems: the public key is of size õ(n2) and encrypting a message increases its size by õ(n)(in previous cryptosystems these values are õ(n4) and õ(n2), respectively). in fact, under the assumption that all parties share a random bit string of length õ(n2), the size of the public key can be reduced to õ(n).
new trade-offs in cost-sharing mechanisms. a cost-sharing mechanism is a protocol that collects bids from a set of players, selects a subset of the players to receive a service (incurring a subset-dependent cost), and determines a price to charge each of these players. three standard requirements for cost-sharing mechanisms are incentive compatibility, which states that players are motivated to bid their true valuation for the service; budget-balance, meaning that the prices charged should recover the cost incurred; and efficiency, which states that the cost incurred and the valuations of the players served should be traded off in an optimal way. these three goals have been known to be mutually incompatible for thirty years. as a result, nearly all work on cost-sharing mechanisms in the economics and theoretical computer science literatures has focused on achieving two of these goals while completely ignoring the third.we show that incentive-compatibility, budget-balance, and approximate efficiency are simultaneously achievable for a wide range of cost functions, where efficiency is measured using the social cost---the sum of the incurred service cost and the excluded valuations. in particular, we prove such guarantees for well-known mechanisms for all submodular cost functions and for the steiner tree cost function. we also prove a generic, quantifiable trade-off between the objectives of efficiency and budget-balance in groupstrategyproof cost-sharing mechanisms.
lattice problems and norm embeddings. we present reductions from lattice problems in the l2 norm to the corresponding problems in other norms such as l1, l∞ (and in fact in any other lp norm where 1 ≤ p ≤ ∞). we consider lattice problems such as the shortest vector problem, shortest independent vector problem, closest vector problem and the closest vector problem with preprocessing. most reductions are simple and follow from known constructions of embeddings of normed spaces.among other things, our reductions imply that the shortest vector problem in the l1 norm and the closest vector problem with preprocessing in the l∞ norm are hard to approximate to within any constant (and beyond). previously, the former problem was known to be hard to approximate to within 2-ε, while no hardness result was known for the latter problem.
context-free grammars on trees in this paper we discuss still another version of indexed grammars 1 and macro grammars3,gaining some geometric intuition about the structure of these systems. an ordinary context-free grammar is a rewriting system for strings; we find that a macro grammar is a rewriting system for trees. cf grammars on strings form a special case since strings can be thought of as trees without branching nodes. we consider the special case of finite-state grammars in this report. we define the tree analogue of a non deterministic generalized sequential machine and obtain results about the domain and range of such a mapping. we relate these results to the theory of generalized finite automata6.
the quantum adiabatic optimization algorithm and local minima. the quantum adiabatic optimization algorithm uses the adiabatic theorem from quantum physics to minimize a function by interpolation between two hamiltonians. the quantum wave function can sometimes tunnel through significant obstacles. however it can also sometimes get stuck in local minima, even for fairly simple problems. an initial hamiltonian which insufficiently mixes computational basis states is analogous to a poorly mixing markov transition rule. we study a physical system -- the ising quantum chain with alternating sector interaction defects, but constant transverse field -- which is equivalent to applying the quantum adiabatic algorithm to a particular sat problem. we prove that for a constant range of values for the transverse field, the spectral gap is exponentially small in the sector length. indeed, we prove that there are exponentially many eigenvalues all exponentially close to the ground state energy. applying the adiabatic theorem therefore takes exponential time, even for this simple problem.
tree-oriented proofs of some theorems on context-free and indexed languages in this paper we study some applications and generalizations of the yield theorem: the yield of a recognizable set of trees (dendrolanguage) is an indexed language [1]. standard results on context-free languages can be obtained quickly using this theorem. we consider here the peters-ritchie theorem [4]: the language analyzable by a finite set of cs rules is cf. an extension of the yield theorem reads: the yield of a cf set of trees is an indexed language. we prove some closure properties of cf sets of trees. applying the yield theorem, we obtain properties of indexed languages. as a special result, we can solve the infiniteness problem for such languages.
universal games of incomplete information we consider two-person games of incomplete information in which certain portions of positions are private to each player and cannot be viewed by the opponent. we present various games of incomplete information which are universal for all reasonable games. the problem of determining the outcome of these universal games from a given initial position is shown to be complete in doubly-exponential time. we also define &ldquo;private alternating turing machines&rdquo; which are alternating turing machines with certain tapes and portions of states private to universal states. the time and space complexity of these machines is characterized in terms of the time complexity of deterministic turing machines, with single and double exponential jumps. we also consider blindfold games, which are restricted games in which the second player is not allowed to modify the common position. we show various blindfold games to have exponential space complete outcome problems and to be universal for reasonable blindfold games. we define &ldquo;blind alternating turing machines&rdquo; which are private alternating turing machines with the restriction that the universal states cannot modify the public tapes and public portion of states. a single exponential jump characterizes the relation between the space complexity of deterministic turing machines.
a new family of cayley expanders (?). we assume that for some fixed large enough integer d, the symmetric group sd can be generated as an expander using d1/30 generators. under this assumption, we explicitly construct an infinite family of groups gn, and explicit sets of generators yn ⊂ gn, such that all generating sets have bounded size (at most d1/7), and the associated cayley graphs are all expanders. the groups gn above are very simple, and completely different from previous known examples of expanding groups. indeed, gn is (essentially) all symmetries of the d-regular tree of depth n. the proof is completely elementary, using only simple combinatorics and linear algebra. the recursive structure of the groups gn (iterated wreath products of the alternating group ad) allows for an inductive proof of expansion, using the group theoretic analogue [4] of the zig-zag graph product of [38]. the explicit construction of the generating sets yn uses an efficient algorithm for solving certain equations over these groups, which relies on the work of [33] on the commutator width of perfect groups.we stress that our assumption above on weak expansion in the symmetric group is an open problem. we conjecture that it holds for all d. we discuss known results related to its likelihood in the paper.
logics for probabilistic programming (extended abstract) this paper introduces a logic for probabilistic programming+ prob-dl (for probabilistic dynamic logic; see section 2 for a formal definition). this logic has &ldquo;dynamic&rdquo; modal operators in which programs appear, as in pratt's [1976] dynamic logic dl. however the programs of prob-dl contain constructs for probabilistic branching and looping whereas dl is restricted to nondeterministic programs. the formula {a}&sgr;p of prob-dl denotes &ldquo;with measure &ge;&sgr;, formula p holds after executing program a.&rdquo; in section 3, we show that prob-dl has a complete and consistent axiomatization, (using techniques derived from parikh's [1978] completeness proof for the propositional dynamic logic). section 4 presents a probabilistic quantified boolean logic (prob-qbf) which also has applications to probabilistic programming.
testing monotone high-dimensional distributions. a monotone distribution p over a (partially) ordered domain has p(y) ≥ p(x) if y ≥ x in the order. we study several natural problems of testing properties of monotone distributions over the n-dimensional boolean cube, given access to random draws from the distribution being tested. we give a poly(n)-time algorithm for testing whether a monotone distribution is equivalent to or ε-far (in the l1 norm) from the uniform distribution. a key ingredient of the algorithm is a generalization of a known isoperimetric inequality for the boolean cube. we also introduce a method for proving lower bounds on testing monotone distributions over the n-dimensional boolean cube, based on a new decomposition technique for monotone distributions. we use this method to show that our uniformity testing algorithm is optimal up to polylog(n) factors, and also to give exponential lower bounds on the complexity of several other problems (testing whether a monotone distribution is identical to or ε-far from a fixed known monotone product distribution and approximating the entropy of an unknown monotone distribution).
symmetric complementation this paper introduces a class of 1 player games of perfect information, which we call complementing games;; the player is allowed moves which complement the value of successive plays. a complementing game is symmetric if all noncomplement moves are reversible (i.e., form a symmetric relation). these games are naturally related to a class of machines we call symmetric complementing machines. symmetric nondeterministic machines were studied in [lewis and papadimitriou, 80]; they are identical to our symmetric complementing machines with complement moves allowed only on termination. (a companion paper to appear describes the computational complexity of symmetric complementing and alternating machines.) of particular interest is the complexity class -&-sgr;(@@@@) csymlog, which contains the outcome problem of symmetric complementing games with constant complement bound with game positions encoded in log space, and next move relations computable in log space. we show that the decision problem for a restricted quantified boolean logic -&-sgr;(@@@@) qbf@@@@ is complete in -&-sgr;(@@@@) csymlog.
lower bounds for leader election and collective coin-flipping in the perfect information model. collective coin-flipping is the problem of producing common random bits in a distributed computing environment with adversarial faults. we consider the perfect information model: all communication is by broadcast and corrupt players are computationally unbounded. protocols in this model may involve many asynchronous rounds. we assume that honest players communicate only uniformly random bits. we demonstrate that any n-player coin-flipping protocol that is resilient against corrupt coalitions of linear size must use either at least [1/2 - o(1)]log* n communication rounds or at least [log(2k-1) n]1-o(1) communication bits in the kth round, where log(j) denotes the logarithm iterated j times. in particular, protocols using one bit per round require [1/2 - o(1)]log* n rounds. these bounds also apply to the leader election problem. the primary component of this result is a new bound on the influence of random sets of variables on boolean functions. finally, in the one-round case, using other methods we prove a new bound on the influence of sets of variables of size $\beta n$ for $\beta > 1/3$.
space-bounded hierarchies and probabilistic computations this paper studies two aspects of the power of space-bounded probabilistic turing machines. section 2 presents a simple alternative proof of simon's recent result [13] that space-bounded probabilistic complexity classes are closed under complement. section 3 demonstrates that any language in the log n space hierarchy can be recognized by an log n space-bounded probabilistic turing machine with small error; this is a generalization of gill's result that any language in nspace(log n) can be recognized by such a machine the second result raises interesting questions about space hierarchies, which are considered in section 4. the usual definition is in terms of space-bounded alternating turing machines with a constant number of alternations [4].
random matroids we introduce a new random structure generalizing matroids. these random matroids allow us to develop general techniques for solving hard combinatorial optimization problems with random inputs.
distributed algorithms for synchronizing interprocess communication within real time this paper considers a fixed (possibly infinite) set &pgr; of distributed asynchronous processes which at various times are willing to communicate with each other. we describe probabilistic algorithms for synchronizing this communication with boolean &ldquo;flag&rdquo; variables, each of which can be written by only one process and read by at most one other process. with very few assumptions (the speeds of processes may vary in time within fixed arbitrary bounds, and the processes may be willing to communicate with a time varying set of processes (but bounded in number), and no probability assumptions about system behavior) we show our synchronization algorithms have real time response: if a pair of processes are mutually willing to communicate within a constant time interval, they establish communication in that interval, with high likelihood (for the worst case behavior of the system). our communication model and synchronization algorithms are quite robust. they are applied to solve a large class of real time resource synchronization problems, as well as real time implementation of the synchronization primitives of hoare's multiprocessing language csp.
polling: a new randomized sampling technique for computational geometry we introduce a new randomized sampling technique, called polling which has applications to deriving efficient parallel algorithms. as an example of its use in computational geometry, we present an optimal parallel randomized algorithm for intersection of half-spaces in three dimensions. because of well-known reductions, our methods also yield equally efficient algorithms for fundamental problems like the convex hull in three dimensions, voronoi diagram of point sites on a plane and euclidean minimal spanning tree. our algorithms run in time t = o(logn) for worst-case inputs and uses p = o(n) processors in a crew pram model where n is the input size. they are randomized in the sense that they use a total of only o(log2 n) random bits and terminate in the claimed time bound with probability 1 - n-&agr; for any &agr; > 0. they are also optimal in p . t product since the sequential time bound for all these problems is &ohgr;(nlogn). the best known determistic parallel algorithms for 2-d voronoi-diagram and 3-d convex hull run in o(log2 n) and o(log2 nlog * n) time respectively while using o(n) processors.
a logarithmic time sort for linear size networks a randomized algorithm that sorts on an n node network with constant valence in o(log n) time is given. more particularly, the algorithm sorts n items on an n-node cube-connected cycles graph, and, for some constant k, for all large enough &agr;, it terminates within k&agr; log n time with probability at least 1 - n-&agr;.
undirected st-connectivity in log-space. we present a deterministic, log-space algorithm that solves st-connectivity in undirected graphs. the previous bound on the space complexity of undirected st-connectivity was log4/3 obtained by armoni, ta-shma, wigderson and zhou [9]. as undirected st-connectivity is complete for the class of problems solvable by symmetric, non-deterministic, log-space computations (the class sl), this algorithm implies that sl = l (where l is the class of problems solvable by deterministic log-space computations). independent of our work (and using different techniques), trifonov [45] has presented an o(log n log log n)-space, deterministic algorithm for undirected st-connectivity.our algorithm also implies a way to construct in log-space a fixed sequence of directions that guides a deterministic walk through all of the vertices of any connected graph. specifically, we give log-space constructible universal-traversal sequences for graphs with restricted labelling and log-space constructible universal-exploration sequences for general graphs.
pseudorandom walks on regular digraphs and the rl vs. l problem. we revisit the general rl vs. l question, obtaining the following results. generalizing reingold's techniques to directed graphs, we present a deterministic, log-space algorithm that given a regular directed graph g (or, more generally, a digraph with eulerian connected components) and two vertices s and t, finds a path between s and t if one exists.if we restrict ourselves to directed graphs that are regular and consistently labelled, then we are able to produce pseudorandom walks for such graphs in logarithmic space (this result already found an independent application).we prove that if (2) could be generalized to all regular directed graphs (including ones that are not consistently labelled) then l=rl. we do so by exhibiting a new complete promise problem for rl, and showing that such a problem can be solved in deterministic logarithmic space given a log-space pseudorandom walk generator for regular directed graphs.
the predicate elimination strategy in theorem proving the predicate elimination strategy is a complete resolution proof strategy for multi-predicate formulas. essentially, the procedure focuses on one of the predicate symbols p, and attempts to deduce clauses independent of p by means of resolution in which only predicates in p are &ldquo;resolved away&rdquo; from parent clauses. the completeness theorem states that one can in this way, deduce an unsatisfiable p-independent set of clauses, provided the given set is unsatisfiable. the strategy is then extended to a suitable form of semantic resolution. this leads to the following strategy: in the attempt to deduce an unsatisfiable p-independent set of clauses, apply elementary resolution to &ldquo;resolve away&rdquo; predicates in p only from parent clauses, one of which has all of its predicates in p positive (negative).
a quasi-polynomial time approximation scheme for minimum weight triangulation. the minimum weight triangulation problem is to find a triangulation t&ast; of minimum length for a given set of points p in the euclidean plane. it was one of the few longstanding open problems from the famous list of twelve problems with unknown complexity status, published by garey and johnson [1979]. very recently, the problem was shown to be np-hard by mulzer and rote [2006]. in this article, we present a quasi-polynomial time approximation scheme for minimum weight triangulation.