waashk/dblp huggingface dataset:
load balancing and orientability thresholds for random hypergraphs. let h>w>0 be two fixed integers. let h be a random hypergraph whose hyperedges are all of cardinality h. to w-orient a hyperedge, we assign exactly w of its vertices positive signs with respect to the hyperedge, and the rest negative. a (w,k)-orientation of h consists of a w-orientation of all hyperedges of h, such that each vertex receives at most k positive signs from its incident hyperedges. when k is large enough, we determine the threshold of the existence of a (w,k)-orientation of a random hypergraph. the (w,k)-orientation of hypergraphs is strongly related to a general version of the off-line load balancing problem. the graph case, when h=2 and w=1, was solved recently by cain, sanders and wormald and independently by fernholz and ramachandran, thereby settling a conjecture made by karp and saks. motivated by a problem of cuckoo hashing, the special hypergraph case with w=k=1, was solved in three separate preprints dating from october 2009, by frieze and melsted, by fountoulakis and panagiotou, and by dietzfelbinger, goerdt, mitzenmacher, montanari, pagh and rink.
bounding the average sensitivity and noise sensitivity of polynomial threshold functions. we give the first non-trivial upper bounds on the average sensitivity and noise sensitivity of degree-d polynomial threshold functions (ptfs). these bounds hold both for ptfs over the boolean hypercube {-1,1}n and for ptfs over rn under the standard n-dimensional gaussian distribution n(0,in). our bound on the boolean average sensitivity of ptfs represents progress towards the resolution of a conjecture of gotsman and linial [17], which states that the symmetric function slicing the middle d layers of the boolean hypercube has the highest average sensitivity of all degree-d ptfs. via the l1 polynomial regression algorithm of kalai et al. [22], our bounds on gaussian and boolean noise sensitivity yield polynomial-time agnostic learning algorithms for the broad class of constant-degree ptfs under these input distributions. the main ingredients used to obtain our bounds on both average and noise sensitivity of ptfs in the gaussian setting are tail bounds and anti-concentration bounds on low-degree polynomials in gaussian random variables [20, 7]. to obtain our bound on the boolean average sensitivity of ptfs, we generalize the "critical-index" machinery of [37] (which in that work applies to halfspaces, i.e. degree-1 ptfs) to general ptfs. together with the "invariance principle" of [30], this lets us extend our techniques from the gaussian setting to the boolean setting. our bound on boolean noise sensitivity is achieved via a simple reduction from upper bounds on average sensitivity of boolean ptfs to corresponding bounds on noise sensitivity.
weighted geometric set cover via quasi-uniform sampling. there has been much progress on geometric set cover problems, but most known techniques only apply to the unweighted setting. for the weighted setting, very few results are known with approximation guarantees better than that for the combinatorial set cover problem. in this article, we employ the idea of quasi-uniform sampling to obtain improved approximation guarantees in the weighted setting for a large class of problems for which such guarantees were known in the unweighted case. as a consequence of this sampling method, we obtain new results on the fractional set cover packing problem.
changing base without losing space. we describe a simple, but powerful local encoding technique, implying two surprising results: 1. we show how to represent a vector of n values from some alphabet s using ceiling(n * log2 |s|) bits, such that reading or writing any entry takes o(1) time. this demonstrates, for instance, an "equivalence" between decimal and binary computers, and has been a central toy problem in the field of succinct data structures. previous solutions required space of n * log2 |s| + n/logo(1) n bits for constant access. 2. given a stream of n bits arriving online (for any n, not known in advance), we can output a *prefix-free* encoding that uses n + log2 n + o(loglog n) bits. the encoding and decoding algorithms only require o(log n) bits of memory, and run in constant time per word. this result is interesting in cryptographic applications, as prefix-free codes are the simplest counter-measure to extensions attacks on hash functions, message authentication codes and pseudorandom functions. our result refutes a conjecture of [maurer, sjodin 2005] on the hardness of online prefix-free encodings.
are many small sets explicitly small? we discuss various aspects of a conjecture that spans analysis, probability and combinatorics. we find it interesting enough to offer a $1000 prize for a solution of any of the main problems.
a deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. we give deterministic ~o(22n+o(n))-time algorithms to solve all the most important computational problems on point lattices in np, including the shortest vector problem (svp), closest vector problem (cvp), and shortest independent vectors problem (sivp). this improves the no(n) running time of the best previously known algorithms for cvp (kannan, math. operation research 12(3):415--440, 1987) and sivp (micciancio, proc. of soda, 2008), and gives a deterministic and asymptotically faster alternative to the 2o(n)-time (and space) randomized algorithm for svp of (ajtai, kumar and sivakumar, stoc 2001). the core of our algorithm is a new method to solve the closest vector problem with preprocessing (cvpp) that uses the voronoi cell of the lattice (described as intersection of half-spaces) as the result of the preprocessing function. in the process, we also give algorithms for several other lattice problems, including computing the kissing number of a lattice, and computing the set of all voronoi relevant vectors. all our algorithms are deterministic, and have 2o(n) time and space complexity.
complexity theory for operators in analysis. we propose a new framework for discussing computational complexity of problems involving uncountably many objects, such as real numbers, sets and functions, that can be represented only through approximation. the key idea is to use a certain class of string functions, which we call regular functions, as names representing these objects. these are more expressive than infinite sequences, which served as names in prior work that formulated complexity in more restricted settings. an important advantage of using regular functions is that we can define their size in the way inspired by higher-type complexity theory. this enables us to talk about computation on regular functions whose time or space is bounded polynomially in the input size, giving rise to more general analogues of the classes p, np, and pspace. we also define np- and pspace-completeness under suitable many-one reductions. because our framework separates machine computation and semantics, it can be applied to problems on sets of interest in analysis once we specify a suitable representation (encoding). as prototype applications, we consider the complexity of functions (operators) on real numbers, real sets, and real functions. the latter two cannot be represented succinctly using existing approaches based on infinite sequences, so ours is the first treatment of them. as an interesting example, the task of numerical algorithms for solving the initial value problem of differential equations is naturally viewed as an operator taking real functions to real functions. as there was no complexity theory for operators, previous results could only state how complex the solution can be. we now reformulate them to show that the operator itself is polynomial-space complete.
interactive privacy via the median mechanism. we define a new interactive differentially private mechanism --- the median mechanism --- for answering arbitrary predicate queries that arrive online. given fixed accuracy and privacy constraints, this mechanism can answer exponentially more queries than the previously best known interactive privacy mechanism (the laplace mechanism, which independently perturbs each query result). with respect to the number of queries, our guarantee is close to the best possible, even for non-interactive privacy mechanisms. conceptually, the median mechanism is the first privacy mechanism capable of identifying and exploiting correlations among queries in an interactive setting. we also give an efficient implementation of the median mechanism, with running time polynomial in the number of queries, the database size, and the domain size. this efficient implementation guarantees privacy for all input databases, and accurate query results for almost all input distributions. the dependence of the privacy on the number of queries in this mechanism improves over that of the best previously known efficient mechanism by a super-polynomial factor, even in the non-interactive setting.
efficiently learning mixtures of two gaussians. given data drawn from a mixture of multivariate gaussians, a basic problem is to accurately estimate the mixture parameters. we provide a polynomial-time algorithm for this problem for the case of two gaussians in $n$ dimensions (even if they overlap), with provably minimal assumptions on the gaussians, and polynomial data requirements. in statistical terms, our estimator converges at an inverse polynomial rate, and no such estimator (even exponential time) was known for this problem (even in one dimension). our algorithm reduces the n-dimensional problem to the one-dimensional problem, where the method of moments is applied. one technical challenge is proving that noisy estimates of the first six moments of a univariate mixture suffice to recover accurate estimates of the mixture parameters, as conjectured by pearson (1894), and in fact these estimates converge at an inverse polynomial rate. as a corollary, we can efficiently perform near-optimal clustering: in the case where the overlap between the gaussians is small, one can accurately cluster the data, and when the gaussians have partial overlap, one can still accurately cluster those data points which are not in the overlap region. a second consequence is a polynomial-time density estimation algorithm for arbitrary mixtures of two gaussians, generalizing previous work on axis-aligned gaussians (feldman {\em et al}, 2006).
approximations for the isoperimetric and spectral profile of graphs and related parameters. the spectral profile of a graph is a natural generalization of the classical notion of its rayleigh quotient. roughly speaking, given a graph g, for each 0g(δ) minimizes the rayleigh quotient (from the variational characterization) of the spectral gap of the laplacian matrix of g over vectors with support at most δ over a suitable probability measure. formally, the spectral profile λg of a graph g is a function λg : [0,1/2] -> r defined as: λg(δ) def= minx∈ rvd(supp(x))≤ δ (∑gij (xi-xj)2)/(∑i di xi2) where gij is the weight of the edge (i,j) in the graph, di is the degree of vertex i, and d(\supp(x)) is the fraction of edges incident on vertices within the support of vector x. while the notion of the spectral profile has numerous applications in markov chain, it is also is closely tied to its isoperimetric profile of a graph. specifically, the spectral profile is a relaxation for the problem of approximating edge expansion of small sets in graphs. in this work, we obtain an efficient algorithm that yields a log(1/δ)-factor approximation for the value of λg(δ). by virtue of its connection to edge-expansion, we also obtain an algorithm for the problem of approximating edge expansion of small linear sized sets in a graph. this problem was recently shown to be intimately connected to the unique games conjecture in [18]. finally, we extend the techniques to obtain approximation algorithms with similar guarantees for restricted eigenvalue problems on diagonally dominant matrices.
combinatorial approach to the interpolation method and scaling limits in sparse random graphs. we establish the existence of free energy limits for several sparse random hypergraph models corresponding to certain combinatorial models on erdos-renyi (er) graph g(n,c/n) and random r-regular graph g(n,r). for a variety of models, including independent sets, max-cut, coloring and k-sat, we prove that the free energy both at a positive and zero temperature, appropriately rescaled, converges to a limit as the size of the underlying graph diverges to infinity. in the zero temperature case, this is interpreted as the existence of the scaling limit for the corresponding combinatorial optimization problem. for example, as a special case we prove that the size of a largest independent set in these graphs, normalized by the number of nodes converges to a limit w.h.p., thus resolving an open problem, (see conjecture 2.20 in wormald's random graph models, or aldous's list of open problems. our approach is based on extending and simplifying the interpolation method of guerra and toninelli. among other applications, this method was used to prove the existence of free energy limits for viana-bray and k-sat models on er graphs. the case of zero temperature was treated by taking limits of positive temperature models. we provide instead a simpler combinatorial approach and work with the zero temperature case (optimization) directly both in the case of er graph g(n,c/n) and random regular graph g(n,r). in addition we establish the large deviations principle for the satisfiability property for constraint satisfaction problems such as coloring, k-sat and nae-k-sat.
saving space by algebraization. the subset sum and knapsack problems are fundamental np-complete problems and the pseudo-polynomial time dynamic programming algorithms for them appear in every algorithms textbook. the algorithms require pseudo-polynomial time and space. since we do not expect polynomial time algorithms for subset sum and knapsack to exist, a very natural question is whether they can be solved in pseudo-polynomial time and polynomial space. in this paper we answer this question affirmatively, and give the first pseudo-polynomial time, polynomial space algorithms for these problems. our approach is based on algebraic methods and turns out to be useful for several other problems as well. then we show how the framework yields polynomial space exact algorithms for the classical traveling salesman, weighted set cover and weighted steiner tree problems as well. our algorithms match the time bound of the best known pseudo-polynomial space algorithms for these problems.
maintaining a large matching and a small vertex cover. we consider the problem of maintaining a large matching and a small vertex cover in a dynamically changing graph. each update to the graph is either an edge deletion or an edge insertion. we give the first randomized data structure that simultaneously achieves a constant approximation factor and handles a sequence of k updates in k*polylog(n) time, where n is the number of vertices in the graph. previous data structures require a polynomial amount of computation per update.
connectivity oracles for failure prone graphs. dynamic graph connectivity algorithms have been studied for many years, but typically in the most general possible setting, where the graph can evolve in completely arbitrary ways. in this paper we consider a dynamic subgraph model. we assume there is some fixed, underlying graph that can be preprocessed ahead of time. the graph is subject only to vertices and edges flipping "off" (failing) and "on" (recovering), where queries naturally apply to the subgraph on edges/vertices currently flipped on. this model fits most real world scenarios, where the topology of the graph in question (say a router network or road network) is constantly evolving due to temporary failures but never deviates too far from the ideal failure-free state. we present the first efficient connectivity oracle for graphs susceptible to vertex failures. given vertices u and v and a set d of d failed vertices, we can determine if there is a path from u to v avoiding d in time polynomial in d log n. there is a tradeoff in our oracle between the space, which is roughly mnε, for 0d)) or update time ω(dn), that is, linear in the number of vertices. our connectivity oracle is therefore the first of its kind. as a byproduct of our oracle for vertex failures we reduce the problem of constructing an edge-failure oracle to 2d range searching over the integers. we show there is an ~o(m)-space oracle that processes any set of d failed edges in o(d2 log log n) time and, thereafter, answers connectivity queries in o(log log n) time. our update time is exponentially faster than a recent connectivity oracle of patrascu and thorup for bounded d, but slower as a function of d.
the hom problem is decidable. we provide an algorithm that, given a tree homomorphism h and a regular tree language l represented by a tree automaton, determines whether h(l) is regular. this settles a question that has been open for a long time. along the way, we develop new constructions and techniques which are interesting by themselves, and provide several significant intermediate results. for example, we prove that the universality problem is decidable for languages represented by tree automata with equality constraints, and that the equivalence and inclusion problems are decidable for images of regular tree languages through tree homomorphisms. our algorithms are based on the following constructions. we describe a simple transformation for converting a tree automaton with equality constraints into a tree automaton with inequality constraints recognizing the complementary language. we also define a new class of automata with arbitrary inequality constraints and a particular kind of equality constraints. an automaton of this new class essentially recognizes the intersection of a tree automaton with inequality constraints and the image of a regular tree language through a tree homomorphism. we prove decidability of emptiness and finiteness for this class by a pumping mechanism.
an optimal ancestry scheme and small universal posets. in this paper, we solve the ancestry problem, which was introduced more than twenty years ago by kannan et al. [stoc '88], and is among the most well-studied problems in the field of informative labeling schemes. specifically, we construct an ancestry labeling scheme for n-node trees with label size log2 n + o(log log n) bits, thus matching the log2 n + ω(log log n) bits lower bound given by alstrup et al. [soda '03]. besides its optimal label size, our scheme assigns the labels in linear time, and guarantees that any ancestry query can be answered in constant time. in addition to its potential impact in terms of improving the performances of xml search engines, our ancestry scheme is also useful in the context of partially ordered sets. specifically, for any fixed integer k, our scheme enables the construction of a universal poset of size o(nk log4k n) for the family of n-element posets with tree-dimension at most k. this bound is almost tight thanks to a lower bound of nk-o(1) due to alon and scheinerman [order '88].
spectral methods for matrices and tensors. while spectral methods have long been used for principal component analysis, this survey focusses on work over the last 15 years with three salient features: (i) spectral methods are useful not only for numerical problems, but also discrete optimization problems (constraint optimization problems - csp's) like the max. cut problem and similar mathematical considerations underlie both areas. (ii) spectral methods can be extended to tensors. the theory and algorithms for tensors are not as simple/clean as for matrices, but the survey describes methods for low-rank approximation which extend to tensors. these tensor approximations help us solve max-$r$-csp's for $r>2$ as well as numerical tensor problems. (iii) sampling on the fly plays a prominent role in these methods. a primary result is that for any matrix, a random submatrix of rows/columns picked with probabilities proportional to the squared lengths (of rows/columns), yields estimates of the singular values as well as an approximation to the whole matrix.
on the complexity of circuit satisfiability. in this paper, we are concerned with the exponential complexity of the circuit satisfiability (cktsat) problem and more generally with the exponential complexity of np-complete problems. over the past 15 years or so, researchers have obtained a number of exponential-time algorithms with improved running times for exactly solving a variety of np-complete problems. the improvements are typically in the form of better exponents compared to exhaustive search. our goal is to develop techniques to prove specific lower bounds on the exponents under plausible complexity assumptions. we consider natural, though restricted, algorithmic paradigms and prove upper bounds on the success probability. our approach has the advantage of clarifying the relative power of various algorithmic paradigms. our main technique is a success probability amplification technique, called the exponential amplification lemma, which shows that for any f(n,m)-size bounded probabilistic circuit family a that decides cktsat with success probability at least 2-α n for α-α2 n > 2-α n. in contrast, the standard method for boosting success probability by repeated trials will improve it to (1-(1-2-α n)t) (approx t2-α n for t=o(2α n)) using circuits of size about tf(n,m). using this lemma, we derive tight bounds on the exponent of the success probability for deciding the cktsat problem in a variety of probabilistic computational models under complexity assumptions. for example, we show that the success probability cannot be better than 2-n+o(n) for deciding cktsat by probabilistic polynomial size circuits unless cktsat (thereby all of np) for polynomial size instances can be decided by 2nμ size deterministic circuits for some μ -n+o(n) unless cktsat (as well as np) has o(mo(lg lg m)) size deterministic circuits, which is very close to the statement np ⊆ p/poly, an unlikely scenario.
faster approximation schemes for fractional multicommodity flow problems via dynamic graph algorithms. we combine the work of garg and konemann, and fleischer with ideas from dynamic graph algorithms to obtain faster (1-ε)-approximation schemes for various versions of the multicommodity flow problem. in particular, if ε is moderately small and the size of every number used in the input instance is polynomially bounded, the running times of our algorithms match -- up to poly-logarithmic factors and some provably optimal terms -- the ω(mn) flow-decomposition barrier for single-commodity flow.
augmenting undirected node-connectivity by one. we present a min-max formula for the problem of augmenting the node-connectivity of a graph by one and give a polynomial time algorithm for finding an optimal solution. we also solve the minimum cost version for node-induced cost functions.