waashk/dblp huggingface dataset:
reordering buffers for general metric spaces. in the reordering buffer problem, we are given an input sequence of requests for service each of which corresponds to a point in a metric space. the cost of serving the requests heavily depends on the processing order. serving a request induces cost corresponding to the distance between itself and the previously served request, measured in the underlying metric space. a reordering buffer with storage capacity k can be used to reorder the input sequence in a restricted fashion so as to construct an output sequence with lower service cost. this simple and universal framework is useful for many applications in computer science and economics, e.g., disk scheduling, rendering in computer graphics, or painting shops in car plants. in this paper, we design online algorithms for the reordering buffer problem. our main result is a strategy with a polylogarithmic competitive ratio for general metric spaces. previous work on the reordering buffer problem only considered very restricted metric spaces. we obtain our result by first developing a deterministic algorithm for arbitrary weighted trees with a competitive ratio of o(d · log k), where d denotes the unweighted diameter of the tree, i.e., the maximum number of edges on a path connecting two nodes. then we show how to improve this competitive ratio to o(log2 k) for metric spaces that are derived from hsts. combining this result with the results on probabilistically approximating arbitrary metrics by tree metrics, we obtain a randomized strategy for general metric spaces that achieves a competitive ratio of o(log2 k · log n) in expectation against an oblivious adversary. here n denotes the number of distinct points in the metric space. note that the length of the input sequence can be much larger than n.
optimal suffix selection. given a string s[1·s n], the suffix selection problemis to find the kth lexicographically smallest amongst the n suffixes s[i·s n], for i=1,...,n. in particular, the fundamental question is if selection can be performed more efficiently than sorting all the suffixes. if one considered n numbers, they can be sorted using θ(n log n) comparisonsand the classical result from 70's is that selection can be done using o(n) comparisons. thus selection is provably more efficient than sorting, for n numbers. suffix sorting can be done using θ(n log n) comparisons, but does suffix selection need suffix sorting? we settle this fundamental problem by presenting an optimal, deterministic algorithm for suffix selection using o(n) comparisons.
faster integer multiplication. for more than 35 years, the fastest known method for integer multiplication has been the sch&ouml;nhage-strassen algorithm running in time $o(n\log n\log\log n)$. under certain restrictive conditions, there is a corresponding $\omega(n\log n)$ lower bound. all this time, the prevailing conjecture has been that the complexity of an optimal integer multiplication algorithm is $\theta(n\log n)$. we take a major step towards closing the gap between the upper bound and the conjectured lower bound by presenting an algorithm running in time $n\log n\,2^{o(\log^*n)}$. the running time bound holds for multitape turing machines. the same bound is valid for the size of boolean circuits.
verifying and decoding in constant depth. we develop a general approach for improving the efficiency of a computationally bounded receiver interacting with a powerful and possibly malicious sender. the key idea we use is that of delegating some of the receiver's computation to the (potentially malicious) sender. this idea was recently introduced by goldwasser et al. [14] in the area of program checking. a classic example of such a sender-receiver setting is interactive proof systems. by taking the sender to be a (potentially malicious) prover and the receiver to be a verifier, we show that (p-prover) interactive proofs with k rounds of interaction are equivalent to (p-prover) interactive proofs with k+o(1) rounds, where the verifier is in nc0. that is, each round of the verifier's computation can be implemented in constant parallel time. as a corollary, we obtain interactive proof systems, with (optimally) constant soundness, for languages in am and nexp, where the verifier runs in constant parallel-time. another, less immediate sender-receiver setting arises in considering error correcting codes. by taking the sender to be a (potentially corrupted) codeword and the receiver to be a decoder, we obtain explicit families of codes that are locally (list-)decodable by constant-depth circuits of size polylogarithmic in the length of the codeword. using the tight connection between locally list-decodable codes and average-case complexity, we obtain a new, more efficient, worst-case to average-case reduction for languages in exp.
approximation algorithms for budgeted learning problems. we present the first approximation algorithms for a large class of budgeted learning problems. one classicexample of the above is the budgeted multi-armed bandit problem. in this problem each arm of the bandithas an unknown reward distribution on which a prior isspecified as input. the knowledge about the underlying distribution can be refined in the exploration phase by playing the arm and observing the rewards. however, there is a budget on the total number of plays allowed during exploration. after this exploration phase,the arm with the highest (posterior) expected reward is hosen for exploitation. the goal is to design the adaptive exploration phase subject to a budget constraint on the number of plays, in order to maximize the expected reward of the arm chosen for exploitation. while this problem is reasonably well understood in the infinite horizon discounted reward setting, the budgeted version of the problem is np-hard. for this problem and several generalizations, we provide approximate policies that achieve a reward within constant factor of the reward optimal policy. our algorithms use a novel linear program rounding technique based on stochastic packing.
toward a general theory of quantum games. we study properties of quantum strategies, which are complete specifications of a given party's actions in any multiple-round interaction involving the exchange of quantum information with one or more other parties. in particular, we focus on a representation of quantum strategies that generalizes the choi-jamiolkowski representation of quantum , with respect to which each strategy is described by a single operations. this new representation associates with each strategy a positive semidefinite operator acting only on the tensor product of its input and output spaces. various facts about such representations are established, and two applications are discussed: the first is a new and conceptually simple proof of kitaev's lower bound for strong coin-flipping, and the second is a proof of the exact characterization qrg = exp of the class of problems having quantum refereed games.
negative weights make adversaries stronger. the quantum adversary method is one of the most successful techniques for proving lower bounds on quantum query complexity. it gives optimal lower bounds for many problems, has application to classical complexity in formula size lower bounds, and is versatile with equivalent formulations interms of weight schemes, eigen values, and kolmogorov complexity. all these formulations rely on the principlethat if an algorithm successfully computes a function then, in particular, itis able to distinguish between inputs which map to different values. we present a stronger version of the adversary method which goes beyond this principle to make explicit use of the stronger condition that the algorithm actually computes the function. this new method, which we call adv+-, has all the advantages ofthe old: it is a lower bound on bounded-error quantum query complexity, its square is a lower bound on formula size, and it behaves well with respect tofunction composition. moreover adv+- is always at least as large as the adversary method adv, and we show an example of a monotone function forwhich adv+-(f)=omega(adv(f)1.098). we also give examples showing that adv+- does not face limitations of adv like the certificate complexity barrier and the property testing barrier.
playing games with approximation algorithms. in an online linear optimization problem, on each period $t$, an online algorithm chooses $s_t\in\mathcal{s}$ from a fixed (possibly infinite) set $\mathcal{s}$ of feasible decisions. nature (who may be adversarial) chooses a weight vector $w_t\in\mathbb{r}^n$, and the algorithm incurs cost $c(s_t,w_t)$, where $c$ is a fixed cost function that is linear in the weight vector. in the full-information setting, the vector $w_t$ is then revealed to the algorithm, and in the bandit setting, only the cost experienced, $c(s_t,w_t)$, is revealed. the goal of the online algorithm is to perform nearly as well as the best fixed $s\in\mathcal{s}$ in hindsight. many repeated decision-making problems with weights fit naturally into this framework, such as online shortest-path, online traveling salesman problem (tsp), online clustering, and online weighted set cover. previously, it was shown how to convert any efficient exact offline optimization algorithm for such a problem into an efficient online algorithm in both the full-information and the bandit settings, with average cost nearly as good as that of the best fixed $s\in\mathcal{s}$ in hindsight. however, in the case where the offline algorithm is an approximation algorithm with ratio $\alpha >1$, the previous approach worked only for special types of approximation algorithms. we show how to convert any offline approximation algorithm for a linear optimization problem into a corresponding online approximation algorithm, with a polynomial blowup in runtime. if the offline algorithm has an $\alpha$-approximation guarantee, then the expected cost of the online algorithm on any sequence is not much larger than $\alpha$ times that of the best $s\in\mathcal{s}$, where the best is chosen with the benefit of hindsight. our main innovation is combining zinkevich's algorithm for convex optimization with a geometric transformation that can be applied to any approximation algorithm. standard techniques generalize the above result to the bandit setting, except that a &ldquo;barycentric spanner&rdquo; for the problem is also (provably) necessary as input. our algorithm can also be viewed as a method for playing large repeated games, where one can compute only approximate best responses, rather than best responses.
on achieving the "best of both worlds" in secure multiparty computation. two settings are typically considered for secure multipartycomputation, depending on whether or not a majority of the partiesare assumed to be honest. protocols designed under this assumptionprovide "full security" (and, in particular, guarantee outputdelivery and fairness) when this assumption is correct; however, if half or more of the parties are dishonest then security iscompletely compromised. on the other hand, protocols toleratingarbitrarily-many faults do not provide fairness or guaranteed output delivery even if only a single party is dishonest. it isnatural to wonder whether it is possible to achieve the "best ofboth worlds" : namely, a single protocol that simultaneouslyachieves the best possible security in both the above settings. ishai, et al. (crypto 2006) recently addressed this question, andruled out constant-round protocols of this type. as our main result, we completely settle the question by ruling outprotocols using any (expected) polynomial number of rounds. given this stark negative result, we then ask what can be achieved if we are willing to assume simultaneous message transmission (or, equivalently, a non-rushing adversary). in this setting, we show that impossibility still holdsfor logarithmic-round protocols. we also show, for any polynomialp, a protocol (whose round complexity depends on p) that can be simulated to within closeness o(1/p).
how to rank with few errors. we present a polynomial time approximation scheme (ptas) for the minimum feedback arc set problem on tournaments. a simple weighted generalization gives a ptas for kemeny-young rank aggregation.
lower bounds in communication complexity based on factorization norms. we introduce a new method to derive lower bounds on randomized and quantum communication complexity. our method is based on factorization norms, a notion from banach space theory. this approach gives us access to several powerful tools from this area such as normed spaces duality and grothendiek's inequality. this extends the arsenal of methods for deriving lower bounds in communication complexity. as we show, our method subsumes most of the previously known general approaches to lower bounds on communication complexity. moreover, we extend all (but one) of these lower bounds to the realm of quantum communication complexity with entanglement. our results also shed some light on the question how much communication can be saved by using entanglement. it is known that entanglement can save one of every two qubits, and examples for which this is tight are also known. it follows from our results that this bound on the saving in communication is tight almost always. &copy; 2008 wiley periodicals, inc. random struct. alg., 2009
search via quantum walk. we propose a new method for designing quantum search algorithms forfinding a "marked" element in the state space of a classical markovchain. the algorithm is based on a quantum walk à la szegedy [25] that is defined in terms of the markov chain. the main new idea is to apply quantum phase estimation to the quantumwalk in order to implement an approximate reflection operator. thisoperatoris then used in an amplitude amplification scheme. as a result weconsiderably expand the scope of the previous approaches ofambainis [6] and szegedy [25]. our algorithm combines the benefits of these approaches in terms of beingable to find marked elements, incurring the smaller cost of the two,and being applicable to a larger class of markov chain. in addition,it is conceptually simple, avoids several technical difficulties in the previous analyses, and leads to improvements in various aspects of several algorithms based on quantum walk.
linear probing with constant independence. hashing with linear probing dates back to the 1950s and is among the most widely studied algorithms. in recent years, it has become one of the most important hash table organizations because it uses the cache of modern computers very well. unfortunately, previous analyses relied either on complicated and space-consuming hash functions, or on the unrealistic assumption of free access to a hash function with random and independent function values. carter and wegman, in their seminal paper on universal hashing, have already raised the question of extending their analysis to linear probing. however, we show in this paper that linear probing using a pairwise independent family may have expected logarithmic cost per operation. on the positive side, we show that 5-wise independence is enough to ensure constant expected time per operation. this resolves the question of finding a space- and time-efficient hash function that provably ensures good performance for linear probing.
an efficient parallel repetition theorem for arthur-merlin games. we show a parallel-repetition theorem for constant-round arthur-merlin games, using an efficient reduction. as a consequence, we show that parallel repetition reduces the soundness-error at an optimal rate (up to a negligible factor) in constant-round public-coin argument systems, and constant-round public-coinproofs of knowledge. the former of these results resolves an open questionposed by bellare, impagliazzo and naor (focs '97).
property testing in hypergraphs and the removal lemma. property testers are efficient, randomized algorithms which recognize if an input graph (or other combinatorial structure) satisfies a given property or if it is "far" from exhibiting it.generalizing several earlier results, alon and shapira showed thathereditary graph properties are testable (with one-sided error). in this paper we prove the analogous result for hypergraphs.this result is an immediate consequence of a (hyper)graph theoretic statement, which is an extension of the so-called removal lemma. the proof of this generalization relies on the regularity method for hypergraphs.
low-degree tests at large distances. we define tests of boolean functions which distinguish between linear (or quadratic) polynomials, and functions which are very far, in an appropriate sense, from these polynomials. the tests have optimal or nearly optimal trade-offs between soundness and the number of queries. a central step in our analysis of quadraticity tests is the proof of aninverse theorem for the third gowers uniformity norm of boolean functions. the last result implies that it ispossible to estimate efficiently the distance from the second-order reed-muller code on inputs lying far beyond its list-decoding radius. our main technical tools are fourier analysis on z2n and methods from additive number theory. we observe that these methods can be used to give a tight analysis of the abelian homomorphism testing problemfor some families of groups, including powers of zp.
tight integrality gaps for lovasz-schrijver lp relaxations of vertex cover and max cut. we study linear programming relaxations of vertex cover and max cutarising from repeated applications of the "lift-and-project" method of lovasz and schrijver starting from the standard linear programming relaxation. for vertex cover, arora, bollobas, lovasz and tourlakis prove thatthe integrality gap remains at least 2-ε after ωε(log n) rounds, where n is the number ofvertices, and tourlakis proves that integrality gap remains at least 1.5-ε after ω((log n)2) rounds. fernandez de lavega and kenyon prove that the integrality gap of max cut is at most 12 + ε after any constant number of rounds. (theirresult also applies to the more powerful sherali-adams method. we prove that the integrality gap of vertex cover remains at least 2-ε after ωε (n) rounds, and that theintegrality gap of max cut remains at most 1/2 +ε after ωε(n) rounds.
low-end uniform hardness vs. randomness tradeoffs for am. impagliazzo and wigderson [proceedings of the 39th annual ieee symposium on foundations of computer science, ieee computer society, washington, dc, 1998, pp. 734-743] proved a hardness versus randomness tradeoff for bpp in the uniform setting, which was subsequently extended to give optimal tradeoffs for the full range of possible hardness assumptions (in slightly weaker settings). gutfreund, shaltiel, and ta-shma [comput. complexity, 12 (2003), pp. 85-130] proved a uniform hardness versus randomness tradeoff for am, but that result worked only on the &ldquo;high end&rdquo; of possible hardness assumptions. in this work, we give uniform hardness versus randomness tradeoffs for am that are near-optimal for the full range of possible hardness assumptions. following gutfreund, shaltiel, and ta-shma, we do this by constructing a hitting-set-generator (hsg) for am with &ldquo;resilient reconstruction.&rdquo; our construction is a recursive variant of the miltersen-vinodchandran hsg [comput. complexity, 14 (2005), pp. 256-279], the only known hsg construction with this required property. the main new idea is to have the reconstruction procedure operate implicitly and locally on superpolynomially large objects, using tools from pcps (low-degree testing, self-correction) together with a novel use of extractors that are built from reed-muller codes for a sort of locally computable error-reduction. as a consequence we obtain gap theorems for am (and am $\cap$ coam) that state, roughly, that either am (or am $\cap$ coam) protocols running in time $t(n)$ can simulate all of exp (&ldquo;arthur-merlin games are powerful&rdquo;) or else all of am (or am $\cap$ coam) can be simulated in nondeterministic time $s(n)$ (&ldquo;arthur-merlin games can be derandomized&rdquo;) for a near-optimal relationship between $t(n)$ and $s(n)$. as in gutfreund, shatiel, and ta-shma, the case of am $\cap$ coam yields a particularly clean theorem that is of special interest due to the wide array of cryptographic and other problems that lie in this class.
separating ac from depth-2 majority circuits. we prove that ac0 cannot be efficiently simulated by majºmaj circuits. namely, we construct an ac0 circuit of depth 3 that requires majºmaj circuits of size 2ω(n1/5). this matches allender's classic result that ac0 can be simulated by majºmajºmaj circuits of quasipolynomial size. our proof is based on communication complexity. to obtain the above result, we develop a novel technique for communication lower bounds, the degree/discrepancy theorem. this technique is a separate contribution of our paper. it translates lower bounds on the threshold degree of a boolean function into upper bounds on the discrepancy of a related function. upper bounds on the discrepancy, in turn, immediately imply communication lower bounds as well as lower bounds against threshold circuits. as part of our proof, we use the degree/discrepancy theorem to obtain an explicit ac0 circuit of depth 3 that has discrepancy 2-ω(n1/5), under an explicit distribution. this yields the first known ac0 function with exponentially small discrepancy. finally, we apply our work to learning theory, showing that polynomial-size dnf and cnf formulas have margin complexity 2ω(n1/5).
interpolation of depth-3 arithmetic circuits with two multiplication gates. in this paper we consider the problem of constructing a small arithmetic circuit for a polynomial for which we have oracle access. our focus is on $n$-variate polynomials, over a finite field $\mathbb{f}$, that have depth-3 arithmetic circuits (with an addition gate at the top) with two multiplication gates of degree at most $d$. we obtain the following results: 1. multilinear case. when the circuit is multilinear (multiplication gates compute multilinear polynomials) we give an algorithm that outputs, with probability $1-o(1)$, all the depth-3 circuits with two multiplication gates computing the polynomial. the running time of the algorithm is $\operatorname{poly}(n,|\mathbb{f}|)$. 2. general case. when the circuit is not multilinear we give a quasi-polynomial (in $n,d,|\mathbb{f}|$) time algorithm that outputs, with probability $1-o(1)$, a succinct representation of the polynomial. in particular, if the depth-3 circuit for the polynomial is not of small depth-3 rank (namely, after removing the g.c.d. (greatest common divisor) of the two multiplication gates, the remaining linear functions span a not too small linear space), then we output the depth-3 circuit itself. in the case that the rank is small we output a depth-3 circuit with a quasi-polynomial number of multiplication gates. $\diamond$ prior to our work there have been several interpolation algorithms for restricted models. however, all the techniques used there completely fail when dealing with depth-3 circuits with even just two multiplication gates. our proof technique is new and relies on the factorization algorithm for multivariate black-box polynomials, on lower bounds on the length of linear locally decodable codes with two queries, and on a theorem regarding the structure of identically zero depth-3 circuits with four multiplication gates.