waashk/dblp huggingface dataset:
space-time tradeoff for answering range queries (extended abstract) in this paper, we raise and investigate the question of (storage) space- (retrieval) time tradeoff for a static database, in the general framework of fredman's. as will be seen, such tradeoff results also lead to lower bounds on the complexity of processing a sequence of m insert and query instructions. the latter results are incomparable to fredman's, since the presence of delete instructions was crucial for his proof technique. we will present our results in detail in the next few sections. here we will only mention three main conclusions. firstly, circular query is shown to be intrinsically hard in the sense that, for some static database with n records, there is a space-time tradeoff ts -&-gt; n1 + -&-egr; where -&-egr;-&-gt;0; in contrast, orthogonal query can always be implemented with space s-&-equil;0(n(log n)k) and time t-&-equil;0((log n)k) for fixed k. furthermore, any algorithm for processing 0(n) insert and query instructions must use time -&-ohgr;(n1+-&-egr;) in the worst case. secondly, for the -&-ldquo;interval-&-rdquo; query, we have determined the space-time tradeoff quite precisely to be t @@@@ -&-agr;(s,n), where -&-agr; is the inverse to an ackermann's function first defined by tarjan [9]. this is a rare case where the function -&-agr; arises outside the context of path compression, and is obtained through a totally independent derivation. thirdly, we prove that, for the interval query, any algorithm to process a sequence of 0(n) insert and query must take time -&-ohgr;((n log n)/(log log n)) in the worst case. this means that one cannot hope to maintain the most efficient static data structure (with retrieval time -&-agr;(s,n)) in the dynamic case.
limitations of vcg-based mechanisms. we consider computationally-efficient incentive-compatiblemechanisms that use the vcg payment scheme, and study how well theycan approximate the social welfare in auction settings. we present anovel technique for setting lower bounds on the approximation ratioof this type of mechanisms. specifically, for combinatorial auctionsamong submodular (and thus also subadditive) bidders we prove an ω(m1/6) lower bound, which is close to the knownupper bound of o(m1/2), and qualitatively higher than theconstant factor approximation possible from a purely computationalpoint of view.
one sketch for all: fast algorithms for compressed sensing. compressed sensing is a new paradigm for acquiring the compressible signals that arise in many applications. these signals can be approximated using an amount of information much smaller than the nominal dimension of the signal. traditional approaches acquire the entire signal and process it to extract the information. the new approach acquires a small number of nonadaptive linear measurements of the signal and uses sophisticated algorithms to determine its information content. emerging technologies can compute these general linear measurements of a signal at unit cost per measurement. this paper exhibits a randomized measurement ensemble and a signal reconstruction algorithm that satisfy four requirements: 1. the measurement ensemble succeeds for all signals, with high probability over the random choices in its construction. 2. the number of measurements of the signal is optimal, except for a factor polylogarithmic in the signal length. 3. the running time of the algorithm is polynomial in the amount of information in the signal and polylogarithmic in the signal length. 4. the recovery algorithm offers the strongest possible type of error guarantee. moreover, it is a fully polynomial approximation scheme with respect to this type of error bound. emerging applications demand this level of performance. yet no otheralgorithm in the literature simultaneously achieves all four of these desiderata.
circuits and local computation this paper contains two parts. in part i, we show that polynomial-size monotone threshold circuits of depth k form a proper hierarchy in parameter k. this implies in particular that monotone tc0 is properly contained in nc1. in part ii, we introduce a new concept, called local function, which tries to characterize when a function can be efficiently computed using only localized processing elements. it serves as a unifying framework for viewing related and sometimes apparently unrelated results. in particular, it will be demonstrated that the recent results on lower bounds for monotone circuits by razborov [ra1] and karchmer and wigderson [kw], as well as a main theorem in part i of this paper, can be regarded as proving certain functions to be nonlocal. we will also suggest an approach based on locality for attacking the conjecture that (nonmonotone) tc0 is properly contained in nc1.
approximating minimum bounded degree spanning trees to within one of optimal. in the minimum bounded degree spanning tree problem, we aregiven an undirected graph with a degree upper bound bv on eachvertex v, and the task is to find a spanning tree of minimumcost which satisfies all the degree bounds. let opt be the costof an optimal solution to this problem. in this paper, we presenta polynomial time algorithm which returns a spanning tree t ofcost at most opt and dt(v) ≤ bv+1 for all v, where dt(v) denotes the degree of v in t. this generalizes aresult of furer and raghavachari [8] to weighted graphs, andsettles a 15-year-old conjecture of goemans [10] affirmatively. the algorithm generalizes when each vertex v hasa degree lower bound av and a degree upper bound bv, andreturns a spanning tree with cost at most opt and av - 1 ≤dt(v) ≤ bv + 1 for all v. this is essentially the bestpossible. the main technique used is an extension of the iterativerounding method introduced by jain [12] for the design ofapproximation algorithms.
parallel repetition: simplifications and the no-signaling case. consider a game where a refereed chooses (x,y) according to a publiclyknown distribution pxy, sends x to alice, and y to bob. withoutcommunicating with each other, alice responds with a value "a" and bobresponds with a value "b". alice and bob jointly win if a publiclyknown predicate q(x,y,a,b) holds. let such a game be given and assume that the maximum probabilitythat alice and bob can win is v<1. raz (siam j. comput. 27, 1998)shows that if the game is repeated n times in parallel, then the probability that alice and bob win all games simultaneously is at most v'(n/log(s)), where s is the maximal number of possible responses from alice and bob in the initial game, and v' is a constant depending only on v. in this work, we simplify raz's proof in various ways and thus shorten it significantly. further we study the case where alice and bob are not restricted to local computations and can use any strategy which does not imply communication among them.
hardness of routing with congestion in directed graphs. given as input a directed graph on n vertices and a set ofsource-destination pairs, we study the problem of routing themaximum possible number of source-destination pairs on paths, suchthat at most c(n) paths go through any edge. we show that theproblem is hard to approximate within an nω(1/c(n)) factoreven when we compare to the optimal solution that routes pairs onedge-disjoint paths, assuming np doesn't have no(log logn)-time randomized algorithms. here the congestion c(n) can beany function in the range 1 ≤ c(n) ≤ α log n/log log n for some absolute constant α > 0. the hardness result is in the right ballpark since a factor no(1/c(n)) approximation algorithm is known for this problem, viarounding a natural multicommodity-flow relaxation. we also give asimple integrality gap construction that shows that themulticommodity-flow relaxation has an integrality gap of nω(1/c) for c ranging from 1 to θ((log n)/(log log n)). a solution to the routing problem involves selecting which pairs tobe routed and what paths to assign to each routed pair. two naturalrestrictions can be placed on input instances to eliminate one ofthese aspects of the problem complexity. the first restriction is toconsider instances with perfect completeness; an optimalsolution is able to route all pairs with congestion 1 in suchinstances. the second restriction to consider is the uniquepaths property where each source-destination pair has a unique pathconnecting it in the instance. an important aspect of our result isthat it holds on instances with any one of these tworestrictions. our hardness construction with the perfectcompleteness restriction allows us to conclude that the directedcongestion minimization problem, where the goal is to route allpairs with minimum congestion, is hard to approximate to within afactor of ω(log n/log log n). on the other hand, thehardness construction with unique paths property allows us toconclude an nω(1/c) inapproximability bound also for theall-or-nothing flow problem. this is in a sharp contrast to theundirected setting where the all-or-nothing flow problem is known tobe approximable to within a poly-logarithmic factor.
inapproximability of the tutte polynomial. the tutte polynomial of a graph g is a two-variable polynomial t(g;x,y) that encodes many interesting properties of the graph. we study the complexity of the following problem, for rationals x and y: take as input a graph g, and output a value which is a good approximation to t(g;x,y). jaeger et al. have completely mapped the complexity of exactly computing the tutte polynomial. they have shown that this is #p-hard, except along the hyperbola (x-1)(y-1)=1 and at four special points. we are interested in determining for which points (x,y) there is a fully polynomial randomised approximation scheme (fpras) for t(g;x,y). under the assumption rpnp, there is no fpras at the point (x,y)=(0,1-@l) when @l>2 is a positive integer. thus, there is no fpras for counting nowhere-zero @l flows for @l>2. this is an interesting consequence of our work since the corresponding decision problem is in p for example for @l=6. although our main concern is to distinguish regions of the tutte plane that admit an fpras from those that do not, we also note that the latter regions exhibit different levels of intractability. at certain points (x,y), for example the integer points on the x-axis, or any point in the positive quadrant, there is a randomised approximation scheme for t(g;x,y) that runs in polynomial time using an oracle for an np predicate. on the other hand, we identify a region of points (x,y) at which even approximating t(g;x,y) is as hard as #p.
the communication complexity of uncoupled nash equilibrium procedures. we study the question of how long it takes players to reach a nashequilibrium in uncoupled setups, where each player initially knowsonly his own payoff function. we derive lower bounds on the communication complexity of reaching a nash equilibrium, i.e., on thenumber of bits that need to be transmitted, and thus also on the requirednumber of steps. specifically, we show lower bounds that are exponential inthe number of players in each one of the following cases: (1) reaching apure nash equilibrium; (2) reaching a pure nash equilibrium in a bayesiansetting; and (3) reaching a mixed nash equilibrium. we then show that, incontrast, the communication complexity of reaching a correlated equilibriumis polynomial in the number of players.
space-time tradeoffs and first order problems in a model of programs we introduce a model of programs for comparison-based problems. this model gives a measure of space usage and is &ldquo;uniform&rdquo;. we first obtain upper and lower bounds on the selection problems which demonstrate the tradeoffs between time and space. we next introduce the class of first order problems and characterize them semantically. a surprisingly simple classification of first order problems into three complexity classes is shown. finally we extend the first order problems to the weak second order problems and show that these can be solved in polynomial time by programs in our model augmented with push-down stores.
testing k-wise and almost k-wise independence. in this work, we consider the problems of testing whether adistribution over (0,1n) is k-wise (resp. (ε,k)-wise) independentusing samples drawn from that distribution. for the problem of distinguishing k-wise independent distributions from those that are δ-far from k-wise independence in statistical distance, we upper bound the number ofrequired samples by õ(nk/δ2) and lower bound it by ω(nk-1/2/δ) (these bounds hold for constantk, and essentially the same bounds hold for general k). toachieve these bounds, we use fourier analysis to relate adistribution's distance from k-wise independence to its biases, a measure of the parity imbalance it induces on a setof variables. the relationships we derive are tighter than previouslyknown, and may be of independent interest. to distinguish (ε,k)-wise independent distributions from thosethat are δ-far from (ε,k)-wise independence in statistical distance, we upper bound thenumber of required samples by o(k log n / δ2ε2) and lower bound it by ω(√ k log n / 2k(ε+δ)√ log 1/2k(ε+δ)). although these bounds are anexponential improvement (in terms of n and k) over thecorresponding bounds for testing k-wise independence, we give evidence thatthe time complexity of testing (ε,k)-wise independence isunlikely to be poly(n,1/ε,1/δ) for k=θ(log n),since this would disprove a plausible conjecture concerning the hardness offinding hidden cliques in random graphs. under the conjecture, ourresult implies that for, say, k = log n and ε = 1 / n0.99,there is a set of (ε,k)-wise independent distributions, and a set of distributions at distance δ=1/n0.51 from (ε,k)-wiseindependence, which are indistinguishable by polynomial time algorithms.
all-pairs bottleneck paths for general graphs in truly sub-cubic time. in the all-pairs bottleneck paths (apbp) problem (a.k.a. all-pairs maximum capacity paths), one is given a directed graph with real non-negative capacities on its edges and is asked to determine, for all pairs of vertices s and t, the capacity of a single path for which a maximum amount of flow can be routed from s to t. the apbp problem was first studied in operations research, shortly after the introduction of maximum flows and all-pairs shortest paths. we present the first truly sub-cubic algorithm for apbp in general dense graphs. in particular, we give a procedure for computing the (max, min)-product of two arbitrary matrices over r ∪ (∞,-∞) in o(n2+ω/3) ≤ o(n2.792) time, where n is the number of vertices and ω is the exponent for matrix multiplication over rings. using this procedure, an explicit maximum bottleneck path for any pair of nodes can be extracted in time linear in the length of the path.
towards 3-query locally decodable codes of subexponential length. a q-query locally decodable code (ldc) encodes an n-bit message x as an n-bit codeword c(x), such that one can probabilistically recover any bit xi of the message by querying only q bits of the codeword c(x), even after some constant fraction of codeword bits has been corrupted. we give new constructions of three query ldcs of vastly shorter length than that of previous constructions. specifically, given any mersenne prime p &equals; 2t &minus; 1, we design three query ldcs of length n &equals; exp(o(n1/t)), for every n. based on the largest known mersenne prime, this translates to a length of less than exp(o(n10 &minus; 7)) compared to exp(o(n1/2)) in the previous constructions. it has often been conjectured that there are infinitely many mersenne primes. under this conjecture, our constructions yield three query locally decodable codes of length n &equals; exp(no(1/log log n)) for infinitely many n. we also obtain analogous improvements for private information retrieval (pir) schemes. we give 3-server pir schemes with communication complexity of o(n10 &minus; 7) to access an n-bit database, compared to the previous best scheme with complexity o(n1/5.25). assuming again that there are infinitely many mersenne primes, we get 3-server pir schemes of communication complexity no(1/log logn)) for infinitely many n. previous families of ldcs and pir schemes were based on the properties of low-degree multivariate polynomials over finite fields. our constructions are completely different and are obtained by constructing a large number of vectors in a small dimensional vector space whose inner products are restricted to lie in an algebraically nice set.
hardness-randomness tradeoffs for bounded depth arithmetic circuits. in this paper we show that lower bounds for bounded depth arithmetic circuits imply derandomization of polynomial identity testing for bounded depth arithmetic circuits. more formally, if there exists an explicit polynomial f(x1,...,xm) that cannot be computed by a depth d arithmetic circuit of small size then there exists an efficient deterministic algorithm to test whether a given depth d-8 circuit is identically zero or not (assuming the individual degrees of the tested circuit are not too high). in particular, if we are guaranteed that the circuit computes a multilinear polynomial then we can perform the identity test efficiently. to the best of our knowledge this is the first hardness-randomness tradeoff for bounded depth arithmetic circuits. the above results are obtained using the arithmetic nisan-wigderson generator of impagliazzo and kabanets together with a new theorem on bounded depth circuits, which is the main technical contribution of our work. this theorem deals with polynomial equations of the form p(x1,...,xn,y) ≡ 0 and shows that if p has a circuit of depth d and size s and if the polynomial f(x1,...,xn) satisfies p(x1,...,xn,f(x1,...,xn))≡ 0 then f has a circuit of depth d+3 and size o(s • r + mr), where m is the degree of f and r is the highest degree of the variable y appearing in p. in the other direction we observe that the methods of impagliazzo and kabanets imply that if we can derandomize polynomial identity testing for bounded depth circuits then nexp does not have bounded depth arithmetic circuits. that is, either nexp ⊄ p/poly or the permanent is not computable by polynomial size bounded depth arithmetic circuits.
graph sparsification by effective resistances. we present a nearly-linear time algorithm that produces high-quality sparsifiers of weighted graphs. given as input a weighted graph g=(v,e,w) and a parameter ε>0, we produce a weighted subgraph h=(v,~e,~w) of g such that |~e|=o(n log n/ε2) and for all vectors x in rv. (1-ε) ∑uv ∈ e (x(u)-x(v))2wuv≤ ∑uv in ~e(x(u)-x(v))2~wuv ≤ (1+ε)∑uv ∈ e(x(u)-x(v))2wuv. this improves upon the sparsifiers constructed by spielman and teng, which had o(n logc n) edges for some large constant c, and upon those of benczur and karger, which only satisfied (1) for x in {0,1}v. we conjecture the existence of sparsifiers with o(n) edges, noting that these would generalize the notion of expander graphs, which are constant-degree sparsifiers for the complete graph. a key ingredient in our algorithm is a subroutine of independent interest: a nearly-linear time algorithm that builds a data structure from which we can query the approximate effective resistance between any two vertices in a graph in o(log n) time.
sampling-based dimension reduction for subspace approximation. we give a randomized bi-criteria algorithm for the problem of finding a k-dimensional subspace that minimizesthe lp-error for given points, i.e., p-th root of the sum of p-th powers of distances to given points,for any p ≥ 1. our algorithm runs in time õ (mn · pk3 (k/ε)2p) andproduces a subset of size õ (pk2 (k/ε)2p) from the given points such that, withhigh probability, the span of these points gives a (1+ε)-approximation to the optimal k-dimensionalsubspace. we also show a dimension reduction type of result for this problem where we can efficiently find asubset of size õ (pk2(p+1) + (k/ε)p+2) such that, with high probability, theirspan contains a k-dimensional subspace that gives (1+ε)-approximation to the optimum. we prove similarresults for the corresponding projective clustering problem where we need to find multiple k-dimensional subspaces.
faster approximate lossy generalized flow via interior point algorithms. we present asymptotically faster approximation algorithms for the generalized flow problems in which multipliers on edges are at most 1. for this lossy version of the maximum generalized flow problem, we obtain an additive ε approximation of the maximum flow in time o{m3/2 log (u/ε)2}, where m is the number of edges in the graph, all capacities are integers in the range {1, ... , u}, and all loss multipliers are ratios of integers in this range. for minimum cost lossy generalized flow with costs in the range {1,... ,u}, we obtain a flow that has value within an additive ε of the maximum value and cost at most the optimal cost. in many parameter ranges, these algorithms improve over the previously fastest algorithms for the generalized maximum flow problem by a factor of m1/2 and for the minimum cost generalized flow problem by a factor of approximately m1/2/ ε2. the algorithms work by accelerating traditional interior point algorithms by quickly solving the system of linear equations that arises in each step. the contributions of this paper are twofold. first, we analyze the performance of interior point algorithms with approximate linear system solvers. this analysis alone provides an algorithm for the standard minimum cost flow problem that runs in time om3/2 log u}--an improvement of roughly o{n / m1/2} over previous algorithms. second, we examine the linear equations that arise when using an interior point algorithm to solve generalized flow problems. we observe that these belong to the family of symmetric m-matrices, and we then develop om-time algorithms for solving linear systems in these matrices. these algorithms reduce the problem of solving a linear system in a symmetric m-matrix to that of solving o{log n} linear systems in symmetric diagonally-dominant matrices, which we can do in time om using the algorithm of spielman and teng. all of our algorithms operate on numbers of bit length at most o{log n u / ε}.
a combinatorial construction of almost-ramanujan graphs using the zig-zag product. reingold, vadhan and wigderson [21] introduced the graph zig-zag product. this product combines a large graph and a small graph into one graph, such that the resulting graph inherits its size from the large graph, its degree from the small graph and its spectral gap from both. using this product they gave the first fully-explicit combinatorial construction of expander graphs. they showed how to construct d-regular graphs having spectral gap 1-o(d-1/3). in the same paper, they posed the open problem of whether a similar graph product could be used to achieve the almost-optimal spectral gap 1-o(d-1/2). in this paper we propose a generalization of the zig-zag product that combines a large graph and several small graphs. the new product gives a better relation between the degree and the spectral gap of the resulting graph. we use the new product to give a fully-explicit combinatorial construction of d-regular graphs having spectral gap 1-d-1/2 + o(1).