waashk/dblp huggingface dataset:
quantum algorithms using the curvelet transform. the curvelet transform is a directional wavelet transform over rn, which is used to analyze functions that have singularities along smooth surfaces (candes and donoho, 2002). i demonstrate how this can lead to new quantum algorithms. i give an efficient implementation of a quantum curvelet transform, together with two applications: a single-shot measurement procedure for approximately finding the center of a ball in rn, given a quantum-sample over the ball; and, a quantum algorithm for finding the center of a radial function over rn, given oracle access to the function. i conjecture that these algorithms succeed with constant probability, using one quantum-sample and o(1) oracle queries, respectively, independent of the dimension n -- this can be interpreted as a quantum speed-up. to support this conjecture, i prove rigorous bounds on the distribution of probability mass for the continuous curvelet transform. this shows that the above algorithms work in an idealized "continuous" model.
a constant-factor approximation for stochastic steiner forest. we consider the stochastic steiner forest problem: suppose we were given a collection of steiner forest instances, and were guaranteed that a random one of these instances would appear tomorrow; moreover, the cost of edges tomorrow will be λ times the cost of edges today. which edges should we buy today so that we can extend it to a solution for the instance arriving tomorrow, to minimize the expected total cost? while very general results have been developed for many problems in stochastic discrete optimization over the past years, the approximation status of the stochastic steiner forest problem has remained open, with previous works yielding constant-factor approximations only for special cases. we resolve the status of this problem by giving a constant-factor primal-dual based approximation algorithm.
how long does it take to catch a wild kangaroo? the discrete logarithm problem asks to solve for the exponent x, given the generator g of a cyclic group g and an element h∈ g such that gx=h. we give the first rigorous proof that pollard's kangaroo method finds the discrete logarithm in expected time (3+o(1))√{b-a} for the worst value of x∈[a,b], and (2+o(1))√b-a when x∈uar[a,b]. this matches the conjectured time complexity and, rare among the analysis of algorithms based on markov chains, even the lead constants 2 and 3 are correct.
hadwiger's conjecture is decidable. the famous hadwiger's conjecture asserts that every graph with no kt-minor is (t-1)-colorable. the case t=5 is known to be equivalent to the four color theorem by wagner, and the case t=6 is settled by robertson, seymour and thomas. so far the cases t ≥ 7 are wide open. in this paper, we prove the following two theorems: there is an o(n2) algorithm to decide whether or not a given graph g satisfies hadwiger's conjecture for the case t. every minimal counterexample to hadwiger's conjecture for the case t has at most f(t) vertices for some explicit bound f(t). the bound f(t) is at most pppt, where p=101010t. our proofs for both results use the well-known result by thomassen [46] for 5-list-coloring planar graphs, together with some results (but not the decomposition theorem) of graph minors in [36]. concerning the first result, we prove the following stronger theorem: for a given graph g and any fixed t, there is an o(n2) algorithm to output one of the following: a (t-1)-coloring of g, or a kt-minor of g, or a minor h of g of order at most f(t) such that h does not have a kt-minor nor is (t-1)-colorable. the last conclusion implies that h is a counterexample to hadwiger's conjecture with at most f(t) vertices for the case t. the time complexity of the algorithm matches the best known algorithms for 4-coloring planar graphs (the four color theorem), due to appel and hakken, and robertson, sanders, seymour and thomas, respectively. let us observe that when t=5, the algorithm gives rise to an algorithm for the four color theorem. the second theorem follows from our structure theorem, which has the following corollary: every minimal counterexample g to hadwiger's conjecture for the case t either has at most f(t) vertices, or has a vertex set z of order at most t-5 such that g-z is planar. it follows from the four color theorem that the second assertion does not happen to any minimal counterexample to hadwiger's conjecture for the case t. thus in constant time, we can decide hadwiger's conjecture for the case t.
multiple intents re-ranking. one of the most fundamental problems in web search is how to re-rank result web pages based on user logs. most traditional models for re-ranking assume each query has a single intent. that is, they assume all users formulating the same query have similar preferences over the result web pages. it is clear that this is not true for a large portion of queries as different users may have different preferences over the result web pages. accordingly, a more accurate model should assume that queries have multiple intents. in this paper, we introduce the multiple intents re-ranking problem. this problem captures scenarios in which some user makes a query, and there is no information about its real search intent. in such cases, one would like to re-rank the search results in a way that minimizes the efforts of all users in finding their relevant web pages. more formally, the setting of this problem consists of various types of users, each of which interested in some subset of the search results. moreover, each user type has a non-negative profile vector. consider some ordering of the search results. this order sets a position for each search result, and induces a position vector of the results relevant to each user type. the overhead of a user type is the dot product of its profile vector and its induced position vector. the goal is to order the search results as to minimize the average overhead of the users. our main result is an o(log r)-approximation algorithm for the problem, where r is the maximum number of search results that are relevant to any user type. the algorithm is based on a new technique, which we call harmonic interpolation. in addition, we consider two important special cases. the first case is when the profile vector of each user type is non-increasing. this case is a generalization of the well-known min-sum set cover problem. we extend the techniques of feige, lovasz and tetali (algorithmica '04), and present an algorithm achieving 4-approximation. the second case is when the profile vector of each user type is non-decreasing. this case generalizes the minimum latency set cover problem, introduced by hassin and levin (esa '05). we devise an lp-based algorithm that attains 2-approximation for it.
on the complexity of differentially private data release: efficient algorithms and hardness results. we consider private data analysis in the setting in which a trusted and trustworthy curator, having obtained a large data set containing private information, releases to the public a "sanitization" of the data set that simultaneously protects the privacy of the individual contributors of data and offers utility to the data analyst. the sanitization may be in the form of an arbitrary data structure, accompanied by a computational procedure for determining approximate answers to queries on the original data set, or it may be a "synthetic data set" consisting of data items drawn from the same universe as items in the original data set; queries are carried out as if the synthetic data set were the actual input. in either case the process is non-interactive; once the sanitization has been released the original data and the curator play no further role. for the task of sanitizing with a synthetic dataset output, we map the boundary between computational feasibility and infeasibility with respect to a variety of utility measures. for the (potentially easier) task of sanitizing with unrestricted output format, we show a tight qualitative and quantitative connection between hardness of sanitizing and the existence of traitor tracing schemes.
fault-tolerant spanners for general graphs. the paper concerns graph spanners that are resistant to vertex or edge failures. given a weighted undirected n-vertex graph g=(v,e) and an integer k ≥ 1, the subgraph h=(v,e'), e'⊆ e, is a spanner of stretch k (or, a k-spanner) of g if δh(u,v) ≤ k· δg(u,v) for every u,v ∈ v, where δg'(u,v) denotes the distance between u and v in g'. graph spanners were extensively studied since their introduction over two decades ago. it is known how to efficiently construct a (2k-1)-spanner of size o(n1+1/k), and this size-stretch tradeoff is conjectured to be tight. the notion of fault tolerant spanners was introduced a decade ago in the geometric setting [levcopoulos et al., stoc'98]. a subgraph h is an f-vertex fault tolerant k-spanner of the graph g if for any set f⊆ v of size at most f and any pair of vertices u,v ∈ v \ f, the distances in h satisfy δh \ f(u,v) ≤ k· δg \ f(u,v). levcopoulos et al. presented an efficient algorithm that given a set s of n points in rd, constructs an f-vertex fault tolerant geometric (1+ε)-spanner for s, that is, a sparse graph h such that for every set f⊆ s of size f and any pair of points u,v ∈ s \ f, δh \ f(u,v) ≤ (1+ε) |uv|, where |uv| is the euclidean distance between u and v. a fault tolerant geometric spanner with optimal maximum degree and total weight was presented in [czumaj &#; zhao, socg'03]. this paper also raised as an open problem the question whether it is possible to obtain a fault tolerant spanner for an arbitrary undirected weighted graph. the current paper answers this question in the affirmative, presenting an f-vertex fault tolerant (2k-1)-spanner of size o(f2 kf+1 · n1+1/klog1-1/kn). interestingly, the stretch of the spanner remains unchanged while the size of the spanner only increases by a factor that depends on the stretch k, on the number of potential faults f, and on logarithmic terms in n. in addition, we consider the simpler setting of f-edge fault tolerant spanners (defined analogously). we present an f-edge fault tolerant 2k-1 spanner with edge set of size o(f· n1+1/k) (only f times larger than standard spanners). for both edge and vertex faults, our results are shown to hold when the given graph g is weighted.
every planar graph is the intersection graph of segments in the plane: extended abstract. given a set s of segments in the plane, the intersection graph of s is the graph with vertex set s in which two vertices are adjacent if and only if the corresponding two segments intersect. we prove a conjecture of scheinerman (phd thesis, princeton university, 1984) that every planar graph is the intersection graph of some segments in the plane.
finding, minimizing, and counting weighted subgraphs. for a pattern graph h on k nodes, we consider the problems of finding and counting the number of (not necessarily induced) copies of h in a given large graph g on n nodes, as well as finding minimum weight copies in both node-weighted and edge-weighted graphs. our results include: the number of copies of an h with an independent set of size s can be computed exactly in o*(2s nk-s+3) time. a minimum weight copy of such an h (with arbitrary real weights on nodes and edges) can be found in o(4s+o(s) nk-s+3) time. (the o* notation omits (k) factors.) these algorithms rely on fast algorithms for computing the permanent of a k x n matrix, over rings and semirings. the number of copies of any h having minimum (or maximum) node-weight (with arbitrary real weights on nodes) can be found in o(nω k/3 + n2k/3+o(1)) time, where ω edge-weighted triangle of weight exactly 0 in general graphs requires ω(n2.5-ε) time for all ε > 0, unless the 3sum problem on n numbers can be solved in o(n2 - ε) time. this suggests that the edge-weighted problem is much harder than its node-weighted version.
public-key cryptosystems from the worst-case shortest vector problem: extended abstract. we construct public-key cryptosystems that are secure assuming theworst-case hardness of approximating the minimum distance on n-dimensional lattices to within small poly(n) factors. prior cryptosystems with worst-case connections were based either on the shortest vector problem for a special class of lattices (ajtai and dwork, stoc 1997; regev, j. acm 2004), or on the conjectured hardness of lattice problems for quantum algorithms (regev, stoc 2005). our main technical innovation is a reduction from variants of the shortest vector problem to corresponding versions of the "learning with errors" (lwe) problem; previously, only a quantum reduction of this kind was known. as an additional contribution, we construct a natural chosen ciphertext-secure cryptosystem having a much simpler description and tighter underlying worst-case approximation factor than prior schemes.
list decoding tensor products and interleaved codes. we design the first efficient algorithms and prove new combinatorial bounds for list decoding tensor products of codes and interleaved codes. (1) we show that for every code, the ratio of its list decoding radius to its minimum distance stays unchanged under the tensor product operation (rather than squaring, as one might expect). this gives the first efficient list decoders and new combinatorial bounds for some natural codes including multivariate polynomials where the degree in each variable is bounded. (2) we show that for every code, its list decoding radius remains unchanged under m-wise interleaving for an integer m. this generalizes a recent result of dinur.et.al, who proved such a result for interleaved hadamard codes (equivalently, linear transformations). (3)using the notion of generalized hamming weights, we give better list size bounds for both tensoring and interleaving of binary linear codes. by analyzing the weight distribution of these codes, we reduce the task of bounding the list size to bounding the number of close-by low-rank codewords. for decoding linear transformations, using rank-reduction together with other ideas, we obtain tight list size bounds for small fields. our results give better bounds on the list decoding radius than what is obtained from the johnson bound, and yield rather general families of codes decodable beyond the johnson bound.
on proximity oblivious testing. we initiate a systematic study of a special type of property testers. these testers consist of repeating a basic test for a number of times that depends on the proximity parameter, whereas the basic test is oblivious of the proximity parameter. we refer to such basic tests by the term proximity-oblivious testers. while proximity-oblivious testers were studied before - most notably in the algebraic setting - the current study seems to be the first one to focus on graph properties. we provide a mix of positive and negative results, and in particular characterizations of the graph properties that have constant-query proximity-oblivious testers in the two standard models (i.e., the adjacency matrix and the bounded-degree models). furthermore, we show that constant-query proximity-oblivious testers do not exist for many easily testable properties, and that even when proximity-oblivious testers exist, repeating them does not necessarily yield the best standard testers for the corresponding property.
private coresets. a coreset of a point set p is a small weighted set of points that captures some geometric properties of $p$. coresets have found use in a vast host of geometric settings. we forge a link between coresets, and differentially private sanitizations that can answer any number of queries without compromising privacy. we define the notion of private coresets, which are simultaneously both coresets and differentially private, and show how they may be constructed. we first show that the existence of a small coreset with low generalized sensitivity (i.e., replacing a single point in the original point set slightly affects the quality of the coreset) implies (in an inefficient manner) the existence of a private coreset for the same queries. this greatly extends the works of blum, ligett, and roth [stoc 2008] and mcsherry and talwar [focs 2007]. we also give an efficient algorithm to compute private coresets for k-median and k-mean queries in red, immediately implying efficient differentially private sanitizations for such queries. following mcsherry and talwar, this construction also gives efficient coalition proof (approximately dominant strategy) mechanisms for location problems. unlike coresets which only have a multiplicative approximation factor, we prove that private coresets must have an additive error. we present a new technique for showing lower bounds on this error.
differential privacy and robust statistics. we show by means of several examples that robust statistical estimators present an excellent starting point for differentially private estimators. our algorithms use a new paradigm for differentially private mechanisms, which we call propose-test-release (ptr), and for which we give a formal definition and general composition theorems.
multiplicative updates outperform generic no-regret learning in congestion games: extended abstract. we study the outcome of natural learning algorithms in atomic congestion games. atomic congestion games have a wide variety of equilibria often with vastly differing social costs. we show that in almost all such games, the well-known multiplicative-weights learning algorithm results in convergence to pure equilibria. our results show that natural learning behavior can avoid bad outcomes predicted by the price of anarchy in atomic congestion games such as the load-balancing game introduced by koutsoupias and papadimitriou, which has super-constant price of anarchy and has correlated equilibria that are exponentially worse than any mixed nash equilibrium. our results identify a set of mixed nash equilibria that we call weakly stable equilibria. our notion of weakly stable is defined game-theoretically, but we show that this property holds whenever a stability criterion from the theory of dynamical systems is satisfied. this allows us to show that in every congestion game, the distribution of play converges to the set of weakly stable equilibria. pure nash equilibria are weakly stable, and we show using techniques from algebraic geometry that the converse is true with probability 1 when congestion costs are selected at random independently on each edge (from any monotonically parametrized distribution). we further extend our results to show that players can use algorithms with different (sufficiently small) learning rates, i.e. they can trade off convergence speed and long term average regret differently.
intrinsic robustness of the price of anarchy. the price of anarchy (poa) is a worst-case measure of the inefficiency of selfish behavior, defined as the ratio of the objective function value of a worst nash equilibrium of a game and that of an optimal outcome. this measure implicitly assumes that players successfully reach some nash equilibrium. this drawback motivates the search for inefficiency bounds that apply more generally to weaker notions of equilibria, such as mixed nash and correlated equilibria; or to sequences of outcomes generated by natural experimentation strategies, such as successive best responses or simultaneous regret-minimization. we prove a general and fundamental connection between the price of anarchy and its seemingly stronger relatives in classes of games with a sum objective. first, we identify a "canonical sufficient condition" for an upper bound of the poa for pure nash equilibria, which we call a smoothness argument. second, we show that every bound derived via a smoothness argument extends automatically, with no quantitative degradation in the bound, to mixed nash equilibria, correlated equilibria, and the average objective function value of regret-minimizing players (or "price of total anarchy"). smoothness arguments also have automatic implications for the inefficiency of approximate and bayesian-nash equilibria and, under mild additional assumptions, for bicriteria bounds and for polynomial-length best-response sequences. we also identify classes of games --- most notably, congestion games with cost functions restricted to an arbitrary fixed set --- that are tight, in the sense that smoothness arguments are guaranteed to produce an optimal worst-case upper bound on the poa, even for the smallest set of interest (pure nash equilibria). byproducts of our proof of this result include the first tight bounds on the poa in congestion games with non-polynomial cost functions, and the first structural characterization of atomic congestion games that are universal worst-case examples for the poa.
3-query locally decodable codes of subexponential length. locally decodable codes (ldc) allow one to decode any particular symbol of the input message by making a constant number of queries to a codeword, even if a constant fraction of the codeword is damaged. in a recent work [yek08] yekhanin constructs a 3-query ldc with sub-exponential length of size exp(exp(o((log n)/(log log n)))). however, this construction requires a conjecture that there are infinitely many mersenne primes. in this paper we give the first unconditional constant query ldc construction with subexponantial codeword length. in addition our construction reduces codeword length. we give construction of 3-query ldc with codeword length exp(exp(o(√{log n log log n ))). our construction could also be extended to higher number of queries. we give a 2r-query ldc with length of exp(exp(o(☂[r] log n (log log n)r-1))).
exact learning of random dnf over the uniform distribution. we show that randomly generated c log(n)-dnf formula can be learned exactly in probabilistic polynomial time using randomly generated examples. our notion of randomly generated is with respect to a uniform distribution. to prove this we extend the concept of well behaved c log(n)-monotone dnf formulae to c log(n)-dnf formulae, and show that almost every dnf formula is well-behaved, and that there exists a probabilistic polynomial time algorithm that exactly learns all well behaved c log(n)-dnf formula. this is the first algorithm that properly learns (non-monotone) dnf with a polynomial number of terms from random examples alone.
reconstruction for the potts model. the reconstruction problem on the tree plays a key role in several important computational problems. deep conjectures in statistical physics link the reconstruction problem to properties of random constraint satisfaction problems including random k-sat and random colourings of random graphs. at this precise threshold the space of solutions is conjectured to undergo a phase transition from a single collected mass to exponentially many small clusters at which point local search algorithm must fail. in computational biology the reconstruction problem is central in phylogenetics. it has been shown [mossel 04] that solvability of the reconstruction problem is equivalent to phylogenetic reconstruction with short sequences for the binary symmetric model. rigorous reconstruction thresholds, however, have only been established in a small number of models. we confirm conjectures made by mezard and montanari for the potts models proving the first exact reconstruction threshold in a non-binary model establishing the so-called kesten-stigum bound for the 3-state potts model on regular trees of large degree. we further establish that the kesten-stigum bound is not tight for the $q$-state potts model when q ≥ 5. moreover, we determine asymptotics for these reconstruction thresholds.