waashk/dblp huggingface dataset:
exponential lower bound for 2-query locally decodable codes via a quantum argument. a locally decodable code (ldc) encodes n-bit strings x in m-bit codewords c(x) in such a way that one can recover any bit xi from a corrupted codeword by querying only a few bits of that word. we use a quantum argument to prove that ldcs with 2 classical queries require exponential length: m = 2ω(n). previously, this was known only for linear codes (goldreich et al., in: proceedings of 17th ieee conference on computation complexity, 2002, pp. 175-183). the proof proceeds by showing that a 2-query ldc can be decoded with a single quantum query, when defined in an appropriate sense. it goes on to establish an exponential lower bound on any 'l-query locally quantum-decodable code'. we extend our lower bounds to non-binary alphabets and also somewhat improve the polynomial lower bounds by katz and trevisan for ldcs with more than 2 queries. furthermore, we show that q quantum queries allow more succinct ldcs than the best known ldcs with q classical queries. finally, we give new classical lower bounds and quantum upper bounds for the setting of private information retrieval. in particular, we exhibit a quantum 2-server private information retrieval (pir) scheme with o(n3/10) qubits of communication, beating the o(n1/3) bits of communication of the best known classical 2-server pir.
buffer overflow management in qos switches. we consider two types of buffering policies that are used in network switches supporting quality of service (qos). in the fifo type, packets must be transmitted in the order in which they arrive; the constraint in this case is the limited buffer space. in the bounded-delay type, each packet has a maximum delay time by which it must be transmitted, or otherwise it is lost. we study the case of overloads resulting in packet loss. in our model, each packet has an intrinsic value, and the goal is to maximize the total value of transmitted packets.our main contribution is a thorough investigation of some natural greedy algorithms in various models. for the fifo model we prove tight bounds on the competitive ratio of the greedy algorithm that discards packets with the lowest value when an overflow occurs. we also prove that the greedy algorithm that drops the earliest packets among all low-value packets is the best greedy algorithm. this algorithm can be as much as 1.5 times better than the tail-drop greedy policy, which drops the latest lowest-value packets.in the bounded-delay model we show that the competitive ratio of any on-line algorithm for a uniform bounded-delay buffer is bounded away from 1, independent of the delay size. we analyze the greedy algorithm in the general case and in three special cases: delay bound 2, link bandwidth 1, and only two possible packet values.finally, we consider the off-line scenario. we give efficient optimal algorithms and study the relation between the bounded-delay and fifo models in this case.
graph partitioning using single commodity flows. we show that the sparsest cut in graphs with n vertices and m edges can be approximated within o(log2 n) factor in &otilde;(m + n3/2) time using polylogarithmic single commodity max-flow computations. previous algorithms are based on multicommodity flows that take time &otilde;(m + n2). our algorithm iteratively employs max-flow computations to embed an expander flow, thus providing a certificate of expansion. our technique can also be extended to yield an o(log2 n)-(pseudo-) approximation algorithm for the edge-separator problem with a similar running time.
on broadcast disk paging. broadcast disks are an emerging paradigm for massive data dissemination. in a broadcast disk, data is divided into n equal-sized pages, and pages are broadcast in a round-robin fashion by a server. broadcast disks are effective because many clients can simultaneously retrieve any transmitted data. paging is used by the clients to improve performance, much as in virtual memory systems. however, paging on broadcast disks differs from virtual memory paging in at least two fundamental aspects: a page fault in the broadcast disk model has a variable cost that depends on the requested page as well as the current state of the broadcast. prefetching is both natural and a provably essential mechanism for achieving significantly better competitive ratios in broadcast disk paging. in this paper, we design a deterministic algorithm that uses prefetching to achieve an o(n log k) competitive ratio for the broadcast disk paging problem, where k denotes the size of the client's cache. we also show a matching lower bound of $\omega(n\log k)$ that applies even when the adversary is not allowed to use prefetching. in contrast, we show that when prefetching is not allowed, no deterministic online algorithm can achieve a competitive ratio better than $\omega(nk)$. moreover, we show a lower bound of $\omega(n \log k)$ on the competitive ratio achievable by any nonprefetching randomized algorithm against an oblivious adversary. these lower bounds are trivially matched from above by known results about deterministic and randomized marking algorithms for paging. an interpretation of our results is that in the broadcast disk paging, prefetching is a perfect substitute for randomization.
hardness results for approximate hypergraph coloring. (math) guruswami et al [6] show the hardness of coloring 2-colorable 4-uniform hypergraphs on n vertices with &omega;(log log n \over log log log n}) colors assuming np $\not\subseteq$ dtime(no log log n)). we obtain a stronger hardness result for approximate coloring of p-colorable 4-uniform hypergraphs for any fixed integer p &rhoe; 7. we prove that there exists an absolute constant c &rho; 0 such that for every fixed integer p &rhoe; 7, it is hard to color a p-colorable 4-uniform hypergraph with (log n)cp colors assuming np $\not \subseteq$ dtime(2(log n)o(1)).this work builds on the idea of "covering complexity" of probabilistically checkable proof systems (pcps) developed in [6] and we introduce some new techniques as well. firstly, we define a new code which we call the split code. this is a variation of the long code, but much shorter in length and it reduces the proof size significantly. split codes enable us to exploit the special structure of the "outer pcp verifier" constructed via raz's parallel repetition theorem [18]. secondly, we make a novel use of the split codes over the domain gf(p) for a prime p. working over non-boolean domain in fact makes our proof technically simpler than the proof of guruswami at al [6].
on the power of unique 2-prover 1-round games. a 2-prover game is called unique if the answer of one prover uniquely determines the answer of the second prover and vice versa (we implicitly assume games to be one round games). the value of a 2-prover game is the maximum acceptance probability of the verifier over all the prover strategies. we make the following conjecture regarding the power of unique 2-prover games, which we call the unique games conjecture: the unique games conjecture: for arbitrarily small constants \zeta, \delta > 0, there exists a constant k = k(\zeta,\delta) such that it is np-hard to determine whether a unique 2-prover game with answers from a domain of size k has value at least 1-\zeta or at most \delta.we show that a positive resolution of this conjecture would imply the following hardness results: (1) for any 1/2 0, it is np-hard to distinguish between the instances of the problem 2-linear-equations mod 2 where either there exists an assignment that satisfies 1-\epsilon fraction of equations or no assignment can satisfy more than 1-\epsilon^t fraction of equations. as a corollary of this result, it is np-hard to approximate the min-2cnf-deletion problem within any constant factor. (2) for the constraint satisfaction problem where every constraint is the predicate not-all-equal(a,b,c) with a,b,c being ternary variables, it is np-hard to distinguish between the instances where either there exists an assignment that satisfies 1-\epsilon fraction of the constraints or no assignment satisfies more than 8/9 + \epsilon fraction of the constraints for an arbitrarily small constant \epsilon > 0. this problem is relavant for showing hardness of coloring 3-colorable 3-uniform hypergraphs. we also show that a variation of the unique games conjecture implies that for arbitrarily small constant \delta > 0, it is hard to find an independent set of size (\delta n) in a graph that is guaranteed to have an independent set of size \omega(n).the main idea in all the above results is to use the 2-prover game given by the unique games conjecture as an "outer verifier" and build new probabilistically checkable proof systems (pcps) on top of it. the uniqueness property plays a crucial role in the analysis of these pcps.in light of such interesting consequences, we think it is an important open problem to prove (or disprove) the unique games conjecture. we also present a semi-definite programming based algorithm for finding reasonable prover strategies for a unique 2-prover game. given a unique 2-prover game with value 1-\zeta and answers from a domain of size k, this algorithm finds prover strategies that make the verifier accept with probability 1-o(k^2 \zeta^{1/5} \sqrt{\log(1/\zeta)}). this result shows that the domain size k = k(\zeta, \delta) must be sufficiently large if the unique games conjecture is true.
low degree spanning trees of small weight. given $n$ points in the plane, the degree-$k$ spanning-tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most $k$. this paper addresses the problem of computing low-weight degree-$k$ spanning trees for $k>2$. it is shown that for an arbitrary collection of $n$ points in the plane, there exists a spanning tree of degree 3 whose weight is at most 1.5 times the weight of a minimum spanning tree. it is shown that there exists a spanning tree of degree 4 whose weight is at most 1.25 times the weight of a minimum spanning tree. these results solve open problems posed by papadimitriou and vazirani. moreover, if a minimum spanning tree is given as part of the input, the trees can be computed in $o(n)$ time. the results are generalized to points in higher dimensions. it is shown that for any $d \ge 3$, an arbitrary collection of points in $\re^d$ contains a spanning tree of degree 3 whose weight is at most 5/3 times the weight of a minimum spanning tree. this is the first paper that achieves factors better than 2 for these problems.
biconnectivity approximations and graph carvings a spanning tree in a graph is the smallest connected spanning subgraph. given a graph, how does one find the smallest (i.e., least number of edges) 2-connected spanning subgraph (connectivity refers to both edge and vertex connectivity, if not specified)? unfortunately, the problem is known to be np-hard. we consider the problem of finding an approximation to the smallest 2-connected subgraph, by an efficient algorithm. for 2-edge connectivity our algorithm guarantees a solution that is no more than 3/2 times the optimal. for 2-vertex connectivity our algorithm guarantees a solution that is no more than 5/3 times the optimal. the previous best approximation factor is 2 for each of these problems. the new algorithms (and their analyses) depend upon a structure called a carving of a graph, which is of independent interest. we show that approximating the optimal solution to within an additive constant is np-hard as well. we also consider the case where the graph has edge weights. we show that an approximation factor of 2 is possible in polynomial time for finding a k-edge connected spanning subgraph. this improves an approximation factor of 3 for k=2 due to [fj81], and extends it for any k (with an increased running time though).
founding cryptography on oblivious transfer suppose your netmail is being erratically censored by captain yossarian. whenever you send a message, he censors each bit of the message with probability 1/2, replacing each censored bit by some reserved character. well versed in such concepts as redundancy, this is no real problem to you. the question is, can it actually be turned around and used to your advantage? we answer this question strongly in the affirmative. we show that this protocol, more commonly known as oblivious transfer, can be used to simulate a more sophisticated protocol, known as oblivious circuit evaluation([y]). we also show that with such a communication channel, one can have completely noninteractive zero-knowledge proofs of statements in np. these results do not use any complexity-theoretic assumptions. we can show that they have applications to a variety of models in which oblivious transfer can be done.
a note on efficient zero-knowledge proofs and arguments (extended abstract) in this note, we present new zero-knowledge interactive proofs and arguments for languages in np. to show that x &egr; l, with an error probability of at most 2-k, our zero-knowledge proof system requires o(|x|c1)+o(lgc2|x|)k ideal bit commitments, where c1 and c2 depend only on l. this construction is the first in the ideal bit commitment model that achieves large values of k more efficiently than by running k independent iterations of the base interactive proof system. under suitable complexity assumptions, we exhibit zero knowledge arguments that require o(lgc|x|kl bits of communication, where c depends only on l, and l is the security parameter for the prover. this is the first construction in which the total amount of communication can be less than that needed to transmit the np witness. our protocols are based on efficiently checkable proofs for np[4].
concurrent and resettable zero-knowledge in poly-loalgorithm rounds. a proof is concurrent zero-knowledge if it remains zero-knowledge when many copies of the proof are run in an asynchronous environment, such as the internet. richardson and kilian have shown that there exists a concurrent zero-knowledge proof for any language in np, but with round complexity polynomial in the maximum number of concurrent proofs. in this paper, we present a concurrent zero-knowledge proof for all languages in np with a poly-logarithmic round complexity: specifically, &ohgr;(log^2 k) rounds given at most k concurrent proofs. finally, we show that a simple modification of our proof is a resettable zero-knowledge proof for np, with &ohgr;(log^2 k) rounds; previously known protocols required a polynomial number of rounds.
probabilistically checkable proofs with zero knowledge. we construct pcps with strong zero-knowledge properties. first, we construct polynomially bounded (in size) pcp''s for {\sf np} which can be checked using poly-logarithmic queries, with polynomially low error, yet are statistical zero-knowledge against an adversary that makes $u$ arbitrary queries, where $u$ can be set to any polynomial. second, we construct pcps for {\sf{nexptime}} that can be checked using polynomially many queries, yet are statistically zero-knowledge against any polynomially bounded adversary. these pcps are exponential in size and have exponentially low error. previously, it was only known how to construct zero-knowledge pcps with a constant error probability. \par in the course of constructing these pcp''s we abstract a tool we call {\em locking systems}. we provide the definition and also a locking system with very efficient parameters. this mechanism may be useful in other settings as well.
digital disks and a digital compactness measure an o(n2) time algorithm is presented that determines whether or not a given convex digital region is a digital disk. a new compactness measure for digital regions is introduced, and an algorithm to evaluate the compactness measure of convex digital regions is also presented.
digital straightness and convexity (extended abstract) we define straightness and convexity of regions in a digital picture. then it is shown that a few important properties satisfied by convex (euclidean) regions are also satisfied by convex digital regions. we extend the definition of digital convexity of regions to digital solids. efficient algorithms are presented that determine whether or not a digital region is convex, a digital arc is a digital straight line segment and a digital solid is convex.
generating random regular graphs. random regular graphs play a central role in combinatorics and theoretical computer science. in this paper, we analyze a simple algorithm introduced by steger and wormald [10] and prove that it produces an asymptotically uniform random regular graph in a polynomial time. precisely, for fixed d and n with d = o(n1/3&#x2212;&#x03b5;), it is shown that the algorithm generates an asymptotically uniform random d-regular graph on n vertices in time o(nd2). this confirms a conjecture of wormald. the key ingredient in the proof is a recently developed concentration inequality by the second author. the algorithm works for relatively large d in practical (quadratic) time and can be used to derive many properties of uniform random regular graphs.
an algebraic system for process structuring and interprocess communication an extension of regular expressions is introduced to represent the activities of synchronizing concurrent processes. a communication link is defined as an automaton (infinite) with one-to-one partial transformations, and communication protocol as an assignment of events to actions of a communication link. a synchronization problem is defined as a problem of concurrent decomposition of a process into a deadlock-free family of processes sharing a communication protocol. it is shown that it is decidable whether a finite family of sequential processes, communicating through a finite link, is deadlock-free or not.
measures of parallelism in alternating computation trees (extended abstract) we examine three ways of restricting the size (and shape) of the accepting computation trees of alternating turing machines. we continue study by examining bounds on the number of leaves in the tree (section 3), the 'width' of the tree (section 4), and the number of nodes at any level of the tree (section 5). each of these measures can be interpreted as a limit on the amount of parallelism permitted the computation.
lower bounds on the complexity of graph properties in this simple model, a decision tree algorithm must determine whether an unknown digraph on nodes {1, 2, &hellip;, n} has a given property by asking questions of the form &ldquo;is edge <i,j> in the graph?&rdquo;. the complexity of a property is the number of questions which must be asked in the worst case. aanderaa and rosenberg conjectured that any monotone, nontrivial, (isomorphism-invariant) n-node digraph property has complexity &ohgr;(n2). this bound was proved by rivest and vuillemin and subsequently improved to n2/4+&ogr;(n2). in part i, we give a bound of n2/2+&ogr;(n2). whether these properties are evasive remains open. in part ii, we investigate the power of randomness in recognizing these properties by considering randomized decision tree algorithms in which coins may be flipped to determine the next edge to be queried. yao's lower bound on the randomized complexity of any monotone nontrivial graph property is improved from &ohgr;(nlog1/12n) to &ohgr;(n5/4), and improved bounds for the complexity of monotone, nontrivial bipartite graph properties are shown.
an interpretation oriented theorem prover over integers a special purpose theorem prover for establishing the validity of expressions over integer variables was developed as part of a program verifier. it is built around a powerful system for manipulating and simplifying integer expressions.
a fully dynamic algorithm for maintaining the transitive closure. this paper presents an efficient fully dynamic graph algorithm for maintaining the transitive closure of a directed graph. the algorithm updates the adjacency matrix of the transitive closure with each update to the graph; hence, each reachability query of the form "is there a directed path from i to j?" can be answered in o(1) time. the algorithm is randomized and has a one-sided error; it is correct when answering yes, but has o(1/nc) probability of error when answering no, for any constant c. in acyclic graphs, worst case update time is o(n2). in general graphs, the update time is o(n2.26). the space complexity of the algorithm is o(n2).
computations with a restricted number of nondeterministic steps (extended abstract) nondeterminism is one of the most elusive concepts in computing. in this paper we direct our efforts towards viewing nondeterminism as an additional resource at the disposal of time or space bounded turing machine computations and study the classes of languages acceptable by these machines with restricted amounts of nondeterminism. one motivation for this study comes from the observation that for many of the well-known np-complete problems, if n' is the length of the input, an algorithm exists requiring a total number of moves which is polynomial in n, but the number of nondeterministic moves is only linear in n.
on the additions necessary to compute certain functions we introduce a theoretical notion, strongly related to algebraic independence, which can be applied to the terms of any computable expression to derive a lower bound on the number of additions and subtractions required to compute that expression.
determining graph properties from matrix representations an open problem, posed by a. rosenberg [r], motivates the consideration of representations of graphs and the effect of these representations on the efficiency of algorithms which determine properties of unlabelled graphs. in this paper we investigate three matrix representations of graphs; the (vertex) adjacency matrix, the edge-adjacency matrix, and the incidence matrix. with the exception of one instance of the edge-adjacency matrix, these structures determine an unlabelled graph up to isomorphism and are, as a result, natural candidates for computer representations of graphs.
on the completeness of a generalized matching problem a perfect matching in a graph h may be viewed as a collection of subgraphs of h, each of which is isomorphic to k2, whose vertex sets partition the vertex set of h. this is naturally generalized by replacing k2 by an arbitrary graph g. we show that if g contains a component with at least three vertices then this generalized matching problem is np-complete. these generalized matchings have numerous applications including the minimization of second-order conflicts in examination scheduling.