The function tag has no wiki summary.
0
votes
1answer
138 views
Newbie question: Meta-functions?
Consider a function F that takes a function and produces a function based on structure of the input function. As an example consider F that takes all functions having at least two conditionals and ...
8
votes
0answers
95 views
Can polynomial-sized circuits use garbage?
This is a non-uniform (and simplified) version of my previous question about Cook reductions. Let $R\subseteq \{0,1\}^*\times\{0,1\}$. A function $r\colon \{0,1\}^*\to\{0,1\}$ solves $R$ if ...
4
votes
1answer
112 views
Cook reduction for search problems, by universal property?
A search problem is a relation $R\subseteq \Sigma^*\times\Sigma^*$. A function $f\colon \Sigma^*\to\Sigma^*$ solves $R$ if $(x,f(x))\in R$ for all $x\in\Sigma^*$. Define a search problem to be ...
11
votes
1answer
419 views
Programming languages with canonical functions
Are there any (functional?) programming languages where all functions have a canonical form? That is, any two functions that return the same values for all set of input is represented in the same way, ...
6
votes
1answer
116 views
Combining (block)-sensitivity and Lipschitz conditions?
If we're given a boolean function $f : \{0,1\}^n \rightarrow \{0,1\}$, we can define its sensitivity as follows. The sensitivity $s(f, w)$ with respect to input $w$ is the number of ways of flipping a ...
5
votes
1answer
434 views
Universal Function approximation
It is known via the universal approximation theorem that a neural network with even a single hidden layer and an arbitrary activation function can approximate any continuous function.
What other ...
