waashk/dblp huggingface dataset:
the pcp theorem by gap amplification. the pcp theorem [arora and safra 1998; arora et. al. 1998] says that every language in np has a witness format that can be checked probabilistically by reading only a constant number of bits from the proof. the celebrated equivalence of this theorem and inapproximability of certain optimization problems, due to feige et al. [1996], has placed the pcp theorem at the heart of the area of inapproximability. in this work, we present a new proof of the pcp theorem that draws on this equivalence. we give a combinatorial proof for the np-hardness of approximating a certain constraint satisfaction problem, which can then be reinterpreted to yield the pcp theorem. our approach is to consider the unsat value of a constraint system, which is the smallest fraction of unsatisfied constraints, ranging over all possible assignments for the underlying variables. we describe a new combinatorial amplification transformation that doubles the unsat-value of a constraint-system, with only a linear blowup in the size of the system. the amplification step causes an increase in alphabet-size that is corrected by a (standard) pcp composition step. iterative application of these two steps yields a proof for the pcp theorem. the amplification lemma relies on a new notion of &ldquo;graph powering&rdquo; that can be applied to systems of binary constraints. this powering amplifies the unsat-value of a constraint system provided that the underlying graph structure is an expander. we also extend our amplification lemma towards construction of assignment testers (alternatively, pcps of proximity) which are slightly stronger objects than pcps. we then construct pcps and locally-testable codes whose length is linear up to a polylog factor, and whose correctness can be probabilistically verified by making a constant number of queries. namely, we prove sat &isin; pcp 1/2,1[log2(n&sdot;poly log n), o(1)].
on the fourier tails of bounded functions over the discrete cube. a theorem of bourgain [4] on fourier tails states that if f :(-1, 1)n → (-1, 1) is a boolean-valued function on the discrete cube such that for any k > 0, [σ|s| > k f(s)2 < k-1/2 + o(1), ] then essentially, f depends on only 2o(k) coordinates. this and related theorems such as friedgut's theorem [12], kkl [16], the fkn theorem [14], and the majority is stablest theorem [27] have proven useful for numerous results in theoretical computer science [3, 5, 9, 6, 7, 10, 11, 18, 19, 20, 24, 17, 25, 23, 22, 28, 29, 31].in this paper we prove an analogue to bourgain's theorem for bounded functions on the discrete cube, f : (n ⋺ [-1,1]); such functions arise naturally in hardness-of-approximation problems, as averages of boolean functions. specifically, we show that for every k > 0, if [σ|s| > k f(s)2 < exp(-o(k2 log k))] then essentially, f depends on only 2o(k) coordinates. we also show, perhaps surprisingly, that this result is sharp up to the log k factor in the exponent.our proof uses fourier analysis, as well as some extremal properties of the chebyshev polynomials.
a new multilayered pcp and the hardness of hypergraph vertex cover. given a k-uniform hypergraph, the ek-vertex-cover problem is to find the smallest subset of vertices that intersects every hyperedge. we present a new multilayered probabilistically checkable proof (pcp) construction that extends the raz verifier. this enables us to prove that ek-vertex-cover is np-hard to approximate within a factor of $(k-1-\epsilon)$ for arbitrary constants $\epsilon>0$ and $k\ge 3$. the result is nearly tight as this problem can be easily approximated within factor k. our construction makes use of the biased long-code and is analyzed using combinatorial properties of s-wise t-intersecting families of subsets.we also give a different proof that shows an inapproximability factor of $\lfloor \frac{k}{2} \rfloor -\eps$. in addition to being simpler, this proof also works for superconstant values of k up to (log n)1/c, where c > 1 is a fixed constant and n is the number of hyperedges.
conditional hardness for approximate coloring. we study the aprxcoloring$(q,q)$ problem: given a graph $g$, decide whether $\chi(g)\le q$ or $\chi(g)\ge q$. we present hardness results for this problem for any constants $3\le q<q$. for $q\ge4$, our result is based on khot's 2-to-1 label cover, which is conjectured to be np-hard [s. khot, proceedings of the 34th annual acm symposium on theory of computing, 2002, pp. 767-775]. for $q=3$, we base our hardness result on a certain &ldquo;${\rhd\hskip-0.5em<}$-shaped&rdquo; variant of his conjecture. previously no hardness result was known for $q=3$ and $q\ge6$. at the heart of our proof are tight bounds on generalized noise-stability quantities, which extend the recent work of mossel, o'donnell, and oleszkiewicz [&ldquo;noise stability of functions with low influences: invariance and optimality,&rdquo; ann. of math. (2), to appear] and should have wider applicability.
the importance of being biased. (math) we show that the minimum vertex cover problem is np-hard to approximate to within any factor smaller than $10\sqrt{5}-21 \approx 1.36067$, improving on the previously known hardness result for a $\frac{7}{6}$ factor.
on some generalizations of binary search classic binary search is extended to multidimensional search problems. these new search methods can efficiently solve several important problems of computer science. applications of these results to an open problem in the theory of computation are discussed yielding new insight into the lba problem.
approximation algorithms for combinatorial auctions with complement-free bidders. we exhibit three approximation algorithms for the allocation problem in combinatorial auctions with complement free bidders. the running time of these algorithms is polynomial in the number of items $m$ and in the number of bidders n, even though the "input size" is exponential in m. the first algorithm provides an o(log m) approximation. the second algorithm provides an o(√ m) approximation in the weaker model of value oracles. this algorithm is also incentive compatible. the third algorithm provides an improved 2-approximation for the more restricted case of "xos bidders", a class which strictly contains submodular bidders. we also prove lower bounds on the possible approximations achievable for these classes of bidders. these bounds are not tight and we leave the gaps as open problems.
truthful randomized mechanisms for combinatorial auctions. we design two computationally-efficient incentive-compatible mechanisms for combinatorial auctions with general bidder preferences. both mechanisms are randomized, and are incentive-compatible in the universal sense. this is in contrast to recent previous work that only addresses the weaker notion of incentive compatibility in expectation. the first mechanism obtains an o(√m)-approximation of the optimal social welfare for arbitrary bidder valuations -- this is the best approximation possible in polynomial time. the second one obtains an o(log2 m)-approximation for a subclass of bidder valuations that includes all submodular bidders. this improves over the best previously obtained incentive-compatible mechanism for this class which only provides an o(√ m)-approximation.
correcting errors without leaking partial information. this paper explores what kinds of information two parties must communicate in order to correct errors which occur in a shared secret string w. any bits they communicate must leak a significant amount of information about w --- that is, from the adversary's point of view, the entropy of w will drop significantly. nevertheless, we construct schemes with which alice and bob can prevent an adversary from learning any useful information about w. specifically, if the entropy of w is sufficiently high, then there is no function f(w) which the adversary can learn from the error-correction information with significant probability.this leads to several new results: (a) the design of noise-tolerant "perfectly one-way" hash functions in the sense of canetti et al. [7], which in turn leads to obfuscation of proximity queries for high entropy secrets w; (b) private fuzzy extractors [11], which allow one to extract uniformly random bits from noisy and nonuniform data w, while also insuring that no sensitive information about w is leaked; and (c) noise tolerance and stateless key re-use in the bounded storage model, resolving the main open problem of ding [10].the heart of our constructions is the design of strong randomness extractors with the property that the source w can be recovered from the extracted randomness and any string w' which is close to w.
on abstractions of parallel programs we discuss a parallel program model that allows a very general synchronization mechanism with a scheduler to control the progress of processes &ldquo;undergoing synchronization.&rdquo; we how to &ldquo;abstract&rdquo; the program, i.e. remove the scheduler, resulting in a simpler program. we then show that, for a large class of schedulers, a process can become deadlocked in the original program iff it can become deadlocked in the abstracted program.
on the possibility and impossibility of achieving clock synchronization it is known that clock synchronization can be achieved in the presence of faulty clocks numbering more than one-third of the total number of participating clocks provided that some authentication technique is used. without authentication the number of faults that can be tolerated has been an open question. here we show that if we restrict logical clocks to running within some linear function of real time, then clock synchronization is impossible, without authentication, when one-third or more of the processors are faulty. however, if there is a bound on the rate at which a processor can generate messages, then we show that clock synchronization is achievable, without authentication, as long as the faults do not disconnect the network. finally, we provide a lower bound on the closeness to which simultaneity can be achieved in the network as a function of the transmission and processing delay properties of the network.
a new look at fault tolerant network routing consider a communication network g in which a limited number of link and/or node faults f might occur. a routing &rgr; for the network (a fixed path between each pair of nodes) must be chosen without any knowledge of which components might become faulty. choosing a good routing corresponds to bounding the diameter of the surviving route graph r(g,&rgr;)/f, where two nonfaulty nodes are joined by an edge if there are no faults on the route between them. we prove a number of results concerning the diameter of surviving route graphs. we show that if &rgr; is a minimal length routing, then the diameter of r(g,&rgr;)/f can be on the order of the number of nodes of g, even if f consists of only a single node. however, if g is the n-dimensional cube, the diameter of r(g,&rgr;)/f&le;3 for any minimal length routing &rgr; and any set of faults f with |f|<n. we also show that if f consists only of edges and does not disconnect g, then the diameter of r(g,&rgr;)/f is &le; 3|f|+1, while if f consists only of nodes and does not disconnect g, then the diameter of r(g,&rgr;)/f is &le; the sum of the degrees of the nodes in f, where in both cases &rgr; is an arbitrary minimal length routing. we conclude with one of the most important contributions of this paper: a list of interesting and apparently difficult open problems.
optimal wiring between rectangles we consider the problem of wiring together two parallel rows of points under a variety of conditions. the options include whether we allow the rows to slide relative to one another, whether we use only rectilinear wires or arbitrary wires, and whether we can use wires in one layer or several layers. in almost all of these combinations of conditions, we can provide a polynomial-time algorithm to minimize the distance between the parallel rows of points. we also compare two fundamentally different wiring approaches, where one and two layers are used. we show that although the theoretical model implies that there can be great gains for the two-layer strategy, even in cases where no crossovers are required, when we consider typical design rules for laying out vlsi circuits there is no substantial advantage to the two-layer approach over the one-layer approach.
polynomial algorithms for multiple processor agreement reaching agreement in a distributed system while handling malfunctioning behavior is a central issue for reliable computer systems. all previous algorithms for reaching the agreement required an exponential number of messages to be sent, with or without authentication. we give polynomial algorithms for reaching (byzantine) agreement, both with and without the use of authentication protocols. we also prove that no matter what kind of information is exchanged, there is no way to reach agreement with fewer than t+1 rounds of exchange, where t is the upper bound on the number of faults.
bounded concurrent time-stamp systems are constructible concurrent time stamping is at the heart of solutions to some of the most fundamental problems in distributed computing. based on concurrent-time-stamp-systems, elegant and simple solutions to core problems such as &fnof;c&fnof;s-mutual-exclusion, construction of a multi-reader-multi-writer atomic register, probabilistic consensus,&hellip; were developed. unfortunately, the only known implementation of a concurrent time stamp system has been theoretically unsatisfying, since it requires unbounded size time-stamps, in other words, unbounded memory. not knowing if bounded concurrent-time-stamp-systems are at all constructible, researchers were led to constructing complicated problem-specific solutions to replace the simple unbounded ones. in this work, for the first time, a bounded implementation of a concurrent-time-stamp-system is presented. it provides a modular unbounded-to-bounded transformation of the simple unbounded solutions to problems such as above. it allows solutions to two formerly open problems, the bounded-probabilistic-consensus problem of abrahamson [a88] and the &fnof;i&fnof;o-@@@@-exclusion problem of [flbb85], and a more efficient construction of mrmw atomic registers.
graph decomposition is npc-a complete proof of holyer's conjecture an h-decomposition of a graph g = (v,e) is a partition of e into subgraphs isomorphic to h. given a fixed graph h, the h-decomposition problem is to determine whether an input graph g admits an h-decomposition. i. holyer (1980) conjectured that h-decomposition is np-complete whenever h is connected and has at least 3 edges. some partial results have been obtained during the last decade. a complete proof for holyer's conjecture is the content of this paper.
propositional representation of arithmetic proofs (preliminary version) equations f@@@@ &equil; g@@@@ between polynomial time computable functions can be represented by sets of propositional formulas. if f@@@@ &equil; g@@@@ is provable in certain arithmetic systems, then polynomial length proofs of the representing formulas exist in certain propositional systems. two cases of this phenomenon and a general theory are given.
competitive recommendation systems. a recommendation system tracks past purchases of a group of users to make product recommendations to individual members of the group. in this paper we present a notion of competitive recommendation systems, building on recent theoretical work on this subject. we reduce the problem of achieving competitiveness to a problem in matrix reconstruction. we then present a matrix reconstruction scheme that is competitive: it requires a small overhead in the number of users and products to be sampled, delivering in the process a net utility that closely approximates the best possible with full knowledge of all user-product preferences.
on the diameter of permutation groups we show that any group represented by generators that are cycles of bounded degree has o(n2) diameter, i.e., that the longest product of generators required to reach any permutation in the group is o(n2). we also show how such &ldquo;short&rdquo; products can be found in polynomial time. the techniques presented are applicable to generalizations of many permutation-group puzzles such as alexander's star and the hungarian rings.
touring a sequence of polygons. given a sequence of k polygons in the plane, a start point s, and a target point, t, we seek a shortest path that starts at s, visits in order each of the polygons, and ends at t. if the polygons are disjoint and convex, we give an algorithm running in time o(kn log (n/k)), where n is the total number of vertices specifying the polygons. we also extend our results to a case in which the convex polygons are arbitrarily intersecting and the subpath between any two consecutive polygons is constrained to lie within a simply connected region; the algorithm uses o(nk2 log n) time. our methods are simple and allow shortest path queries from s to a query point t to be answered in time o(k log n + m), where m is the combinatorial path length. we show that for nonconvex polygons this "touring polygons" problem is np-hard.the touring polygons problem is a strict generalization of some classic problems in computational geometry, including the safari problem, the zoo-keeper problem, and the watchman route problem in a simple polygon. our new results give an order of magnitude improvement in the running times of the safari problem and the watchman route problem: we solve the safari problem in o(n2 log n) time and the watchman route problem (through a fixed point s) in time o(n3 log n), compared with the previous time bounds of o(n3) and o(n4), respectively.
on the randomness complexity of efficient sampling. we consider the following question: can every efficiently samplable distribution be efficiently sampled, up to a small statistical distance, using roughly as much randomness as the length of its output? towards a study of this question we generalize the current theory of pseudorandomness and consider pseudorandom generators that fool non-boolean distinguishers (nb-prgs). we show a link between nb-prgs and a notion of function compression, introduced by harnik and naor [16]. (a compression algorithm for f should efficiently compress an input x in a way that will preserve the information needed to compute f(x).) by constructing nb-prgs, we answer the above question affirmatively under the following types of assumptions:cryptographic incompressibility assumptions (that are implied by, and seem weaker than, "exponential" cryptographic assumptions).nisan-wigderson style (average-case) incompressibility assumptions for polynomial-time computable functions.no assumptions are needed for answering our question affirmatively in the case of constant depth samplers.to complement the above, we extend an idea from [16] and establish the following win-win situation. if the answer to our main question is "no", then it is possible to construct a (weak variant of) collision-resistant hash function from any one-way permutation. the latter would be considered a surprising result, as a black-box construction of this type was ruled out by simon [35].finally, we present an application of nb-prgs to information theoretic cryptography. specifically, under any of the above assumptions, efficient protocols for information-theoretic secure multiparty computation never need to use (much) more randomness than communication.
optimal outlier removal in high-dimensional. we study the problem of finding an outlier-free subset of a set of points (or a probability distribution) in n-dimensional euclidean space. a point x is defined to be a &bgr;-outlier if there exists some direction w in which its squared distance from the mean along w is greater than &bgr; times the average squared distance from the mean along w [1]. our main theorem is that for any &egr;>0, there exists a (1-&egr;) fraction of the original distribution that has no o(\frac{n}{&egr;}(b+log \frac{n}{&egr;))-outliers, improving on the previous bound of o(n^7b/&egr;). this bound is shown to be nearly the best possible. the theorem is constructive, and results in a \frac{1}{1-&egr;} approximation to the following optimization problem: given a distribution &mgr; (i.e. the ability to sample from it), and a parameter &egr;>0, find the minimum &bgr; for which there exists a subset of probability at least (1-&egr;) with no &bgr;-outliers.
a simple polynomial-time rescaling algorithm for solving linear programs. the perceptron algorithm, developed mainly in the machine learning literature, is a simple greedy method for finding a feasible solution to a linear program (alternatively, for learning a threshold function). in spite of its exponential worst-case complexity, it is often quite useful, in part due to its noise-tolerance and also its overall simplicity. in this paper, we show that a randomized version of the perceptron algorithm along with periodic rescaling runs in polynomial-time. the resulting algorithm for linear programming has an elementary description and analysis.
complex tilings. we study the minimal complexity of tilings of a plane with a given tile set. we note that any tile set admits either no tiling or some tiling with \ooo(n) kolmogorov complexity of its (n\times n)-squares. we construct tile sets for which this bound is nearly tight: all tilings have complexity >n/r(n), given any unbounded computable monotone r. this adds a quantitative angle to classical results on non-recursivity of tilings -- that we also develop in terms of turing degrees of unsolvability.
fooling a two-way automaton or one pushdown store is better than one counter for two way machines (preliminary version) we define a language l and show that is cannot be recognized by any two way deterministic counter machine. it is done by fooling any given such machine; i.e. showing that if it accepts l' @@@@ l, then l'-l @@@@ &fgr;. for this purpose, an argument stronger than the well known crossing sequence argument needs to be introduced. since l is accepted by a two-way deterministic pushdown automaton, we consequently show that one pushdown stack is more powerful than one counter for deterministic two-way machines.
two tapes are better than one for nondeterministic machines it is known that k tapes are no better than two tapes for nondeterministic machines. we show here that two tapes are better than one. in fact, we show that two pushdown stores are better than one tape. also, k tapes are no better than two for nondeterministic reversal-bounded machines. we show here that two tapes are better than one for such machines. in fact, we show that two reversal-bounded pushdown stores are better than one reversal-bounded tape. we also show that for one-tape nondeterministic machines, unrestricted machines are better than reversal-bounded machines.