Hidden Hypergraphs,Error-Correcting Codes,and Critical Learning in Hopfield Networks

In 1943, McCulloch and Pitts introduced a discrete recurrent neural network as a model for computation in brains. The work inspired breakthroughs such as the first computer design and the theory of finite automata. We focus on learning in Hopfield networks, a special case with symmetric weights and fixed-point attractor dynamics. Specifically, we explore minimum energy flow (MEF) as a scalable convex objective for determining network parameters. We catalog various properties of MEF, such as biological plausibility, and then compare to classical approaches in the theory of learning. Trained Hopfield networks can perform unsupervised clustering and define novel error-correcting coding schemes. They also efficiently find hidden structures (cliques) in graph theory. We extend this known connection from graphs to hypergraphs and discover n-node networks with robust storage of 2Ω(n1−ϵ) memories for any ϵ>0. In the case of graphs, we also determine a critical ratio of training samples at which networks generalize completely.     

The Structure and First-Passage Properties of Generalized Weighted Koch Networks

Characterizing the topology and random walk of a random network is difficult because the connections in the network are uncertain. We propose a class of the generalized weighted Koch network by replacing the triangles in the traditional Koch network with a graph Rs according to probability 0≤p≤1 and assign weight to the network. Then, we determine the range of several indicators that can characterize the topological properties of generalized weighted Koch networks by examining the two models under extreme conditions, p=0 and p=1, including average degree, degree distribution, clustering coefficient, diameter, and average weighted shortest path. In addition, we give a lower bound on the average trapping time (ATT) in the trapping problem of generalized weighted Koch networks and also reveal the linear, super-linear, and sub-linear relationships between ATT and the number of nodes in the network.     

New Bounds and a Generalization for Share Conversion for 3-Server PIR

Private Information Retrieval (PIR) protocols, which allow the client to obtain data from servers without revealing its request, have many applications such as anonymous communication, media streaming, blockchain security, advertisement, etc. Multi-server PIR protocols, where the database is replicated among the non-colluding servers, provide high efficiency in the information-theoretic setting. Beimel et al. in CCC 12’ (further referred to as BIKO) put forward a paradigm for constructing multi-server PIR, capturing several previous constructions for k≥3 servers, as well as improving the best-known share complexity for 3-server PIR. A key component there is a share conversion scheme from corresponding linear three-party secret sharing schemes with respect to a certain type of “modified universal” relation. In a useful particular instantiation of the paradigm, they used a share conversion from (2,3)-CNF over Zm to three-additive sharing over Zpβ for primes p1,p2,p where p1≠p2 and m=p1·p2, and the relation is modified universal relation CSm. They reduced the question of the existence of the share conversion for a triple (p1,p2,p) to the (in)solvability of a certain linear system over Zp, and provided an efficient (in m,logp) construction of such a sharing scheme. Unfortunately, the size of the system is Θ(m2) which entails the infeasibility of a direct solution for big m’s in practice. Paskin-Cherniavsky and Schmerler in 2019 proved the existence of the conversion for the case of odd p1, p2 when p=p1, obtaining in this way infinitely many parameters for which the conversion exists, but also for infinitely many of them it remained open. In this work, using some algebraic techniques from the work of Paskin-Cherniavsky and Schmerler, we prove the existence of the conversion for even m’s in case p=2 (we computed β in this case) and the absence of the conversion for even m’s in case p>2. This does not improve the concrete efficiency of 3-server PIR; however, our result is promising in a broader context of constructing PIR through composition techniques with k≥3 servers, using the relation CSm where m has more than two prime divisors. Another our suggestion about 3-server PIR is that it’s possible to achieve a shorter server’s response using the relation CSm′ for extended Sm′⊃Sm. By computer search, in BIKO framework we found several such sets for small m’s which result in share conversion from (2,3)-CNF over Zm to 3-additive secret sharing over Zpβ′, where β′>0 is several times less than β, which implies several times shorter server’s response. We also suggest that such extended sets Sm′ can result in better PIR due to the potential existence of matching vector families with the higher Vapnik-Chervonenkis dimension.     

A Super Fast Algorithm for Estimating Sample Entropy

Sample entropy, an approximation of the Kolmogorov entropy, was proposed to characterize complexity of a time series, which is essentially defined as −log(B/A), where B denotes the number of matched template pairs with length m and A denotes the number of matched template pairs with m+1, for a predetermined positive integer m. It has been widely used to analyze physiological signals. As computing sample entropy is time consuming, the box-assisted, bucket-assisted, x-sort, assisted sliding box, and kd-tree-based algorithms were proposed to accelerate its computation. These algorithms require O(N2) or O(N2−1m+1) computational complexity, where N is the length of the time series analyzed. When N is big, the computational costs of these algorithms are large. We propose a super fast algorithm to estimate sample entropy based on Monte Carlo, with computational costs independent of N (the length of the time series) and the estimation converging to the exact sample entropy as the number of repeating experiments becomes large. The convergence rate of the algorithm is also established. Numerical experiments are performed for electrocardiogram time series, electroencephalogram time series, cardiac inter-beat time series, mechanical vibration signals (MVS), meteorological data (MD), and 1/f noise. Numerical results show that the proposed algorithm can gain 100–1000 times speedup compared to the kd-tree and assisted sliding box algorithms while providing satisfactory approximate accuracy.     

Mean Hitting Time for Random Walks on a Class of Sparse Networks

For random walks on a complex network, the configuration of a network that provides optimal or suboptimal navigation efficiency is meaningful research. It has been proven that a complete graph has the exact minimal mean hitting time, which grows linearly with the network order. In this paper, we present a class of sparse networks G(t) in view of a graphic operation, which have a similar dynamic process with the complete graph; however, their topological properties are different. We capture that G(t) has a remarkable scale-free nature that exists in most real networks and give the recursive relations of several related matrices for the studied network. According to the connections between random walks and electrical networks, three types of graph invariants are calculated, including regular Kirchhoff index, M-Kirchhoff index and A-Kirchhoff index. We derive the closed-form solutions for the mean hitting time of G(t), and our results show that the dominant scaling of which exhibits the same behavior as that of a complete graph. The result could be considered when designing networks with high navigation efficiency.     

Information and complexity measures in the interface of a metal and a superconductor

Fisher information, Shannon information entropy and Statistical Complexity are calculated for the interface of a normal metal and a superconductor, as a function of the temperature for several materials. The order parameter $\mathrm{\Psi }(\mathbf{r})$ derived from the Ginzburg–Landau theory is used as an input together with experimental values of critical transition temperature $T_c$ and the superconducting coherence length ${\xi }_0$. Analytical expressions are obtained for information and complexity measures. Thus $T_c$ is directly related in a simple way with disorder and complexity. An analytical relation is found of the Fisher Information with the energy profile of superconductivity i.e. the ratio of surface free energy and the bulk free energy. We verify that a simple relation holds between Shannon and Fisher information i.e. a decomposition of a global information quantity (Shannon) in terms of two local ones (Fisher information), previously derived and verified for atoms and molecules by Liu et al. Finally, we find analytical expressions for generalized information measures like the Tsallis entropy and Fisher information. We conclude that the proper value of the non-extensivity parameter $q?1$, in agreement with previous work using a different model, where $q?1.005$.     

A Satellite Incipient Fault Detection Method Based on Decomposed Kullback–Leibler Divergence

Detection of faults at the incipient stage is critical to improving the availability and continuity of satellite services. The application of a local optimum projection vector and the Kullback–Leibler (KL) divergence can improve the detection rate of incipient faults. However, this suffers from the problem of high time complexity. We propose decomposing the KL divergence in the original optimization model and applying the property of the generalized Rayleigh quotient to reduce time complexity. Additionally, we establish two distribution models for subfunctions F1(w) and F3(w) to detect the slight anomalous behavior of the mean and covariance. The effectiveness of the proposed method was verified through a numerical simulation case and a real satellite fault case. The results demonstrate the advantages of low computational complexity and high sensitivity to incipient faults.     

Exploring self-similarity of complex cellular networks: The edge-covering method with simulated annealing and log-periodic sampling

Song et al. [Self-similarity of complex networks, Nature 433 (2005) 392–395] have recently used a version of the box-counting method, called the node-covering method, to quantify the self-similar properties of 43 cellular networks: the minimal number _NV$N_V$ of boxes of size ?$?$ needed to cover all the nodes of a cellular network was found to scale as the power-law _NV∼(?+1)^-_DV$N_V\sim (?+1{)}^{-D_V}$ with a fractal dimension _DV=3.53±0.26$D_V=3.53\pm 0.26$. We implement an alternative box-counting method in terms of the minimum number _NE$N_E$ of edge-covering boxes which is well-suited to cellular networks, where the search over different covering sets is performed with the simulated annealing algorithm. The method also takes into account a possible discrete scale symmetry to optimize the sampling rate and minimize possible biases in the estimation of the fractal dimension. With this methodology, we find that _NE$N_E$ scales with respect to ?$?$ as a power-law _NE∼?^-_DE$N_E\sim {?}^{-D_E}$ with _DE=2.67±0.15$D_E=2.67\pm 0.15$ for the 43 cellular networks previously analyzed by Song et al. [Self-similarity of complex networks, Nature 433 (2005) 392–395]. Bootstrap tests suggest that the analyzed cellular networks may have a significant log-periodicity qualifying a discrete hierarchy with a scaling ratio close to 2.     

How entangled can a multi-party system possibly be?

The geometric measure of entanglement of a pure quantum state is defined to be its distance to the space of pure product (separable) states. Given an n-partite system composed of subsystems of dimensions $d_1,\dots ,d_n$, an upper bound for maximally allowable entanglement is derived in terms of geometric measure of entanglement. This upper bound is characterized exclusively by the dimensions $d_1,\dots ,d_n$ of composite subsystems. Numerous examples demonstrate that the upper bound appears to be reasonably tight.     

Critical sets of eigenfunctions of the Laplacian

We give an upper bound for the (n−1)$(n-1)$-dimensional Hausdorff measure of the critical set of eigenfunctions of the Laplacian on compact analytic n$n$-dimensional Riemannian manifolds. This is the analog of a result on the nodal set of eigenfunctions by H. Donnelly and C. Fefferman.     

Quantum Walk on the Generalized Birkhoff Polytope Graph

We study discrete-time quantum walks on generalized Birkhoff polytope graphs (GBPGs), which arise in the solution-set to certain transportation linear programming problems (TLPs). It is known that quantum walks mix at most quadratically faster than random walks on cycles, two-dimensional lattices, hypercubes, and bounded-degree graphs. In contrast, our numerical results show that it is possible to achieve a greater than quadratic quantum speedup for the mixing time on a subclass of GBPG (TLP with two consumers and m suppliers). We analyze two types of initial states. If the walker starts on a single node, the quantum mixing time does not depend on m, even though the graph diameter increases with it. To the best of our knowledge, this is the first example of its kind. If the walker is initially spread over a maximal clique, the quantum mixing time is O(m/ϵ), where ϵ is the threshold used in the mixing times. This result is better than the classical mixing time, which is O(m1.5/ϵ).     

Computational approaches to aspect-ratio-dependent upper bounds and heat flux in porous medium convection

Direct numerical simulation (DNS) has shown that Rayleigh–Bénard convection in a fluid-saturated porous medium self-organizes into narrowly spaced plumes at (ostensibly) asymptotically high values of the Rayleigh number Ra. In this Letter a combination of DNS and upper bound theory is used to investigate the dependence of the Nusselt number Nu on the domain aspect ratio L at large Ra  . A novel algorithm is introduced to solve the optimization problems arising from the upper bound analysis, allowing for the best available bounds to be extended up to Ra≈2.65×10⁴$\mathit{Ra}\approx 2.65\times {10}^4$. The dependence of the bounds on L(Ra)$L(\mathit{Ra})$ is explored and a “minimal flow unit” is identified.     

Learnability of the Boolean Innerproduct in Deep Neural Networks

In this paper, we study the learnability of the Boolean inner product by a systematic simulation study. The family of the Boolean inner product function is known to be representable by neural networks of threshold neurons of depth 3 with only 2n+1 units (n the input dimension)—whereas an exact representation by a depth 2 network cannot possibly be of polynomial size. This result can be seen as a strong argument for deep neural network architectures. In our study, we found that this depth 3 architecture of the Boolean inner product is difficult to train, much harder than the depth 2 network, at least for the small input size scenarios n≤16. Nonetheless, the accuracy of the deep architecture increased with the dimension of the input space to 94% on average, which means that multiple restarts are needed to find the compact depth 3 architecture. Replacing the fully connected first layer by a partially connected layer (a kind of convolutional layer sparsely connected with weight sharing) can significantly improve the learning performance up to 99% accuracy in simulations. Another way to improve the learnability of the compact depth 3 representation of the inner product could be achieved by adding just a few additional units into the first hidden layer.     

Quantum Statistical Complexity Measure as a Signaling of Correlation Transitions

We introduce a quantum version for the statistical complexity measure, in the context of quantum information theory, and use it as a signaling function of quantum order–disorder transitions. We discuss the possibility for such transitions to characterize interesting physical phenomena, as quantum phase transitions, or abrupt variations in correlation distributions. We apply our measure on two exactly solvable Hamiltonian models: the 1D-Quantum Ising Model (in the single-particle reduced state), and on Heisenberg XXZ spin-1/2 chain (in the two-particle reduced state). We analyze its behavior across quantum phase transitions for finite system sizes, as well as in the thermodynamic limit by using Bethe Ansatz technique.     

First Integrals of Shear-Free Fluids and Complexity

A single master equation governs the behaviour of shear-free neutral perfect fluid distributions arising in gravity theories. In this paper, we study the integrability of yxx=f(x)y2, find new solutions, and generate a new first integral. The first integral is subject to an integrability condition which is an integral equation which restricts the function f(x). We find that the integrability condition can be written as a third order differential equation whose solution can be expressed in terms of elementary functions and elliptic integrals. The solution of the integrability condition is generally given parametrically. A particular form of which corresponds to repeated roots of a cubic equation is given explicitly, which is a new result. Our investigation demonstrates that complexity of a self-gravitating shear-free fluid is related to the existence of a first integral, and this may be extendable to general matter distributions.     

Analytical Expressions for Ising Models on High Dimensional Lattices

We use an m-vicinity method to examine Ising models on hypercube lattices of high dimensions d≥3. This method is applicable for both short-range and long-range interactions. We introduce a small parameter, which determines whether the method can be used when calculating the free energy. When we account for interaction with the nearest neighbors only, the value of this parameter depends on the dimension of the lattice d. We obtain an expression for the critical temperature in terms of the interaction constants that is in a good agreement with the results of computer simulations. For d=5,6,7, our theoretical estimates match the numerical results both qualitatively and quantitatively. For d=3,4, our method is sufficiently accurate for the calculation of the critical temperatures; however, it predicts a finite jump of the heat capacity at the critical point. In the case of the three-dimensional lattice (d=3), this contradicts the commonly accepted ideas of the type of the singularity at the critical point. For the four-dimensional lattice (d=4), the character of the singularity is under current discussion. For the dimensions d=1, 2 the m-vicinity method is not applicable.     

Rigidity of noncompact complete Bach-flat manifolds

Let (M,g)$(M,g)$ be a noncompact complete Bach-flat manifold with positive Yamabe constant. We prove that (M,g)$(M,g)$ is flat if (M,g)$(M,g)$ has zero scalar curvature and sufficiently small _L2$L_2$ bound of curvature tensor. When (M,g)$(M,g)$ has nonconstant scalar curvature, we prove that (M,g)$(M,g)$ is conformal to the flat space if (M,g)$(M,g)$ has sufficiently small _L2$L_2$ bound of curvature tensor and _L4/3$L_{4/3}$ bound of scalar curvature.