waashk/dblp huggingface dataset:
typical properties of winners and losers in discrete optimization. we present a probabilistic analysis for a large class of combinatorial optimization problems containing, e. g., all binary optimization problems defined by linear constraints and a linear objective function over (0,1)n. by parameterizing which constraints are of stochastic and which are of adversarial nature, we obtain a semi-random input model that enables us to do a general average-case analysis for a large class of optimization problems while at the same time taking care for the combinatorial structure of individual problems. our analysis covers various probability distributions for the choice of the stochastic numbers and includes smoothed analysis with gaussian and other kinds of perturbation models as a special case. in fact, we can exactly characterize the smoothed complexity of optimization problems in terms of their random worst-case complexity.a binary optimization problem has a polynomial smoothed complexity if and only if it has a pseudopolynomial complexity. our analysis is centered around structural properties of binary optimization problems, called winner, loser, and feasibility gaps. we show, when the coefficients of the objective function and/or some of the constraints are stochastic, then there usually exist a polynomial n-ω(1) gap between the best and the second best solution as well as a polynomial slack to the boundary of the constraints. similar to the condition number for linear programming, these gaps describe the sensitivity of the optimal solution to slight perturbations of the input and can be used to bound the necessary accuracy as well as the complexity for solving an instance. we exploit the gaps in form of an adaptive rounding scheme increasing the accuracy of calculation until the optimal solution is found. the strength of our techniques is illustrated by applications to various np-hard optimization problems from mathematical programming, network design, and scheduling for which we obtain the the first algorithms with polynomial average-case/smoothed complexity.
np might not be as easy as detecting unique solutions. we construct an oracle a such that p^a = parityp^a and np^a=exp^a. this relativized world has several amazing properties: - the oracle a gives the first relativized world where one can solve satisfiability on formulae with at most one assignment yet p is not equal to np. - the oracle a is the first where p^a = up^a >< np^a = conp^a. - the construction gives a much simpler proof than fenner, fortnow and kurtz of a relativized world where all np-complete sets are polynomial-time isomorphic. it is the first such computable oracle. - relative to $a$ we have a collapse of parityexp^a is in zpp^a in p^a/poly. we also create a different relativized world where there exists a set l in np that is np-complete under reductions that make one query to l but not under traditional many-one reductions. this contrasts with the result of buhrman, spaan and torenvliet showing that these two completeness notions for nexp coincide.
private approximation of search problems. many approximation algorithms have been presented in the last decades for ${\cal np}$-hard search problems. the focus of this paper is on cryptographic applications, where it is desirable to design algorithms which do not leak unnecessary information. specifically, we are interested in private approximation algorithms&mdash;efficient approximation algorithms whose output does not leak information not implied by the optimal solutions to the search problems. privacy requirements add constraints on the approximation algorithms; in particular, known approximation algorithms usually leak a lot of information. for functions, feigenbaum et al. [acm trans. algorithms, 2 (2006), pp. 435-472] presented a natural requirement that a private algorithm should not leak information not implied by the original function. generalizing this requirement to relations is not straightforward as an input may have many different outputs. we present a new definition that captures a minimal privacy requirement from such algorithms; applied to an input instance, it should not leak any information that is not implied by its collection of exact solutions. we argue that our privacy requirement is natural and quite minimal. we show that, even under this minimal definition of privacy, for well-studied problems such as vertex cover and max exact 3sat, private approximation algorithms are unlikely to exist even for poor approximation ratios. similarly to halevi et al. [in proceedings of the 33rd acm symposium on theory of computing, acm, new york, 2001, pp. 550-559], we define a relaxed notion of approximation algorithms that leak (a little) information, and demonstrate the applicability of this notion by showing near optimal approximation algorithms for max exact 3sat that leak a little information.
a new recursion-theoretic characterization of the polytime functions (extended abstract) we give a recursion-theoretic characterization of fp which describes polynomial time computation independently of any externally imposed resource bounds. in particular, this syntactic characterization avoids the explicit size bounds on recursion (and the initial function 2|x|.|y|) of cobham.
backing up in singly linked lists. we show how to reduce the time overhead for implementing two-way movement on a singly linked list to o(n&epsi;) per operation without modifying the list and without making use of storage other than a finite number of pointers into the list. we also prove a matching lower bound.these results add precision to the intuitive feeling that doubly linked lists are more efficient than singly linked lists, and quantify the efficiency gap in a read-only situation. we further analyze the number of points of access into the list (pointers) necessary for obtaining a desired value of &epsi;. we obtain tight tradeoffs which also separate the amortized and worst-case settings.our upper bound implies that read-only programs with singly-linked input can do string matching much faster than previously expected.
can finite samples detect singularities of real-valued functions? consider the following type of problem: there is an unknown function, f : rn &rarr; rm, there is also a black-box that on query x (&egr; rn) returns f(x). is there an algorithm that, using probes to the black-box, can figure out analytic information about f? (for an example: &ldquo;is f a polynomial?&rdquo;, &ldquo;is f a second order differentiable at x = (0,0,&hellip;,0)?&rdquo; etc.). clearly, for examples as these, if we bound the number of probes an algorithm has to settle for, no algorithm can carry the task. on the other hand, if one allows an infinite iteration of a &ldquo;probe compute and guess&rdquo; process, then, (quite surprisingly) for many such questions, there are algorithms that are guaranteed to be correct in all but finitely many of their guesses. we call such questions decidable in the limit, (dil). we analyze the class of dil problems and provide a necessary and sufficient condition for the membership of a decision problem in this class. we offer an algorithm for any dil problem, and apply it to several types of learning tasks. furthermore, if an a-priori probability distribution p, according to which f is being chosen, is available to the algorithm, then it can be strengthened into a finite algorithm. more precisely, for many distributions p, there exists a polynomial function, l, such that for every 0<&dgr;<1, there is an algorithm using at most l(log(&dgr;)) many probes that succeeds on more than (1&ndash;&dgr;) of the f's (as measured by p). we believe that the new approach presented here will be found useful for many further applications.
towards a theory of semantics and compilers for programming languages the concept of imbedding a programming language l into a formal system is introduced and used as the basis of defining the semantics &fgr; of the language. &fgr; is an operator which maps a program p in l onto a function. the pair (l, &fgr;) is called a programming system. if (l, &fgr;) and (l,' &fgr;') are two programming systems, a mapping &ggr; from l into l' is called a compiler. a compiler is said to be correct if &fgr;'(&ggr;(p)) &equil; &fgr;(p) for p in l. these ideas are illustrated in terms of two programming systems, one for recursive functions and the other for turing machines.
on the cryptographic security of single rsa bits the ability to &ldquo;hide&rdquo; one bit in trapdoor functions has recently gained much interest in cryptography research, and is of great importance in many transactions protocols. in this paper we study the cryptographic security of rsa bits. in particular, we show that unless the cryptanalyst can completely break the rsa encryption, any heuristic he uses to determine the least significant bit of the cleartext must have an error probability greater than 1&edivide;4&mdash;&egr; a similar result is shown for rabin's encryption scheme.
multi-prover interactive proofs: how to remove intractability assumptions quite complex cryptographic machinery has been developed based on the assumption that one-way functions exist, yet we know of only a few possible such candidates. it is important at this time to find alternative foundations to the design of secure cryptography. we introduce a new model of generalized interactive proofs as a step in this direction. we prove that all np languages have perfect zero-knowledge proof-systems in this model, without making any intractability assumptions. the generalized interactive-proof model consists of two computationally unbounded and untrusted provers, rather than one, who jointly agree on a strategy to convince the verifier of the truth of an assertion and then engage in a polynomial number of message exchanges with the verifier in their attempt to do so. to believe the validity of the assertion, the verifier must make sure that the two provers can not communicate with each other during the course of the proof process. thus, the complexity assumptions made in previous work, have been traded for a physical separation between the two provers. we call this new model the multi-prover interactive-proof model, and examine its properties and applicability to cryptography.
linear time bounds for median computations new upper and lower bounds are presented for the maximum number of comparisons, f(i,n), required to select the i-th largest of n numbers. an upper bound is found, by an analysis of a new selection algorithm, to be a linear function of n: f(i,n) &le; 103n/18 < 5.73n, for 1 &le; i &le; n. a lower bound is shown deductively to be: f(i,n) &ge; n+min(i,n&minus;i+l) + [log2(n)] &minus; 4, for 2 &le; i &le; n&minus;1, or, for the case of computing medians: f([n/2],n) &ge; 3n/2 &minus; 3
linear approximation of shortest superstrings we consider the following problem: given a collection of strings s1,&hellip;, sm, find the shortest string s such that each si appears as a substring (a consecutive block) of s. although this problem is known to be np-hard, a simple greedy procedure appears to do quite well and is routinely used in dna sequencing and data compression practice, namely: repeatedly merge the pair of (distinct) strings with maximum overlap until only one string remains. let n denote the length of the optimal superstring. a common conjecture states that the above greedy procedure produces a superstring of length o(n) (in fact, 2n), yet the only previous nontrivial bound known for any polynomial-time algorithm is a recent o(n log n) result. we show that the greedy algorithm does in fact achieve a constant factor approximation, proving an upper bound of 4n. furthermore, we present a simple modified version of the greedy algorithm that we show produces a superstring of length at most 3n. we also show the superstring problem to be maxsnp-hard, which implies that a polynomial-time approximation scheme for this problem is unlikely.
fast quantum byzantine agreement. we present a fast quantum byzantine agreement protocol that can reach agreement in o(1) expected communication rounds against a strong full information, dynamic adversary, tolerating up to the optimal t‹n3 faulty players in the synchronous setting, and up to t‹n4 faulty players for asynchronous systems. this should be contrasted with the known classical synchronous lower bound of ω(√ nlog n) [3] when t=(n).
designing programs that check their work a program correctness checker is an algorithm for checking the output of a computation. this paper defines the concept of a program checker. it designs program checkers for a few specific and carefully chosen problems in the class p of problems solvable in polynomial time. it also applies methods of modern cryptography, especially the idea of a probabilistic interactive proof, to the design of program checkers for group theoretic computations. finally it characterizes the problems that can be checked.
byzantine agreement in the full-information model in o(log n) rounds. we present a randomized byzantine agreement (ba) protocol with an expected running time of o(log n) rounds, in a synchronous full-information network of n players. for any constant ε > 0, the constructed protocol tolerates t non-adaptive byzantine faults, as long as n ≥ (4 + ε)t. in the full-information model, no restrictions are placed on the computational power of the faulty players or the information available to them. in particular, the faulty players may be infinitely powerful, and they can observe all communication among the honest players.this constitutes significant progress over the best known randomized ba protocol in the same setting which has a round-complexity of θ(t/log n) rounds [9], and answers an open problem posed by chor and dwork [10].
noise-tolerant learning, the parity problem, and the statistical query model. we describe a slightly subexponential time algorithm for learning parity functions in the presence of random classification noise, a problem closely related to several cryptographic and coding problems. our algorithm runs in polynomial time for the case of parity functions that depend on only the first o(log n log log n) bits of input, which provides the first known instance of an efficient noise-tolerant algorithm for a concept class that is not learnable in the statistical query model of kearns [1998]. thus, we demonstrate that the set of problems learnable in the statistical query model is a strict subset of those problems learnable in the presence of noise in the pac model.in coding-theory terms, what we give is a poly(n)-time algorithm for decoding linear k &times; n codes in the presence of random noise for the case of k = c log n log log n for some c > 0. (the case of k = o(log n) is trivial since one can just individually check each of the 2k possible messages and choose the one that yields the closest codeword.)a natural extension of the statistical query model is to allow queries about statistical properties that involve t-tuples of examples, as opposed to just single examples. the second result of this article is to show that any class of functions learnable (strongly or weakly) with t-wise queries for t = o(log n) is also weakly learnable with standard unary queries. hence, this natural extension to the statistical query model does not increase the set of weakly learnable functions.
size space tradeoffs for resolution. we investigate tradeoffs of various basic complexity measures such as size, space, and width. we show examples of formulas that have optimal proofs with respect to any one of these parameters, but optimizing one parameter must cost an increase in the other. these results have implications to the efficiency (or rather, inefficiency) of some commonly used sat solving heuristics. our proof relies on a novel connection of the variable space of a proof to the black-white pebbling measure of an underlying graph.
fast learning of k-term dnf formulas with queries this paper presents an algorithm that uses equivalence and membership queries to learn the class of k-term dnf formulas in time o(n&bull;2o(k)), where n is the number of input variables. this improves upon previous o(nk) bounds and allows one to learn dnf of o(log n) terms in polynomial time. we present the algorithm in its most natural form as a randomized algorithm, and then show how recent derandomization techniques can be used to make it deterministic. the algorithm is an exact learning algorithm, but one where the equivalance query hypotheses and the final output are general (not necessarily k-term) dnf formulas. for the special case of 2-term dnf formulas, we give a simpler version of our algorithm that uses at most 4n + 2 total membership and equivalence queries.
on effective procedures for speeding up algorithms this paper is concerned with the nature of speedups. let f be any recursive function. we show that there is no effective procedure for going from an algorithm for f to a significantly faster algorithm for f. on the other hand, there is an effective procedure for going from any algorithm to a faster algorithm, provided one has a bound on the size of the algorithm that does the computation faster for all inputs. if no bound on the size of the faster algorithm is known in advance, one can still obtain a pseudo speedup: this is a very fast algorithm which computes a variant of the function, one which differs from the original function on a finite number of inputs.
robust pcps of proximity, shorter pcps and applications to coding. we continue the study of the trade-off between the length of probabilistically checkable proofs (pcps) and their query complexity, establishing the following main results (which refer to proofs of satisfiability of circuits of size $n$): 1. we present pcps of length $\exp(o(\log\log n)^2)\cdot n$ that can be verified by making $o(\log\log n)$ boolean queries. 2. for every \epsilon>0, we present pcps of length $\exp(\log^\epsilon n)\cdot n$ that can be verified by making a constant number of boolean queries. in both cases, false assertions are rejected with constant probability (which may be set to be arbitrarily close to 1). the multiplicative overhead on the length of the proof, introduced by transforming a proof into a probabilistically checkable one, is just quasi polylogarithmic in the first case (of query complexity $o(\log\log n)$), and is $2^{(\log n)^\epsilon}$, for any $\epsilon > 0$, in the second case (of constant query complexity). our techniques include the introduction of a new variant of pcps that we call &ldquo;robust pcps of proximity.&rdquo; these new pcps facilitate proof composition, which is a central ingredient in the construction of pcp systems. (a related notion and its composition properties were discovered independently by dinur and reingold.) our main technical contribution is a construction of a &ldquo;length-efficient&rdquo; robust pcp of proximity. while the new construction uses many of the standard techniques used in pcp constructions, it does differ from previous constructions in fundamental ways, and in particular does not use the &ldquo;parallelization&rdquo; step of arora et al. [j. acm, 45 (1998), pp. 501-555]. the alternative approach may be of independent interest. we also obtain analogous quantitative results for locally testable codes. in addition, we introduce a relaxed notion of locally decodable codes and present such codes mapping $k$ information bits to codewords of length $k^{1+\epsilon}$ for any $\epsilon>0$.
some 3cnf properties are hard to test. for a boolean formula $\phi$ on n variables, the associated property $p_\phi$ is the collection of n-bit strings that satisfy $\phi$. we study the query complexity of tests that distinguish (with high probability) between strings in $p_\phi$ and strings that are far from $p_\phi$ in hamming distance. we prove that there are 3cnf formulae (with o(n) clauses) such that testing for the associated property requires $\omega(n)$ queries, even with adaptive tests. this contrasts with 2cnf formulae, whose associated properties are always testable with $o(\sqrt{n})$ queries [e. fischer et al., monotonicity testing over general poset domains, in proceedings of the 34th annual acm symposium on theory of computing, acm, new york, 2002, pp. 474--483]. notice that for every negative instance (i.e., an assignment that does not satisfy $\phi$) there are three bit queries that witness this fact. nevertheless, finding such a short witness requires reading a constant fraction of the input, even when the input is very far from satisfying the formula that is associated with the property.a property is linear if its elements form a linear space. we provide sufficient conditions for linear properties to be hard to test, and in the course of the proof include the following observations which are of independent interest: in the context of testing for linear properties, adaptive two-sided error tests have no more power than nonadaptive one-sided error tests. moreover, without loss of generality, any test for a linear property is a linear test. a linear test verifies that a portion of the input satisfies a set of linear constraints, which define the property, and rejects if and only if it finds a falsified constraint. a linear test is by definition nonadaptive and, when applied to linear properties, has a one-sided error. random low density parity check codes (which are known to have linear distance and constant rate) are not locally testable. in fact, testing such a code of length n requires $\omega(n)$ queries.
simple pcps with poly-log rate and query complexity. we give constructions of probabilistically checkable proofs (pcps) of length n . poly(log n) (to prove satisfiability of circuits of size n) that can verified by querying poly(log n) bits of the proof. we also give constructions of locally testable codes (ltcs) with similar parameters.previous constructions of short pcps (from [5]to [9]) relied extensively on properties of low degree multi-variate polynomials. in contrast, our constructions rely on new problems and techniques revolving around the properties of codes based on high degree polynomials in one variable (also known as reed-solomon codes). we show how to convert the problem of verifying the satisfaction of a circuit by a given assignment to the task of verifying that a given function is close to being a reed-solomon codeword, i.e., a univariate polynomial of specified degree. this reduction is simpler than the corresponding steps in previous reductions, and gives a new alternative to using the popular "sum-check protocol". we then give a new pcp for the special task of proving that a function is close to being a reed-solomon codeword. this step of the construction is by a self-contained recursion, and the only ingredient needed in the analysis is the bi-variate low-degree test of polischuk and spielman[27].note that our constructions yield ltcs first, which are then converted to pcps. in contrast, most recent constructions go in the opposite (and less natural) direction of getting ltcs from pcps.