waashk/dblp huggingface dataset:
multi-armed bandits in metric spaces. in a multi-armed bandit problem, an online algorithm chooses from a set of strategies in a sequence of $n$ trials so as to maximize the total payoff of the chosen strategies. while the performance of bandit algorithms with a small finite strategy set is quite well understood, bandit problems with large strategy sets are still a topic of very active investigation, motivated by practical applications such as online auctions and web advertisement. the goal of such research is to identify broad and natural classes of strategy sets and payoff functions which enable the design of efficient solutions. in this work we study a very general setting for the multi-armed bandit problem in which the strategies form a metric space, and the payoff function satisfies a lipschitz condition with respect to the metric. we refer to this problem as the "lipschitz mab problem". we present a complete solution for the multi-armed problem in this setting. that is, for every metric space (l,x) we define an isometry invariant max min cov(x) which bounds from below the performance of lipschitz mab algorithms for $x$, and we present an algorithm which comes arbitrarily close to meeting this bound. furthermore, our technique gives even better results for benign payoff functions.
terminal backup, 3d matching, and covering cubic graphs. we define a problem called simplex matching, and show that it is solvable in polynomial time. while simplex matching is interesting in its own right as a nontrivial extension of non-bipartite min-cost matching, its main value lies in many(seemingly very different) problems that can be solved using ouralgorithm. for example, suppose that we are given a graph with terminal nodes, non-terminal nodes, and edge costs. then, the terminal backup problem, which consists of finding the cheapest forest connecting every terminal to at least one other terminal, is reducible to simplex matching. simplex matching is also useful for various tasks that involve forming groups of at least two members, such as project assignment and variants of facility location. in an instance of simplex matching, we are given a hypergraphh with edge costs, and edge size at most 3. we show how to find the min-cost perfect matching of h efficiently, if the edge costs obey a simple and realistic inequality that we call the simplexcondition. the algorithm we provide is relatively simple to understand and implement, but difficult to prove correct. in the process of this proof we show some powerful new results about covering cubic graphs with simple combinatorial objects.
a learning theory approach to non-interactive database privacy. we demonstrate that, ignoring computational constraints, it is possible to release privacy-preserving databases that are useful for all queries over a discretized domain from any given concept class with polynomial vc-dimension. we show a new lower bound for releasing databases that are useful for halfspace queries over a continuous domain. despite this, we give a privacy-preserving polynomial time algorithm that releases information useful for all halfspace queries, for a slightly relaxed definition of usefulness. inspired by learning theory, we introduce a new notion of data privacy, which we call distributional privacy, and show that it is strictly stronger than the prevailing privacy notion, differential privacy.
a combinatorial, primal-dual approach to semidefinite programs. semidefinite programs (sdp) have been used in many recentapproximation algorithms. we develop a general primal-dualapproach to solve sdps using a generalization ofthe well-known multiplicative weights update rule to symmetricmatrices. for a number of problems, such as sparsest cut and balanced separator in undirected and directed weighted graphs, and the min uncut problem, this yields combinatorial approximationalgorithms that are significantly more efficient than interiorpoint methods. the design of our primal-dual algorithms is guidedby a robust analysis of rounding algorithms used to obtain integersolutions from fractional ones.
tight rmr lower bounds for mutual exclusion and other problems. we investigate the remote memory references (rmrs) complexity of deterministic processes that communicate by reading and writing shared memory in asynchronous cache-coherent and distributed shared-memory multiprocessors. we define a class of algorithms that we call order encoding. by applying information-theoretic arguments, we prove that every order encoding algorithm, shared by n processes, has an execution that incurs ω(n log n) rmrs. from this we derive the same lower bound for the mutual exclusion, bounded counter and store/collect synchronization problems. the bounds we obtain for these problems are tight. it follows from the results of [10] that our lower bounds hold also for algorithms that can use comparison primitives and load-linked/store-conditional in addition to reads and writes. our mutual exclusion lower bound proves a longstanding conjecture of anderson and kim.
balanced max 2-sat might not be the hardest. we show that, assuming the unique games conjecture, it is np-hard to approximate max2sat within αllz-+ε, where 0.9401 < αllz- < 0.9402 is the believed approximation ratio of the algorithm of lewin, livnat and zwick [28]. this result is surprising considering the fact that balanced instances of max2sat, i.e., instances where each variable occurs positively and negatively equally often, can be approximated within 0.9439. in particular, instances in which roughly 68% of the literals are unnegated variables and 32% are negated appear less amenable to approximation than instances where the ratio is 50% - 50%.
a quadratic lower bound for the permanent and determinant problem over any characteristic != 2. in valiant's theory of arithmetic complexity, the classes vp and vnp are analogs of p and np. a fundamental problem concerning these classes is the permanent and determinant problem: given a field f of characteristic ≠2, and an integer n, what is the minimum m such that the permanent of an n x n matrix x=(xij) can be expressed as a determinant of an m x m matrix, where the entries of the determinant matrix are affine linear functions of xij's, and the equality is in f [x]. mignon and ressayre (2004) [11] proved a quadratic lower bound m=ω(n2) for fields of characteristic 0. we extend the mignon-ressayre quadratic lower bound to all fields of characteristic ≠2.
lower bounds for randomized read/write stream algorithms. motivated by the capabilities of modern storage architectures, we consider the following generalization of the data stream model where the algorithm has sequential access to multiple streams. unlike the data stream model, where the stream is read only, in this new model (introduced in [8,9]) the algorithms can also write onto streams. there is no limit on the size of the streams but the number of passes made on the streams is restricted. on the other hand, the amount of internal memory used by the algorithm is scarce, similar to data stream model. we resolve the main open problem in [7] of proving lower bounds in this model for algorithms that are allowed to have 2-sided error. previously, such lower bounds were shown only for deterministic and 1-sided error randomized algorithms [9,7]. we consider the classical set disjointness problemthat has proved to be invaluable for deriving lower bounds for many other problems involving data streams and other randomized models of computation. for this problem, we show a near-linear lower bound on the size of the internal memory used by a randomized algorithm with 2-sided error that is allowed to have o(log n/log log n) passes over the streams. this bound is almost optimal sincethere is a simple algorithm that can solve this problem using logarithmic memory if the number of passes over the streams. applications include near-linear lower bounds onthe internal memory for well-known problems in the literature:(1) approximately counting the number of distinct elements in the input (f0);(2) approximating the frequency of the mod of an input sequence(f*∞);(3) computing the join of two relations; and (4) deciding if some node of an xml document matches an xquery (or xpath) query. our techniques involve a novel direct-sum type of argument that yields lower bounds for many other problems. our results asymptotically improve previously known bounds for any problem even in deterministic and 1-sided error models of computation.
optimal hierarchical decompositions for congestion minimization in networks. hierarchical graph decompositions play an important role in the design of approximation and online algorithms for graph problems. this is mainly due to the fact that the results concerning the approximation of metric spaces by tree metrics (e.g. [10,11,14,16]) depend on hierarchical graph decompositions. in this line of work a probability distribution over tree graphs is constructed from a given input graph, in such a way that the tree distances closely resemble the distances in the original graph. this allows it, to solve many problems with a distance-based cost function on trees, and then transfer the tree solution to general undirected graphs with only a logarithmic loss in the performance guarantee. the results about oblivious routing [30,22] in general undirected graphs are based on hierarchical decompositions of a different type in the sense that they are aiming to approximate the bottlenecks in the network (instead of the point-to-point distances). we call such decompositions cut-based decompositions. it has been shown that they also can be used to design approximation and online algorithms for a wide variety of different problems, but at the current state of the art the performance guarantee goes down by an o(log2n log log n)-factor when making the transition from tree networks to general graphs. in this paper we show how to construct cut-based decompositions that only result in a logarithmic loss in performance, which is asymptotically optimal. remarkably, one major ingredient of our proof is a distance-based decomposition scheme due to fakcharoenphol, rao and talwar [16]. this shows an interesting relationship between these seemingly different decomposition techniques. the main applications of the new decomposition are an optimal o(log n)-competitive algorithm for oblivious routing in general undirected graphs, and an o(log n)-approximation for minimum bisection, which improves the o(log1.5n) approximation by feige and krauthgamer [17].
read-once polynomial identity testing. in this paper we study the problems of polynomial identity testing (pit) and reconstruction of read-once formulas. the following are some deterministic algorithms that we obtain. an no(k2) algorithm for checking whether given k rofs sum to zero or not. an no(d+k2) time algorithm for checking whether a black box holding the sum of k depth d rofs computes the zero polynomial. in other words, we provide a hitting set of size no(d+k2) for the sum of k depth d rofs. this implies an no(d) deterministic algorithm for the reconstruction of depth d rofs. a hitting set of size exp(~o(√n+k2)) for the sum of k rofs (without depth restrictions). this implies a sub-exponential time deterministic algorithm for black-box identity testing and reconstructing of rofs. to the best of our knowledge our results give the first polynomial time (non black-box) and sub-exponential time (black-box) identity testing algorithms for the sum of (a constant number of) rofs. in addition, we introduce and study the read-once testing problem (rot for short): given an arithmetic circuit computing a polynomial p(x), decide whether there is a rof computing p(x). if there is such a formula then output it. otherwise output "no". we show that most previous algorithms for polynomial identity testing can be strengthen to yield algorithms for the rot problem. in particular we give rot algorithms for: depth-2 circuits (circuits computing sparse polynomials), depth-3 circuits with bounded top fan-in (both in the black-box and non black-box settings, where the running time depends on the model), non-commutative formulas and sum of k rofs. the running time of the rot algorithm is essentially the same running time as the corresponding pit algorithm for the class. the main tool in most of our results is a new connection between polynomial identity testing and reconstruction of read-once formulas. namely, we show that in any model that is closed under partial derivatives (that is, a partial derivative of a polynomial computed by a circuit in the model, can also be computed by a circuit in the model) and that has an efficient deterministic polynomial identity testing algorithm, we can also answer the read-once testing problem.
constructing non-computable julia sets. while most polynomial julia sets are computable, it has been recently shown [12] that there exist non-computable julia sets. the proof was non-constructive, and indeed there were doubts as to whether specific examples of parameters with non-computable julia sets could be constructed. it was also unknown whether the non-computability proof can be extended to the filled julia sets. in this paper we give an answer to both of these questions, which were the main open problems concerning the computability of polynomial julia sets. we show how to construct a specific polynomial with a non-computable julia set. in fact, in the case of julia sets of quadratic polynomials we give a precise characterization of juliasets with computable parameters. moreover, assuming a widely believed conjecture in complex dynamics, we give a poly-time algorithm forcomputing a number c such that the julia set jz2+c z is non-computable. in contrast with these results, we show that the filled julia set of a polynomial is always computable.
the complexity of temporal constraint satisfaction problems. a temporal constraint language is a set of relations that has a first-order definition in (b q,
holographic algorithms: from art to science. we develop the theory of holographic algorithms. we definea basis manifold and give characterizations of algebraic varieties of realizable symmetric generators and recognizers on this manifold. we present a polynomial time decision algorithm for the simultaneous realizability problem. using the general machinery we are able to giveunexpected holographic algorithms for some counting problems, modulo certain mersenne type integers. these counting problems are p-complete without the moduli. going beyond symmetric signatures, we define d-admissibility and d-realizability for general signatures, and give a characterizationof 2-admissibility.
randomized k-server on hierarchical binary trees. we design a randomized online algorithm for k-server on binary trees with hierarchical edge lengths, with expected competitive ratio o(log delta), where delta is the diameter of the metric. this is one of the first k-server algorithms with competitive ratio poly-logarithmic in the natural problem parameters, and represents substantial progress on the randomized k-server conjecture. extending the algorithm to trees of higher degree would give a competitive ratio of o(log2 delta log n) for the k-server problem on general metrics with n points and diameter delta.
a fixed-parameter algorithm for the directed feedback vertex set problem. the (parameterized) feedback vertex set problem on directed graphs, which we refer to as the dfvs problem, is defined as follows: given a directed graph g and a parameter k, either construct a feedback vertex set of at most k vertices in g or report that no such set exists. whether or not the dfvs problem is fixed-parameter tractable has been a well-known open problem in parameterized computation and complexity, i.e., whether the problem can be solved in time f(k)no(1) for some function f. in this paper we develop new algorithmic techniques that result in an algorithm with running time 4k k! no(1) for the dfvs problem, thus showing that this problem is fixed-parameter tractable.
polynomial flow-cut gaps and hardness of directed cut problems. we study the multicut and the sparsest cut problems in directed graphs. in the multicut problem, we are a given an n-vertex graph g along with k source-sink pairs, and the goal is to find the minimum cardinality subset of edges whose removal separates all source-sink pairs. the sparsest cut problem has the same input, but the goal is to find a subset of edges to delete so as to minimize the ratio of the number of deleted edges to the number of source-sink pairs that are separated by this deletion. the natural linear programming relaxation for multicut corresponds, by lp-duality, to the well-studied maximum (fractional) multicommodity flow problem, while the standard lp-relaxation for sparsest cut corresponds to maximum concurrent flow. therefore, the integrality gap of the linear programming relaxation for multicut/sparsest cut is also the flow-cut gap: the largest gap, achievable for any graph, between the maximum flow value and the minimum cost solution for the corresponding cut problem. our first result is that the flow-cut gap between maximum multicommodity flow and minimum multicut is &omega;&tilde;(n1/7) in directed graphs. we show a similar result for the gap between maximum concurrent flow and sparsest cut in directed graphs. these results improve upon a long-standing lower bound of &omega;(log n) for both types of flow-cut gaps. we notice that these polynomially large flow-cut gaps are in a sharp contrast to the undirected setting where both these flow-cut gaps are known to be &theta;(log n). our second result is that both directed multicut and sparsest cut are hard to approximate to within a factor of 2&omega;(log1&minus;&epsis; n) for any constant &epsis; > 0, unless np &sube; zpp. this improves upon the recent &omega;(log n/log log n)-hardness result for these problems. we also show that existence of pcp's for np with perfect completeness, polynomially small soundness, and constant number of queries would imply a polynomial factor hardness of approximation for both these problems. all our results hold for directed acyclic graphs.
stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads. we study the stability of the max-weight protocol for combined routingand scheduling in communication networks. previous work has shownthat this protocol is stable for adversarial multicommodity trafficin subcritically loaded static networks and for single-commoditytraffic in critically loaded dynamic networks. we show: the max-weight protocol is stable for adversarial multicommodity traffic in adversarial dynamic networks whenever the network is subcriticallyloaded. the max-weight protocol is stable for fixed multicommodity trafficin fixed networks even if the network is critically loaded. the latter result has implications for the running time of themax-weight protocol when it is used to solve multicommodity flowproblems. in particular, for a fixed problem instance we show thatif the value of the optimum solution is known, the max-weight protocolfinds a flow that is within a (1-ε)-factor of optimal in time o(1/ε) (improving the previous bound of o(1/ε2)). if thevalue of the optimum solution is not known, we show how to apply themax-weight algorithm in a binary search procedure that runs in o(1/ε) time.
random projection trees and low dimensional manifolds. we present a simple variant of the k-d tree which automatically adapts to intrinsic low dimensional structure in data without having to explicitly learn this structure.
minimum k-way cuts via deterministic greedy tree packing. we present a simple and fast deterministic algorithm for the minimum k-way cut problem in a capacitated graph, that is, finding a set of edges with minimum total capacity whose removal splits the graph into at least k components. the algorithm packs o(mk3 log n) trees. each new tree is a minimal spanning tree with respect to the edge utilizations, and the utilization of an edge is the number of times it has been used in previous spanning trees divided by its capacity. we prove that each minimum k-way cut is crossed at most 2k-2 times by one of the trees. we can enumerate all such cuts in ~o(n2k) time, which is hence the running time of our algorithm producing all minimum k-way cuts. the previous fastest deterministic algorithm of kamidoi et al. [sicomp'06] took o(n(4+o(1))k) time, so this is a near-quadratic improvement. moreover, we essentially match the o(n(2-o(1))k) running time of the monto carlo (no correctness guarantee) randomized algorithm of karger and stein [jacm'96].
classical interaction cannot replace a quantum message. we demonstrate a two-player communication problem that can be solved in the one-way quantum model by a 0-error protocol of cost o(log n) but requires exponentially more communication in the classical interactive (bounded error) model.
iteratively constructing preconditioners via the conjugate gradient method. we consider the problem of solving a symmetric, positive definite system of linear equations.the most well-known and widely-used method for solving such systemsis the preconditioned conjugate gradient method.the performance of this method depends crucially on knowing a good preconditioner matrix.we show that the conjugate gradient method itself canproduce good preconditioners as a by-product. these preconditioners allow us to derive new asymptotic bounds on the timeto solve multiple related linear systems.
the price of privacy and the limits of lp decoding. this work is at theintersection of two lines of research. one line, initiated by dinurand nissim, investigates the price, in accuracy, of protecting privacy in a statistical database. the second, growing from an extensive literature on compressed sensing (see in particular the work of donoho and collaborators [4,7,13,11])and explicitly connected to error-correcting codes by candès and tao ([4]; see also [5,3]), is in the use of linearprogramming for error correction. our principal result is the discovery of a sharp threshhold ρ*∠ 0.239, so that if ρ < ρ* and a is a random m x n encoding matrix of independently chosen standardgaussians, where m = o(n), then with overwhelming probability overchoice of a, for all x ∈ rn, lp decoding corrects ⌊ ρ m⌋ arbitrary errors in the encoding ax, while decoding can be made to fail if the error rate exceeds ρ*. our boundresolves an open question of candès, rudelson, tao, and vershyin [3] and (oddly, but explicably) refutesempirical conclusions of donoho [11] and candès et al [3]. by scaling and rounding we can easilytransform these results to obtain polynomial-time decodable random linear codes with polynomial-sized alphabets tolerating any ρ < ρ* ∠ 0.239 fraction of arbitrary errors. in the context of privacy-preserving datamining our results say thatany privacy mechanism, interactive or non-interactive, providingreasonably accurate answers to a 0.761 fraction of randomly generated weighted subset sum queries, and arbitrary answers on the remaining 0.239 fraction, is blatantly non-private.