waashk/dblp huggingface dataset:
guessing secrets with inner product questions. suppose we are given some fixed (but unknown) subset x of a set &omega; = f2n, where f2 denotes the field of two elements. we would like to learn as much as possible about the elements x by asking certain binary questions. each "question" q is some element of &omega;, and the "answer" to q is just the inner product q&middot;x (in f2) for some x &epsilon; x. however, the choice of x is made by a truthful (but possibly malevolent) adversary a, whom we may assume is trying to choose answers so as to as yield as little information as possible about x. in this paper, we study various aspects of this problem. in particular, we are interested in extracting as much information as possible about x from a's answers. although a can prevent us from learning the identity of any particular element of x, with appropriate questions we can still learn a lot about x. we determine the maximum amount of information that can be recovered and discuss the optimal strategies for selecting questions. for the case that |x| = 2, we give an o(n3) algorithm for an optimal strategy. however, for the case that |x| &ge; 3, we show that no such polynomial-time algorithm can exist, unless p = np.
on the approximability of some network design problems. consider the following classical network design problem: a set of terminals t &equals; &lcub;ti&rcub; wishes to send traffic to a root r in an n-node graph g &equals; (v, e). each terminal ti sends di units of traffic and enough bandwidth has to be allocated on the edges to permit this. however, bandwidth on an edge e can only be allocated in integral multiples of some base capacity ue and hence provisioning k &times; ue bandwidth on edge e incurs a cost of &lceil;k&rceil; times the cost of that edge. the objective is a minimum-cost feasible solution. this is one of many network design problems widely studied where the bandwidth allocation is governed by side constraints: edges can only allow a subset of cables to be purchased on them or certain quality-of-service requirements may have to be met. in this work, we show that this problem and, in fact, several basic problems in this general network design framework cannot be approximated better than &omega;(log log n) unless np &sube; dtime (no(log log log n)), where &verbar;v&verbar; &equals; n. in particular, we show that this inapproximability threshold holds for (i) the priority-steiner tree problem, (ii) the (single-sink) cost-distance problem, and (iii) the single-sink version of an even more fundamental problem, fixed charge network flow. our results provide a further breakthrough in the understanding of the level of complexity of network design problems. these are the first nonconstant hardness results known for all these problems.
approximating k-median with non-uniform capacities. in this paper we give a constant factor approximation algorithm for the capacitated k-median problem. our algorithm produces a solution where capacities are exceeded by at most a constant factor, while the number of open facilities is at most k. this problem resisted attempts to apply the plethora of methods designed for the uncapacitated case. our algorithm is based on adding some new ingredients to the approach using the primal-dual schema and lagrangian relaxations.previous results on the capacitated k-median problem gave approximations where the number of facilities is exceeded by some constant factor. relaxing the constraint on the number of facilities seems to render k-median problems much simpler. in some applications it is important not to violate the constraint on the number of facilities, whereas relaxing the capacity constraints is a natural thing to do, as the capacities express rough estimates on cluster sizes.
recognizing dart-free perfect graphs. a graph g is called a berge graph if neither g nor its complement contains a chordless cycle whose length is odd and at least five; what we call a dart is the graph with vertices u,v,w,x,y and edges uv,vw,uy,vy,wy,xy; a graph is called dart-free if it has no induced subgraph isomorphic to the dart. we present a polynomial-time algorithm to recognize dart-free berge graphs; this algorithm uses as a subroutine the polynomial-time algorithm for recognizing claw-free berge graphs designed previously by chvátal and sbihi [j. combin. theory ser. b, 44 (1988), pp. 154--176].
on the competitive ratio of evaluating priced functions. let f be a function on a set of variables v. for each x &epsilon; v, let c(x) be the cost of reading the value of x. an algorithm for evaluating f is a strategy for adaptively identifying and reading a set of variables u &sube; v whose values uniquely determine the value of f. we are interested in finding algorithms which minimize the cost incurred to evaluate f in the above sense. competitive analysis is employed to measure the performance of the algorithms. we study two variants of the above problem. first we consider the classical setting in which one assumes that the algorithm knows the cost c(x), for each x &epsilon; v. for the case where f is a monotone boolean function which is representable by a threshold tree, we provide a polynomial time algorithm with the best possible competitive ratio &gamma;fc for each fixed cost function c(&middot;). remarkably, the best known result for the same class of functions is a pseudo-polynomial algorithm with competitiveness 2&gamma;fc. for the class of game tree functions our polynomial time algorithm attains, for each fixed cost function, the same competitiveness as the best known algorithm for the same class of functions, which instead runs in pseudo-polynomial time.in the second part of the paper, we study a novel variant of the problem. here, we assume that the cost function is not known in advance and some preemption is allowed in the reading operations. this model has applications, e.g., when reading a variable coincides with obtaining the output of a job on a cpu and the cost is the cpu time. in such a case, it is reasonable to assume that no exact knowledge of the cost is available. we define a new algorithm for this problem based on the solution of a linear program. we show the optimality of our algorithm for the class of monotone boolean functions representable by and-or-trees. we also show a sub-optimal implementation for general monotone boolean functions.
selective families, superimposed codes, and broadcasting on unknown radio networks. selective families, a weaker variant of superimposed codes [ks64, f92, 197, cr96], have been recently used to design deterministic distributed broadcast (ddb) protocols for unknown radio networks (a radio network is said to be unknown when the nodes know nothing about the network but their own label) [cggpr00, cgor00]. we first provide a general almost tight lower bound on the size of selective families. then, by reverting the selective families - ddb protocols connection, we exploit our lower bound to construct a family of &ldquo;hard&rdquo; radio networks (i.e. directed graphs). these networks yield an &ohgr;(n log d) lower bound on the completion time of ddb protocols that is superlinear (in the size n of the network) even for very small maximum eccentricity d of the network, while all the previous lower bounds (e.g. &ohgr;(d log n) [cggpr00]) are superlinear only when d is almost linear. on the other hand, the previous upper bounds are all superlinear in n independently of the eccentricity d and the maximum in-degree d of the network. we introduce a broadcast technique that exploits selective families in a new way. then, by combining selective families of almost optimal size with our new broadcast technique, we obtain an &ogr;(dd log3 n) upper bound that we prove to be almost optimal when d = &ogr;(n/d). this exponentially improves over the best known upper bound [cgr00) when d, d = &ogr;(polylogn). furthermore, by comparing our deterministic upper bound with the best known randomized one [bgi87] we obtain a new, rather surprising insight into the real gap between deterministic and randomized protocols. it turns out that this gap is exponential (as discovered in [bgi87]), but only when the network has large maximum in-degree (i.e. d = &ohgr;(na), for some constant a > o). we then look at the multibroadcast problem on unknown radio networks. a similar connection to that between selective families and (single) broadcast also holds between superimposed codes and multibroadcast. we in fact combine a variant of our (single) broadcast technique with superimposed codes of almost optimal size available in literature [eff85, hs87, i97, chi99]. this yields a multibroadcast protocol having completion time &ogr;(dd2 log3 n). finally, in order to determine the limits of our multibroadcast technique, we generalize (and improve) the best known lower bound [cr96] on the size of superimposed codes.
on the polynomial time computation of equilibria for certain exchange economies. the problem of computing equilibria for exchange economies has recently started to receive a great deal of attention in the theoretical computer science community. it has been shown that equilibria can be computed in polynomial time in various special cases, the most important of which are when traders have linear, cobb-douglas, or a range of ces utility functions. these important special cases are instances when the market satisfies a property called weak gross substitutability. classical results in economics, which theoretical computer scientists (including us) appear to have been hitherto unaware of, show that the equilibrium prices in such markets are characterized by an infinite number of linear inequalities and therefore form a convex set. in this paper, we show that under fairly general assumptions, there are polynomial-time algorithms to compute equilibria in such markets. to the best of our knowledge, these are the first polynomial-time algorithms for exchange markets under the general setting of weak gross substitutability. to show this result, we need to build on the proofs that characterize the equilibria as a convex set.as a consequence, we obtain alternative polynomial-time algorithms for computing equilibria with linear, cobb-douglas, a range of ces, as well as certain other non-homogeneous utility functions that satisfy weak gross substitutability. unlike previous polynomial-time algorithms, our approach does not make use of the specific form of these utility functions and is in this sense more general. we expect our framework to work or be readily adaptable to handle other exchange markets, provided that the utility functions satisfy weak gross substitutability.
leontief economies encode nonzero sum two-player games. we consider leontief exchange economies, i.e., economies where the consumers desire goods in fixed proportions. unlike bimatrix games, such economies are not guaranteed to have equilibria in general. on the other hand, they include suitable restricted versions which always have equilibria.we give a reduction from two-player games to a special family of leontief exchange economies, which are guaranteed to have equilibria, with the property that the nash equilibria of any game are in one-to-one correspondence with the equilibria of the corresponding economy.our reduction exposes a potential hurdle inherent in solving certain families of market equilibrium problems: finding an equilibrium for leontief economies (where an equilibrium is guaranteed to exist) is at least as hard as finding a nash equilibrium for two-player nonzero sum games.as a corollary of the one-to-one correspondence, we obtain a number of hardness results for questions related to the computation of market equilibria, using results already established for games [17]. in particular, among other results, we show that it is np-hard to say whether a particular family of leontief exchange economies, that is guaranteed to have at least one equilibrium, has more than one equilibrium.perhaps more importantly, we also prove that it is np-hard to decide whether a leontief exchange economy has an equilibrium. this fact should be contrasted against the known ppad-completeness result of [30], which holds when the problem satisfies some standard sufficient conditions that make it equivalent to the computational version of brouwer's fixed point theorem.on the algorithmic side, we present an algorithm for finding an approximate equilibrium for some special leontief economies, which achieves quasi-polynomial time whenever each trader does not demand too much more of any good than some other good.
approximation algorithms for extensible bin packing. in a variation of bin packing called extensible bin packing, the number of bins is specified as part of the input, and bins may be extended to hold more than the usual unit capacity. the cost of a bin is 1 if it is not extended, and the size if it is extended. the goal is to pack a set of items of given sizes into the specified number of bins so as to minimize the total cost. adapting ideas grötschel et al. (1981), grötschel et al. (1988), karmarkar and karp (1982), murgolo (1987), we give a fully polynomial time asymptotic approximation scheme (fptaas) for extensible bin packing. we close with comments on the complexity of obtaining stronger results.
efficient sequences of trials. we introduce a problem called sequential trial optimization, a generalization of the well studied set cover problem with a new objective function. we give a simple algorithm that achieves a constant factor approximation to this problem. sequential trial optimization naturally arises in heterogenous search environments such as peer to peer networks.
reachability and distance queries via 2-hop labels. reachability and distance queries in graphs are fundamental to numerous applications, ranging from geographic navigation systems to internet routing. some of these applications involve huge graphs and yet require fast query answering. we propose a new data structure for representing all distances in a graph. the data structure is distributed in the sense that it may be viewed as assigning labels to the vertices, such that a query involving vertices u and v may be answered using only the labels of u and v.our labels are based on 2-hop covers of the shortest paths, or of all paths, in a graph. for shortest paths, such a cover is a collection s of shortest paths such that, for every two vertices u and v, there is a shortest path from u to v that is a concatenation of two paths from s. we describe an efficient algorithm for finding an almost optimal 2-hop cover of a given collection of paths. our approach is general and can be applied to directed or undirected graphs, exact or approximate shortest paths, or to reachability queries.we study the proposed data structure using a combination of theoretical and experimental means. we implemented our algorithm and checked the size of the resulting data structure on several real-life networks from different application areas. our experiments show that the total size of the labels is typically not much larger than the network itself, and is usually considerably smaller than an explicit representation of the transitive closure of the network.
efficient estimation algorithms for neighborhood variance and other moments. the neighborhood variance problem is as follows. given a (directed or undirected) graph with values associated with each node, compute a data structure that for any given node v and r &ge; 0, would quickly produce an estimate of the variance of all values of nodes that lie within distance r from v. the problem can be generalized to other moment functions and to arbitrary distance-dependent decay.these problems are motivated by applications where the relevance of a measurement observed (or data present) at a certain location decreases with its distance, and thus the aggregate value varies by location. the centralized version of the problem is motivated by applications to query processing on graphical databases. the distributed version of the problem falls in a model we recently introduced for spatially decaying aggregation and is motivated by sensor or p2p networks.we present novel algorithms for the centralized and distributed versions of the problem. our algorithms are nearly optimal, the centralized version requires &otilde;(m) time and the distributed version requires polylogarithmic communication per node or edge (depending on assumptions).
a spectral heuristic for bisecting random graphs. the minimum bisection problem is to partition the vertices of a graph into two classes of equal size so as to minimize the number of crossing edges. the problem is np-hard in the worst case. in this paper we analyze a spectral heuristic for the minimum bisection problem on random graphs gn(p,p'), which are made up as follows. partition n vertices into two classes of equal size randomly, and then insert edges inside the two classes with probability p' and edges crossing the partition with probability p independently. if n(p'-p) &ge; c0&radic;np'in(np') for a certain constant c0 > 0, then with probability 1 - 0(1) as n &larr; &infin; the heuristic finds a minimum bisection of gn(p,p') along with a certificate of optimality in polynomial time. furthermore, we observe that the structure of the set of all minimum bisections of gn(p,p') undergoes a phase transition as n(p' - p) = &theta;(&radic;np' in n). the heuristic solves instances in the subcritical, the critical, and the supercritical phase of the phase transition optimally with probability 1-o(1). these results extend the work of boppana [5].
tight bounds on the complexity of the boyer-moore string matching algorithm. the problem of finding all occurrences of a pattern of length $m$ in a text of length $n$ is considered. it is shown that the boyer--moore string matching algorithm performs roughly $3n$ comparisons and that this bound is tight up to $o(n/m)$; more precisely, an upper bound of $3n - 3(n-m+1)/(m+2)$ comparisons is shown, as is a lower bound of $3n(1-o(1))$ comparisons, as $\frac{n}{m}\rightarrow\infty$ and $m\rightarrow\infty$. while the upper bound is somewhat involved, its main elements provide a simple proof of a $4n$ upper bound for the same algorithm.
bottleneck links, variable demand, and the tragedy of the commons. the price of anarchy, a measure of the inefficiency of selfish behavior, has been successfully analyzed in a diverse array of models over the past five years. the overwhelming majority of this work has studied optimization problems that sought an optimal way to allocate a fixed demand to resources whose performance degrades with increasing congestion. while fundamental, such problems overlook a crucial feature of many applications: the intrinsic coupling of the quality or cost of a resource and the demand for that resource. this coupling motivates allowing demand to vary with congestion, which in turn can lead to "the tragedy of the commons"---severe inefficiency caused by the overconsumption of a shared resource.allowing the demand for resources to vary with their congestion illuminates a second issue with existing studies of the price of anarchy: the standard additive method of aggregating the costs of different resources in a player's strategy is inappropriate for some important applications, including many of those with variable demand. for example, in networking applications a key performance metric is the achievable throughput along a path, which is controlled by its bottleneck (most congested) edge. this disconnect motivates consideration of nonlinear cost aggregation functions, such as the lp norms.in this paper, we initiate the study of the price of anarchy with variable demand and with broad classes of nonlinear aggregation functions. we focus on selfish routing in single- and multicommodity networks, and on the lp norms for 1 &le; p &le; &infin;; our main results are as follows.&bull; for a natural "prize-collecting" objective function, the price of anarchy in multicommodity networks with variable demand is no larger than that in fixed-demand networks. thus the inefficiency arising from the tragedy of the commons is no more severe than that from routing inefficiencies.&bull; using the lp norm with 1 < p < &infin; as a cost aggregation function can dramatically increase the price of anarchy in multicommodity networks (relative to additive aggregation), but causes no such additional inefficiency in single-commodity networks.&bull; using the l&infin; norms as a cost aggregation function can dramatically increase the price of anarchy, even in single-commodity networks. if attention is restricted to equilibria with additional structure, however---structure that is ensured by distributed shortest-path routing protocols---then using the l&infin; norm does not increase the price of anarchy relative to additive aggregation.
approximate string matching: a simpler faster algorithm. we give two algorithms for finding all approximate matches of a pattern in a text, where the edit distance between the pattern and the matching text substring is at most k. the first algorithm, which is quite simple, runs in time $o(\frac{nk^3}{m}+n+m)$ on all patterns except k-break periodic strings (defined later). the second algorithm runs in time $o(\frac{nk^4}{m}+n+m)$ on k-break periodic patterns. the two classes of patterns are easily distinguished in o(m)time.
dynamic lca queries on trees. we show how to maintain a data structure on trees which allows for the following operations, all in worst-case constant time: insertion of leaves and internal nodes, deletion of leaves, deletion of internal nodes with only one child, determining the least common ancestor of any two nodes. we also generalize the dietz--sleator "cup-filling" scheduling methodology, which may be of independent interest.
a faster implementation of the goemans-williamson clustering algorithm. we give an implementation of the goemans-williamson clustering procedure which is at the core of several approximation algorithms including those for generalized steiner trees, prize collecting travelling salesman, 2-edge connected subgraph etc. on a graph with n nodes and m edge, our implementation gives &ogr; (k(n + m) log2 n) time approximation algorithms for all these problems at the expense of a slight additive degradation of 1/nk in the approximation factor, for any constant k.
multidimensional matching and fast search in suffix trees. we show how to construct a suffix tree of a text string t in linear time, after sorting the characters in the text, so that a search for pattern p take time o(p + log t), independent of the alphabet size, thereby matching the asymptotic performance of suffix arrays. using these suffix trees or suffix arrays we then give linear time algorithms for pattern matching in any fixed dimension.
sampling regular graphs and a peer-to-peer network. we consider a simple markov chain for d-regular graphs on n vertices, and show that the mixing time of this markov chain is bounded above by a polynomial in n and d. a related markov chain for d-regular graphs on a varying number of vertices is introduced, for even degree d. we use this to model a certain peer-to-peer network structure. we prove that the related chain has mixing time which is bounded by a polynomial in n, the expected number of vertices, under reasonable assumptions about the arrival and departure process.
the cover time of sparse random graphs. we study the cover time of a random walk on graphs g &isin; gn, p when p = c log n/n, c < 1. we prove that whpthe cover time is asymptotic to c log (c/c--1) n log n.