Search Results

The traditional art gallery problem sets up a region and guards with some notion of visibility, and asks for the minimum number of guards that need to be placed to see the entire region. Has anyone e …

It's well known that if you throw n balls into n bins, the most loaded bin is highly likely to have $O(\log n)$ balls in it. In general, one can ask about $m > n$ balls in $n$ bins. A paper from RANDO …

I'm wondering if there are good references that describe the random restriction method as a lower bound technique ? I'm aware that it's linked to the switching lemma and shows up in many different pro …

Is there a good survey that compares different extractors, concentrators and superconcentrators and lays out the best methods in terms of the tradeoff between randomness, time and space ?

If you're given a collection of partial orders, topological sort will tell you if there's an extension of the collection to a total order (an extension in this case is a total order consistent with ea …

When I teach tail bounds, I use the usual progression: If your r.v is positive, you can apply Markov's inequality If you have independence and also bounded variance, you can apply Chebyshev's inequ …

Suppose we're given a graph $G$ and parameters $k,\epsilon$. Are there ranges of values for $k$ (or is it doable for all $k$) for which it is possible to test whether $G$ is $\epsilon$-far from having …

The fat shattering dimension generalizes the notion of VC-dimension to handle function classes where the range is $(0,1)$, instead of $\{0,1\}$. Fat shattering dimension plays the same role as VC-dime …

Since it's Friday, it's time for a CW question. I'm looking for heuristics that have wide use in optimization problems. To limit the scope to more 'theory-friendly' heuristics, here are the rules (som …

I'm preparing some course material on heuristics for optimization, and have been looking at coordinate descent methods. The setting is here a multivariate function $f$ that you wish to optimize. $f$ h …

Branch and bound is an effective heuristic for search problems, and Wikipedia lists a number of hard problems where branch-and-bound has been used. However, I haven't been able to find references to s …

I'm trying to understand the relationship between graph isomorphism and the hidden subgroup problem. Is there a good reference for this ?

Since the term is overloaded, a brief definition first. A poset is a set $X$ endowed with a partial order $\le$. Given two elements $a,b \in X$, we can define $x \vee y$ (join) as their least upper bo …

I'm trying to understand the complexity of functions expressible via threshold gates and this led me to $\mathsf{TC}^0$. In particular, I'm interested what's currently known about learning inside $\ma …