Theoretical Computer Science
dohmatob's user avatar
dohmatob's user avatar
dohmatob's user avatar
dohmatob
  • Member for 6 years, 8 months
  • Last seen more than a month ago
Profile Activity

10 Questions

Score Activity Newest Views
6 votes
1 answer
91 views

Generate cut $(A,B)$ in edge-colored graph $(V,E_1 \cup E_2)$ such that there are more red than white crossings, i.e $|E_1(A,B)| > |E_2(A,B)|$

4 votes
0 answers
104 views

Strong data-processing inequality: bound $TV(T_{\#}P_0,T_{\#}P_1)$ if $\|T(x)-x\|_\infty \le \varepsilon;\forall x \in \mathbb R^p$

3 votes
2 answers
160 views

Worst-case complexity of computing a certain non-standard dot product + algorithms realizing this complexity

3 votes
1 answer
147 views

Fast private computation of dot product

2 votes
1 answer
206 views

Upper bound for VCdim of $H$ in terms of subgraph$(F)$, where $H := \{S(f) | f \in F\}$, with $S(f) := \{(x,y) \in X \times \{\pm 1\} | yf(x) \le 1\}$

1 vote
0 answers
38 views

Remove cycles from a stochastic comparison matrix, while doing the least amount of editing

1 vote
0 answers
28 views

Generalization bound for margin / ramp loss which is not vacuous when margin tends to zero, but recovers usual generalization bound for 0-1 loss

0 votes
1 answer
197 views

Construction of a collection of subsets of $\{1,2,\ldots,n\}$ with certain properties

0 votes
0 answers
35 views

Let $C$ be collection of subsets of $[N]$. Given, $n\in [N]$, what's the terminology for $card\{s\subseteq [N]\mid n\not \in s,\, s \cup\{n\}\in C\}$?

0 votes
0 answers
31 views

Minimax computation for classification problems with smooth densities functions

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.