New answers tagged randomized-algorithms
1
vote
Accepted
Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties
Here's an elaboration on my comment, assuming I didn't get lost in all the notation above:
For $\mathfrak{S}=\mathcal{P}([n])$, the power set of $[n]$, it holds that
\begin{equation*}
f_{\mathfrak{S}}(...
- 800
1
vote
Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity
Disclaimer. This is just to provide some details for Yuri's nice response to Q3, and generalize it to arbitrary group sizes.
Let $n=p_1 + \ldots + p_k$ be a partition of $n$ in to $k \ge 1$ positive ...
- 291
4
votes
Accepted
Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity
Let $z$ be the coordinate-wise product of $x$ and $y$; that is, $z_i = x_i y_i$ for all $i$. Then we need to compute $\sum_{S\in {\cal S}} z_S$.
Q1: We can solve the problem using dynamic programming. ...
- 3,899
Top 50 recent answers are included
Related Tags
randomized-algorithms × 206ds.algorithms × 52
cc.complexity-theory × 31
reference-request × 24
approximation-algorithms × 21
pr.probability × 20
randomness × 20
derandomization × 18
graph-theory × 12
graph-algorithms × 12
complexity-classes × 11
ds.data-structures × 11
linear-algebra × 8
circuit-complexity × 7
pseudorandomness × 7
random-walks × 7
lower-bounds × 6
matrices × 6
hash-function × 6
chernoff-bound × 6
optimization × 5
counting-complexity × 5
it.information-theory × 5
streaming-algorithms × 5
np-hardness × 4