The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
A random sampling function Sample: U → {0, 1} for a key universe U is a distinguisher with probability. If for any given assignment of values v(x) to the keys x ε U, including at least one non-zero v(x) ≠ 0, the sampled sum ∑{v(x)|x ε U ^. Sample(x) = 1} is non-zero with probability at least Α...
The Lovasz Local Lemma is a seminal result in probabilistic combinatorics. It gives a sufficient condition on a probability space and a collection of events for the existence of an outcome that simultaneously avoids all of those events. Finding such an outcome by an efficient algorithm has been an active research topic for decades. Breakthrough work of Moser and Tardos (2009) presented an efficient...
Smoothing properties of the noise operator on the discrete cube and on Gaussian space have played a pivotal role in many fields. In particular, these smoothing effects have seena broad range of applications in theoretical computer science. We exhibit new regularization properties of the noise operator on Gaussian space. More specifically, we show that the mass on level sets of a probability density...
A set function on a ground set of size n is approximately modular if it satisfies every modularity requirement to within an additive error, approximate modularity is the set analog of approximate linearity. In this paper we study how close, in additive error, can approximately modular functions be to truly modular functions. We first obtain a polynomial time algorithm that makes O(n2 log n) queries...
During the last decade, the matroid secretary problem (MSP) became one of the most prominent classes of online selection problems. The interest in MSP is twofold: on the one hand, there are many interesting applications of MSP, and on the other hand, there is strong hope that MSP admits O(1)-competitive algorithms, which is the claim of the well-known matroid secretary conjecture. Partially linked...
We describe a fully dynamic linear-space data structure for point location in connected planar subdivisions, or more generally vertical ray shooting among non-intersecting line segments, that supports queries in O(logn(loglogn)2) time and updates in O(log n log log n) time. This is the first data structure that achieves close to logarithmic query and update time simultaneously, ignoring log log n...
The algorithmic tasks of computing the Hamming distance between a given pattern P of length m and each location in a text T of length n is one of the most fundamental algorithmic tasks in string algorithms. Karloff [IPL 1999] showed that if one is willing to suffer a 1+ε approximation, then it is possible to solve the problem with high probability, in Õ(n/ε2) time. Due...
In recent years, a number of works have studied methods for computing the Fourier transform in sub linear time if the output is sparse. Most of these have focused on the discrete setting, even though in many applications the input signal is continuous and naive discretization significantly worsens the sparsity level. We present an algorithm for robustly computing sparse Fourier transforms in the continuous...
We consider the problem of estimating the number of triangles in a graph. This problem has been extensively studied in both theory and practice, but all existing algorithms read the entire graph. In this work we design a sub linear-time algorithm for approximating the number of triangles in a graph, where the algorithm is given query access to the graph. The allowed queries are degree queries, vertex-pair...
In the subspace approximation problem, we seek a k-dimensional subspace F of Rd that minimizes the sum of p-th powers of Euclidean distances to a given set of n points a1, an ε Rd, for p ≥ 1. More generally than minimizing Σi dist(ai, F)p, we may wish to minimize Σi M(dist(ai, F)) for some loss function M(), for example, M-Estimators, which...
Independent component analysis (ICA) is the problem of efficiently recovering a matrix A ∈ Rn×n from i.i.d. Observations of X=AS where S ∈ Rn is a random vector with mutually independent coordinates. This problem has been intensively studied, but all existing efficient algorithms with provable guarantees require that the coordinates Si have finite fourth moments. We consider...
We study the satisfiability of ordering constraint satisfaction problems (CSPs) above average. We prove the conjecture of Gutin, van Iersel, Mnich, and Yeo that the satisfiability above average of ordering CSPs of arity k is fixed-parameter tractable for every k. Previously, this was only known for k=2 and k=3. We also generalize this result to more general classes of CSPs, including CSPs with predicates...
We present a new approach to constructing unconditional pseudorandom generators against classes of functions that involve computing a linear function of the inputs. We give an explicit construction of a pseudorandom generator that fools the discrete Fourier transforms of linear functions with seed-length that is nearly logarithmic (up to polyloglog factors) in the input size and the desired error...
We prove that there exist bipartite Ramanujan graphs of every degree and every number of vertices. The proof is based on analyzing the expected characteristic polynomial of a union of random perfect matchings, and involves three ingredients: (1) a formula for the expected characteristic polynomial of the sum of a regular graph with a random permutation of another regular graph, (2) a proof that this...
We prove a complexity dichotomy for complex-weighted Holant problems with an arbitrary set of symmetric constraint functions on Boolean variables. In the study of counting complexity, such as #CSP, there are problems which are #P-hard over general graphs but P-time solvable over planar graphs. A recurring theme has been that a holographic reduction [Val08] to FKT precisely captures these problems...
A non-backtracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The non-backtracking matrix of a graph is indexed by its directed edges and can be used to count on-backtracking walks of a given length. It has been used recently in the context of community detection and has appeared previously in connection with the Ihara zeta function and in some generalizations...
Let X be a sparse random matrix of size n by p (p >> n). We prove that if p > C n log4 n, then with probability 1-o(1), |XT v|1 is close to its expectation for all vectors v in Rn (simultaneously). The bound on p is sharp up to the polylogarithmic factor. The study of this problem is directly motivated by an application. Let A be an n by n matrix, X be an n by p matrix and Y = AX. A challenging...
We pose and study a fundamental algorithmic problem which we term mixture selection, arising as a building block in a number of game-theoretic applications: Given a function g from the n-dimensional hypercube to the bounded interval [-1, 1], and an n × m matrix A with bounded entries, maximize g(Ax) over x in the m-dimensional simplex. This problem arises naturally when one seeks to design a lottery...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.