waashk/dblp huggingface dataset:
smooth sensitivity and sampling in private data analysis. we introduce a new, generic framework for private data analysis.the goal of private data analysis is to release aggregate information about a data set while protecting the privacy of the individuals whose information the data set contains.our framework allows one to release functions f of the data withinstance-based additive noise. that is, the noise magnitude is determined not only by the function we want to release, but also bythe database itself. one of the challenges is to ensure that the noise magnitude does not leak information about the database. to address that, we calibrate the noise magnitude to the smoothsensitivity of f on the database x --- a measure of variabilityof f in the neighborhood of the instance x. the new frameworkgreatly expands the applicability of output perturbation, a technique for protecting individuals' privacy by adding a smallamount of random noise to the released statistics. to our knowledge, this is the first formal analysis of the effect of instance-basednoise in the context of data privacy. our framework raises many interesting algorithmic questions. namely,to apply the framework one must compute or approximate the smoothsensitivity of f on x. we show how to do this efficiently for several different functions, including the median and the cost ofthe minimum spanning tree. we also give a generic procedure based on sampling that allows one to release f(x) accurately on manydatabases x. this procedure is applicable even when no efficient algorithm for approximating smooth sensitivity of f is known orwhen f is given as a black box. we illustrate the procedure by applying it to k-sed (k-means) clustering and learning mixtures of gaussians.
a polynomial combinatorial algorithm for generalized minimum cost flow. we propose the first combinatorial solution to the generalized minimum cost flow problem (flow with losses and gains). despite a rich history dating back to kantorovich and dantzig, until now, the only known way to solve the problem in polynomial-time was via general-purpose linear programming techniques. polynomial combinatorial algorithms were previously known only for the version of our problem without costs. we design the first such algorithms for the version with costs. our algorithms also find provably good solutions faster than optimal ones, providing the first strongly polynomial approximation schemes for the problem.our techniques extend to optimize linear programs with two variables per inequality. polynomial combinatorial algorithms were previously developed for testing the feasibility of such linear programs. we propose the first such methods for the optimization version.
survivable network design with degree or order constraints. we present algorithmic and hardness results for network design problems with degree or order constraints. the first problem we consider is the survivable network design problem with degree constraints on vertices. the objective is to find a minimum cost subgraph which satisfies connectivity requirements between vertices and also degree upper bounds $b_v$ on the vertices. this includes the well-studied minimum bounded degree spanning tree problem as a special case. our main result is a $(2,2b_v+3)$-approximation algorithm for the edge-connectivity survivable network design problem with degree constraints, where the cost of the returned solution is at most twice the cost of an optimum solution (satisfying the degree bounds) and the degree of each vertex $v$ is at most $2b_v+3$. this implies the first constant factor (bicriteria) approximation algorithms for many degree constrained network design problems, including the minimum bounded degree steiner forest problem. our results also extend to directed graphs and provide the first constant factor (bicriteria) approximation algorithms for the minimum bounded degree arborescence problem and the minimum bounded degree strongly $k$-edge-connected subgraph problem. in contrast, we show that the vertex-connectivity survivable network design problem with degree constraints is hard to approximate, even when the cost of every edge is zero. a striking aspect of our algorithmic result is its simplicity. it is based on the iterative relaxation method, which is an extension of jain's iterative rounding method. this provides an elegant and unifying algorithmic framework for a broad range of network design problems. we also study the problem of finding a minimum cost $\lambda$-edge-connected subgraph with at least $k$ vertices, which we call the $(k,\lambda)$-subgraph problem. this generalizes some well-studied classical problems such as the $k$-mst and the minimum cost $\lambda$-edge-connected subgraph problems. we give a polylogarithmic approximation for the $(k,2)$-subgraph problem. however, by relating it to the densest $k$-subgraph problem, we provide evidence that the $(k,\lambda)$-subgraph problem might be hard to approximate for arbitrary $\lambda$.
lattices that admit logarithmic worst-case to average-case connection factors. we exhibit an average-case problem that is as hard as finding γ(n)-approximate shortest nonzero vectors in certain n-dimensional lattices in the worst case, for γ(n) = o(√log n). the previously best known factor for any non-trivial class of lattices was γ(n) = õ(n). our results apply to families of lattices having special algebraic structure. specifically, we consider lattices that correspond to ideals in the ring of integers of an algebraic number field. the worst-case problem we rely on is to find approximate shortest vectors in these lattices, under an appropriate form of preprocessing of the number field. for the connection factors γ(n) we achieve, the corresponding decision problems on ideal lattices are not known to be np-hard; in fact, they are in p. however, the search approximation problems still appear to be very hard. indeed, ideal lattices are well-studied objects in computational number theory, and the best known algorithms for them seem to perform no better than the best known algorithms for general lattices. to obtain the best possible connection factor, we instantiate our constructions with infinite families of number fields having constant root discriminant. such families are known to exist and are computable, though no efficient construction is yet known. our work motivates the search for such constructions. even constructions of number fields having root discriminant up to o(n2/3-ε) would yield connection factors better than õ(n). as an additional contribution, we give reductions between various worst-case problems on ideal lattices, showing for example that the shortest vector problem is no harder than the closest vector problem. these results are analogous to previously-known reductions for general lattices.
neighborhood search algorithms for finding optimal traveling salesman tours must be inefficient search in this paper, we explore the use of neighborhood search techniques for finding optimal solutions to the symmetric traveling salesman problem. these techniques have been dramatically successful in obtaining near-optimal solutions to this problem for a reasonable expenditure of effort (1,2,3,4,5,6,9,10,12). extensions of these techniques can be used to obtain the globally optimum solution, but the effort involved is at least an exponential function of the number of cities, n. indeed, as this paper demonstrates, all local search algorithms that are capable of finding the optimal solution to an arbitrary n-city problem must grow at least as fast as equation !. thus for large problems, these algorithms are computationally inefficient. in following section we show that any exact neighborhood search algorithm for the traveling salesman problem must inspect a prohibitively large number of feasible solutions. we begin with a brief discussion of the traveling salesman problem (tsp) and neighborhood search techniques in section ii. in section iii we develop a necessary condition for neighborhood search to converge to an optimal solution. we use this result in sections iv and v to obtain a lower bound on the effectiveness of neighborhood search as applied to the tsp.
computing crossing number in linear time. we show that for every fixed k, there is a linear time algorithm that decides whether or not a given graph has crossing number at most k, and if this is the case, computes a drawing of the graph in the plane with at most k crossings. this answers the question posed by grohe (stoc'01 and jcss 2004). our algorithm can be viewed as a generalization of the seminal result by hopcroft and tarjan lin1, which determines if a given graph is planar in linear time. our algorithm can also be compared to the algorithms by mohar (stoc'96 and siam j. discrete math 2001), for testing the embeddability of an input graph in a fixed surface. for each surface s, mohar describes an algorithm which yields either an embedding of g in s or a minor of g which is not embeddable in s and is minimal with this property. the same approach allows us to obtain linear time algorithms for the same question for a variety of other crossing numbers. we can also determine in linear time if an input graph can be made planar by the deletion of k edges (for fixed k).
counting independent sets up to the tree threshold. consider the problem of approximately counting weighted independent sets of a graph g with activity λ, i.e., where the weight of an independent set i is λ|i|. we present a novel analysis yielding a deterministic approximation scheme which runs in polynomial time for any graph of maximum degree δ and λ< λc=(δ-1)δ-1/(δ-2)δ. this improves on the previously known general bound of λ ≤ (2 ‾ δ-2). the new regime includes the interesting case of λ=1 (uniform weights) and δ ≤ 5. the previous bound required δ ≤ 4 for uniform approximate counting and there is evidence that for δ ≥ 6 the problem is hard. note that λc is the critical activity for uniqueness of the gibbs measure on the regular tree of degree δ, i.e., for λ ≤ λc the probability that the root is in the independent set is asymptotically independent of the configuration on the leaves far below. indeed, our analysis is focused on establishing decay of correlations with distance in the above weighted distribution. we show that on any graph of maximum degree δ correlations decay with distance at least as fast as they do on the regular tree of the same degree. this resolves an open conjecture in statistical physics. our comparison of a general graph with the tree uses an algorithmic argument yielding the approximation scheme mentioned above. also, by existing arguments, establishing decay of correlations for all graphs and λ<λc gives that the glauber dynamics is rapidly mixing in this regime. however, the implication from decay of correlations to rapid mixing of the dynamics is only known to hold for graphs of subexponential growth, and hence, our result regarding the glauber dynamics is limited to this class of graphs.
the condition number of a randomly perturbed matrix. let m be an arbitrary n by n matrix. we study the conditionnumber a random perturbation m+nn of m, where nn is arandom matrix. it is shown that, under very general conditions on m and mn, the condition number of m+nn is polynomial in nwith very high probability. the main novelty here is that we allow nn to have discrete distribution.
proportional response dynamics leads to market equilibrium. one of the main reasons of the recent success of peer to peer (p2p)file sharing systems such as bittorrent is their built-in tit-for-tat mechanism. in this paper, we model the bandwidth allocation in a p2p system as an exchange economy and study a tit-for-tat dynamics, namely the proportional response dynamics, in this economy. in aproportional response dynamics each player distributes its good to its neighbors proportional to the utility it received from them in thelast period. we show that this dynamics not only converges but converges to a market equilibrium, a standard economic characterization of efficient exchanges in a competitive market. in addition, for some classes of utility functions we consider, it converges much faster than the classical tat process and any existingalgorithms for computing market equilibria. as a part of our proof we study the double normalization of a matrix, an operation that linearly scales the rows of a matrix sothat each row sums to a prescribed positive number, followed by a similar scaling of the columns. we show that the iterative double normalization process of any non-negative matrix always converges. this complements the previous studies in matrix scaling that has focused on the convergence condition of the process when the row and column normalizations are considered as separate steps.
depth through breadth, or why should we attend talks in other areas? given that the two other invited lectures in this conference are on such remote areas as "quantum computation" and "algorithmic game theory," and given the diversity of other topics represented in the program, it makes sense to ask if the stoc/focs community is still one.indeed, the program chair has asked me to respond to this question.in the talk i'll try to illustrate, with a few (of many) examples, how the presence of such diversity in our community and conferences was actually responsible for important progress in specific areas of research, why i find these a natural and expected phenomena, and why i expect this trend to continue.
simple deterministic approximation algorithms for counting matchings. we construct a deterministic fully polynomial time approximationscheme (fptas) for computing the total number of matchings in abounded degree graph. additionally, for an arbitrary graph, weconstruct a deterministic algorithm for computing approximately thenumber of matchings within running time exp(o(√n log2n)),where n is the number of vertices. our approach is based on the correlation decay technique originating in statistical physics. previously thisapproach was successfully used for approximately counting thenumber of independent sets and colorings in some classes of graphs [1, 24, 6].thus we add another problem to the small, but growing, class of p-complete problems for whichthere is now a deterministic fptas.
a new approximate graph coloring algorithm let a be a graph coloring algorithm. denote by -&-agrave; (g) the ratio between the maximum number of colors a will use to color the graph g, and the chromatic number of g,x(g). for most existing polynomial coloring algorithms, -&-agrave;(g) can be as bad as o(n), where n is the number of vertices in g. the best currently known algorithm guarantees -&-agrave; (g)-&-equil;o(n/logn). in this paper we present a simple and efficient coloring algorithm which guarantees -&-agrave;(g)-&-le;x(g)n (equation), a considerable improvem-&-edot;nt over the current bounds.
uncertainty principles, extractors, and explicit embeddings of l2 into l1. we give an explicit construction of a constant distortion embedding f of l2n into l1m, with m=n1+o(1).as a bonus, our embedding also has good computational properties: for any input x, fx can be computed in n1+o(1) time.the previously known mappings required ω(n2) evaluation time.
balanced allocations: the weighted case. we investigate balls-and-bins processes where m weighted balls areplaced into n bins using the "power of two choices" paradigm,whereby a ball is inserted into the less loaded of two randomly chosen bins. the case where each of the m balls has unit weight had been studied extensively. in a seminal paper azar et.al. showed that when m=n the most loaded bin has θ(log log n) balls with high probability. surprisingly, thegap in load between the heaviest bin and the average bin does not increase with m and was shown by berenbrink etal tobe θ(log log n) with high probability for arbitrarily large m. we generalize this result to the weighted case where balls have weights drawn from an arbitrary weight distribution. we show that aslong as the weight distribution has finite second moment andsatisfies a mild technical condition, the gap between the weight of the heaviest bin and the weight of the average bin is independent ofthe number balls thrown. this is especially striking whenconsidering heavy tailed distributions such as power-law andlog-normal distributions. in these cases, as more balls are thrown,heavier and heavier weights are encountered. nevertheless with high probability, the imbalance in the load distribution does notincrease. furthermore, if the fourth moment of the weight distribution is finite, the expected value of the gap is shown to beindependent of the number of balls.
local embeddings of metric spaces. in many application areas, complex data sets are often representedby some metric space and metric embedding is used to provide a more structured representation of the data. in many of these applications much greater emphasis is put on the preserving the local structure of the original space than on maintaining its complete structure. this is also the case in some networking applications where "small world" phenomena in communication patterns has been observed. practical study of embedding has indeed involved with finding embeddings with this property. in this paper we initiate thestudy of local embeddings of metric spaces and provide embeddings with distortion depending solely on the local structureof the space.
white pebbles help a family of directed acyclic graphs of vertex indegree 2 is constructed for which there are strategies of the black-white pebble game that use asymptotically fewer pebbles than the best strategies of the black pebble game. this shows that there are straight-line programs that can be evaluated nondeterministically with asymptotically less space than is required by any deterministic evaluation.
maintaining dense sequential files in a dynamic environment (extended abstract) in this article, we study an alternate approach that shifts the records among adjacent pages rather than using overflow pointers when space is needed for inserting a record in a sequential file. we show how to use this method to achieve a worst-case record insertion-deletion complexity of o[(log2n)/(d-d)] page-accesses, in (d-d)-dense files.
more algorithms for all-pairs shortest paths in weighted graphs. in the first part of the paper, we reexamine the all-pairsshortest paths (apsp) problem and present a newalgorithm with running time approaching o(n3/log2n), which improves all known algorithms for general real-weighted dense graphs andis perhaps close to the best result possible without using fast matrix multiplication, modulo a few log log n factors. in the second part of the paper, we use fast matrix multiplication to obtain truly subcubic apsp algorithms for a large class of "geometrically weighted" graphs, where the weight of an edge is a function of the coordinates of its vertices. for example, for graphs embedded in euclidean space of a constant dimension d, we obtain a time bound near o(n3-(3-ω)/(2d+4)), where ω < 2.376 ; in two dimensions, this is o(n2.922). our framework greatly extends the previously considered case of small-integer-weighted graphs, and incidentally also yields the first truly subcubic result (near o(n3-(3-ω)/4)=o(n2.844) time) forapsp in real-vertex-weighted graphs, as well as an improved result (near o(n(3+ω)/2)=o(n2.688) time) for the all-pairs lightest shortest path problem for small-integer-weighted graphs.
exponential separations for one-way quantum communication complexity, with applications to cryptography. we give an exponential separation between one-way quantum and classical communication protocols for a partial boolean function (a variant of the boolean hidden matching problem of bar-yossef et al.). previously, such an exponential separation was known only for a relational problem. the communication problem corresponds to a strong extractor that fails against a small amount of quantum information about its random source. our proof uses the fourier coefficients inequality of kahn, kalai, and linial. we also give a number of applications of this separation. in particular, we show that there are privacy amplification schemes that are secure against classical adversaries but not against quantum adversaries; and we give the first example of a key-expansion scheme in the model of bounded-storage cryptography that is secure against classical memory-bounded adversaries but not against quantum ones.
combinatorial complexity in o-minimal geometry. in this paper we prove tight bounds on the combinatorial and topological complexity of sets dened in terms of n denable sets belonging to some fixed denable family of sets in an o-minimal structure. this generalizes the combinatorial parts of similar bounds known in the case of semi-algebraic and semi-pfaffian sets, and as a result vastly increases the applicability of results on combinatorial and topological complexity of arrangements studied in discrete and computational geometry. as a sample application, we extend a ramsey-type theorem due to alon et al. [3], originally proved for semi-algebraic sets of fixed description complexity to this more general setting.
domolki's algorithm applied to generalized overlap resolvable grammars recently hext and roberts have attempted to refine domolki's parsing algorithm to include limited context checking. this paper links their effort to lynch's overlap resolvable grammars, which are here extended to include &egr;-rules. both lynch's and hext and roberts' versions of the algorithm are modified, the former with a considerable time improvement and the latter using the full power of overlap resolvability. results are also proposed on removing 1-productions from overlap resolvable grammars for such parsers, answering a question of lynch. both new formulations of the algorithm can be efficiently implemented: the former being particularly suited for fixed word length machines, and the latter for newer array processing systems. an extension of these algorithms to parse deremer's slr(1) class of grammars is demonstrated.
statistically-hiding commitment from any one-way function. we give a construction of statistically-hiding commitment schemes (ones where the hiding propertyholds information theoretically), based on the minimal cryptographic assumption that one-way functions exist. our construction employs two-phase commitment schemes, recently constructed by nguyen, ong and vadhan (focs '06), and universal one-way hash functions introduced and constructedby naor and yung (stoc '89) and rompel (stoc '90).
degree-languages, polynomial time recognition, and the lba problem the so-called chomsky hierarchy [5], consisting of regular, context-free, context-sensitive, and recursively enumerable languages, does not account for many &ldquo;real world&rdquo; classes of languages, e.g., programming languages and natural languages [4]. this is one of the reasons why many attempts have been made to &ldquo;refine&rdquo; the original chomsky classification. the main goal has been to describe languages which, for instance, are not context-free but are still context-sensitive, without using the powerful and complex concept of context-sensitive grammars.