Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take survey.

# Tag Info

Accepted

### Best query complexity of Goldreich-Levin / Kushilevitz-Mansour learning algorithm

The question seems somewhat under-specified in the sense that it did not specify the desired error probability of the procedure. Assuming one means constant error probability, then the above is indeed ...

### Approximating the sign rank of a matrix

Recent work by Alon, Moran, and Yehudayoff gives an $O(n/\log n)$ approximation algorithm. Let $d$ be the VC-dimension of a sign matrix $S$. The idea is that there exists an efficiently computable ...

• 2,743

### What is the VC Dimension of the $k-$Junta class

For the very limited situation in which $k=1$ and we're only interested in functions whose domain is $\{0,1\}^n$, the VC dimension is $\lfloor \log_2(n+1) + 1 \rfloor$. The upper bound follows ...
• 1,419
Accepted

### Complexity of finding a consistent hyperplane

Second version, hopefully correct. I claim that solving the feasibility problem $\exists? x: Ax \le b$ reduces in strongly polynomial time to finding a linear separator. Then it's easy to reduce ...

### Theoretical results for random forests?

I guess you already had a look at Breiman's 2001 paper about RF. I can just point out a few other references: Empirical comparisons of different RF simplifications that allow proving theorems: ...
• 186

### Learnability of constraint satisfaction problems CSPs?

You are probably looking for this paper: Víctor Dalmau and Peter Jeavons, Learnability of quantified formulas, TCS 306 485–511, 2003. doi:10.1016/S0304-3975(03)00342-6 In short, the learning ...
• 18.7k
Accepted

• 4,331
Accepted

### Oncina-Garcia RPNI algorithm for learning DFAs

The algorithm is named RPNI, not RNPI. Given that the language generating the inputs is regular and that enough examples are given (the characteristic set), the algorithm returns the canonical (i.e., ...
Accepted

### Is there an equivalent to VC-dimension for density estimation as opposed to classification?

For distributions with finite support of size $d$, when the error metric is the $\ell_1$ distance, the analogue of VC dimension is exactly $d$. (In fact, it's pretty much the VC dimension -- since to ...
• 10k

### Property testing in other metrics?

The work of Berman, Raskhodnikova, and Yaroslavtsev [1] introduces testing of functions $f\colon [n]^d\to \mathbb{R}$ with regard to $L_p$ distances, for $p\geq 1$. It is meant to capture situations ...
• 4,331

### Minimizing residual finite state automata

Let the "DFA $\to$ NFA" problem denote the following: Given a DFA $A$ and an integer $k$, is there an NFA with at most $k$ states equivalent to $A$? Similarly, let "DFA $\to$ RFSA" denote the problem ...
• 5,424
If your function is $f:\mathbb{R}\to\mathbb{R}$, you can "learn" $f'$ as a standard regression problem (linear, polynomial, etc.) and then recover $f$ up to an additive constant by integrating $f'$. ...