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.
It is a long-standing problem to lower bound the performance of randomized greedy algorithms for maximum matching. Aronson, Dyer, Frieze and Suen studied the modified randomized greedy (MRG) algorithm and proved that it approximates the maximum matching within a factor of at least 1/2 + 1/400,000. They use heavy combinatorial methods in their analysis. We introduce a new technique we call Contrast...
Let be the maximal value such that the product of an matrix by an matrix can be computed with $n^{2+o(1)}$ arithmetic operations. In this paper we show that $\alpha>0.30298$, which improves the previous record by Coppersmith (Journal of Complexity, 1997). More generally, we construct a new algorithm for multiplying an matrix...
This paper proves that an """"old dog"""", namely -- the classical Johnson-Linden Strauss transform, """"performs new tricks"""" -- it gives a novel way of preserving differential privacy. We show that if we take two databases, D and D', such that (i) D'-D is a rank-1 matrix of bounded norm and (ii) all singular values...
Let be a set of points in $\R^d$. We present a linear-size data structure for answering range queries on with constant-complexity semi algebraic sets as ranges, in time close to $O(n^{1-1/d})$. It essentially matches the performance of similar structures for simplex range searching, and, for $d\ge 5$, significantly improves earlier solutions by the first two authors obtained in~1994. This almost...
We study several problems in which an unknown distribution over an unknown population of vectors needs to be recovered from partial or noisy samples, each of which nearly completely erases or obliterates the original vector. For example, consider a distribution p over a population V subset of or equal to {0, 1}n. A noisy sample v0 is obtained by choosing v according to p and flipping each coordinate...
For a set of n points in \Re^d, and parameters k and e, we present a data structure that answers (1 + e)-approximate k nearest neighbor queries in logarithmic time. Surprisingly, the space used by the data-structure is \wide tilde{O}(n/k), that is, the space used is sub linear in the input size if k is sufficiently large. Our approach provides a novel way to summarize geometric data, such that meaningful...
We develop a framework for proving approximation limits of polynomial-size linear programs from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any linear program as opposed to only programs generated by hierarchies. Using our framework, we prove that quadratic approximations for CLIQUE require linear...
The existence of a polynomial kernel for Odd Cycle Transversal was a notorious open problem in parameterized complexity. Recently, this was settled by the present authors (Kratsch and Wahlstr\"om, SODA 2012), with a randomized polynomial kernel for the problem, using matroid theory to encode flow questions over a set of terminals in size polynomial in the number of terminals (rather than the...
We introduce a new technique for designing fixed-parameter algorithms for cut problems, namely randomized contractions. With our framework: * We obtain the first FPT algorithm for the parameterized version of the UNIQUE LABEL COVER problem, with single exponential dependency on the size of the cutset and the size of the alphabet. As a consequence, we extend the set of the polynomial time solvable...
In the presence of a quantum adversary, there are two possible definitions of security for a pseudorandom function. The first, which we call standard-security, allows the adversary to be quantum, but requires queries to the function to be classical. The second, quantum-security, allows the adversary to query the function on a quantum superposition of inputs, thereby giving the adversary a superposition...
A distance sensitivity oracle is a data structure which, given two nodes s and t in a directed edge-weighted graph G and an edge e, returns the shortest length of an s-t path not containing e, a so called replacement path for the triple (s, t, e). Such oracles are used to quickly recover from edge failures. In this paper we consider the case of integer weights in the interval [-M, M], and present...
Motivated by an application in kidney exchange, we study the following query-commit problem: we are given the set of vertices of a non-bipartite graph G. The set of edges in this graph are not known ahead of time. We can query any pair of vertices to determine if they are adjacent. If the queried edge exists, we are committed to match the two endpoints. Our objective is to maximize the size of the...
The online matching problem has received significant attention in recent years because of its connections to allocation problems in Internet advertising, crowd-sourcing, etc. In these real-world applications, the typical goal is not to maximize the number of allocations, rather it is to maximize the number of successful allocations, where success of an allocation is governed by a stochastic process...
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.