Can a neural network with random connections still work correctly? Let's say we have a neural network with n layers where connections do not simply go from layer i to layer i+1, but can go from any layer i to any layer k such that k > i. For example; connections from layer 1 directly to layer 3, or layer 2 directly to layer n, etc...
Given an arbitrary training function and some chosen activation function for each layer, would such a neural network still work correctly?
 A: You can setup your weight connections which you want remove as $0$. For example you have 3-1 NN structure. Your weights for example:
$w_{11} = 1$
$w_{21} = 0$
$w_{31} = 1$
$w = [w_{11}, w_{21}, w_{31}]$
Input unit for example is:
$x = [0.5, 0.5, 0.5]$
First of all you try populate your data in network and check output result. (For easier computation we just get linear layer activator, but it still works for any other). So your output will be:
$output = linear(x w^{T}) = 0.5 * 1 + 0.5 * 0 + 0.5 * 1 = 1$
As you see, zero weight synapse just ignore contribution of input and in output neuron we calculate this connection as zero, so this is the same as we don't have this connection.
UPDATE:
So this is also works for weight update, but different algorithms can works in different way in weight updates. After one iteration you can update your zero weight and it will be non-zero. So in this case you can control your training for zero weights and update only non-zero.
A: You're effectively describing DenseNet-like architectures. The relevant paper is this one: Densely Connected Convolutional Networks - Huang, et. al..
The basic idea is to connect layer $i$ to all layers $k$ with $k>i$, by concatenating all incoming connections to layer $k$. While the complexity of the network grows quadratically with size, the paper demonstrates that the resulting architectures tend to be much more efficient than vanilla neural networks, requiring less overall neurons, and making considerable savings in terms of model size. In the above paper, comparable accuracy results on ImageNet are achieved with 10x less weights, compared to competing architectures like ResNet.  
This is because features from previous layers can now be recycled and reused in lower layers. Note that the above paper ends up using blocks of 4 layers, which are densely connected, so the resulting network isn't exactly fully dense. 
