Entropy of Operators or why Matrix Multiplication is Hard for Depth-Two Circuits

We consider unbounded fanin depth-2 circuits with arbitrary boolean functions as gates. We define the entropy of an operator f:{0,1} ⁿ →{0,1} ^m as the logarithm of the maximum number of vectors distinguishable by at least one special subfunction of f. Our main result is that every depth-2 circuit for f requires at least entropy(f) wires. This is reminiscent of a classical lower bound of Nechiporuk on the formula size, and gives an information-theoretic explanation of why some operators require many wires. We use this to prove a tight estimate Θ(n ³) of the smallest number of wires in any depth-2 circuit computing the product of two n by n matrices over any finite field. Previously known lower bound for this operator was Ω(n ²log n).     

Accumulation and Toxicity of Superparamagnetic Iron Oxide Nanoparticles in Cells and Experimental Animals

The uptake and distribution of negatively charged superparamagnetic iron oxide (Fe₃O₄) nanoparticles (SPIONs) in mouse embryonic fibroblasts NIH3T3, and magnetic resonance imaging (MRI) signal influenced by SPIONs injected into experimental animals, were visualized and investigated. Cellular uptake and distribution of the SPIONs in NIH3T3 after staining with Prussian Blue were investigated by a bright-field microscope equipped with digital color camera. SPIONs were localized in vesicles, mostly placed near the nucleus. Toxicity of SPION nanoparticles tested with cell viability assay (XTT) was estimated. The viability of NIH3T3 cells remains approximately 95% within 3–24 h of incubation, and only a slight decrease of viability was observed after 48 h of incubation. MRI studies on Wistar rats using a clinical 1.5 T MRI scanner were showing that SPIONs give a negative contrast in the MRI. The dynamic MRI measurements of the SPION clearance from the injection site shows that SPIONs slowly disappear from injection sites and only a low concentration of nanoparticles was completely eliminated within three weeks. No functionalized SPIONs accumulate in cells by endocytic mechanism, none accumulate in the nucleus, and none are toxic at a desirable concentration. Therefore, they could be used as a dual imaging agent: as contrast agents for MRI and for traditional optical biopsy by using Prussian Blue staining.     

Estimation of ambient temperature impact on vertical dynamic behaviour of passenger rail vehicle with damaged wheels

Maintenance and repair specialists of rolling stock face the problem related to accurate and reliable assessment of the vibrations of the car body of passenger rail vehicle, caused by wheel damage, and its impact on passengers. Another important aspect is to deter-mine the permissible speed at which the passenger car with wheel damage could move to the nearest station or depot without badly damaging the rails. The purpose of this research is to examine the dynamic processes of the interaction of the passenger car chassis with the railway track using a newly developed mathematical models called the “Passenger Car - Track” system. During the simulation, the dynamic characteristics of the track, bogies and car body in different season temperature were estimated. The validation of theoretical results was obtained based on the field tests of the test train as well as the results of measurements of changes in track stiffness temperatures. Finally, conclusions and suggestions are presented.     

On the minimum number of negations leading to super-polynomial savings

We show that an explicit sequence of monotone functions can be computed by Boolean circuits with polynomial (in n) number of And, Or and Not gates, but every such circuit must use at least logn−O(loglogn) Not gates. This is almost optimal because results of Markov [J. ACM 5 (1958) 331] and Fisher [Lecture Notes in Comput. Sci., Vol. 33, Springer, 1974, p. 71] imply that, with only small increase of the total number of gates, any circuit in n variables can be simulated by a circuit with at most ⌈log(n+1)⌉ Not gates.     

Yet harder knapsack problems

Already 30 years ago, Chvátal has shown that some instances of the zero-one knapsack problem cannot be solved in polynomial time using a particular type of branch-and-bound algorithms based on relaxations of linear programs together with some rudimentary cutting-plane arguments as bounding rules. We extend this result by proving an exponential lower bound in a more general class of branch-and-bound and dynamic programming algorithms which are allowed to use memoization and arbitrarily powerful bound rules to detect and remove subproblems leading to no optimal solution.     

Socially aware microcloud service overlay optimization in community networks

Community networks are a growing network cooperation effort by citizens to build and maintain Internet infrastructure in regions that are not available. Adding that, to bring cloud services to community networks (CNs), microclouds were started as an edge cloud computing model where members cooperate using resources. Therefore, enhancing routing for services in CNs is an attractive paradigm that benefits the infrastructure. The problem is the growing consumption of resources for disseminating messages in the CN environment. This is because the services that build their overlay networks are oblivious to the underlying workload patterns that arise from social cooperation in CNs. In this paper, we propose Select in Community Networks (SELECTinCN), which enhances the overlay creation for pub/sub systems over peer-to-peer (P2P) networks. Moreover, SELECTinCN includes social information based on cooperation within CNs by exploiting the social aspects of the community of practice. Our work organizes the peers in a ring topology and provides an adaptive P2P connection establishment algorithm, where each peer identifies the number of connections needed based on the social structure and user availability. This allows us to propagate messages using a reduced number of hops, thus providing an efficient heuristic to an NP-hard problem that maps the workload graph to the structured P2P overlays resulting in a number of messages close to the theoretical minimum. Experiments show that, by using social network information, SELECTinCN reduces the number of relay nodes by up to 89% using the community of practice information versus the state-of-the-art pub/sub notification systems given as baseline.     

On the P versus NP intersected with co-NP question in communication complexity

We consider the analog of the P versus NP∩co-NP question for the classical two-party communication protocols where polynomial time is replaced by poly-logarithmic communication: if both a boolean function f and its negation ¬f have small (poly-logarithmic in the number of variables) nondeterministic communication complexity, what is then its deterministic and/or probabilistic communication complexity? In the fixed (worst) partition model of communication this question was answered by Aho, Ullman and Yannakakis in 1983: here P=NP∩co-NP.We show that in the best partition model of communication the situation is entirely different: here P is a proper subset even of RP∩co-RP. This, in particular, resolves an open question raised by Papadimitriou and Sipser in 1982.     

Performance of direct-injection off-road diesel engine on rapeseed oil

This article presents the comparative bench testing results of a naturally aspirated, four stroke, four cylinder, water cooled, direct injection Diesel engine operating on Diesel fuel and cold pressed rapeseed oil. The purpose of this research is to study rapeseed oil flow through the fuelling system, the effect of oil as renewable fuel on a high speed Diesel engine performance efficiency and injector coking under various loading conditions.Test results show that when fuelling a fully loaded engine with rapeseed oil, the brake specific fuel consumption at the maximum torque and rated power is correspondingly higher by 12.2 and 12.8% than that for Diesel fuel. However, the brake thermal efficiency of both fuels does not differ greatly and its maximum values remain equal to 0.37–0.38 for Diesel fuel and 0.38–0.39 for rapeseed oil. The smoke opacity at a fully opened throttle for rapeseed oil is lower by about 27–35%, however, at the easy loads its characteristics can be affected by white coloured vapours.Oil heating to the temperature of 60 °C diminishes its viscosity to 19.5 mm² s⁻¹ ensuring a smooth oil flow through the fuel filter and reducing the brake specific energy consumption at light loads by 11.7–7.4%. Further heating to the temperature of 90 °C offers no advantages in terms of performance. Special tests conducted with modified fuel injection pump revealed that coking of the injector nozzles depends on the engine performance mode. The first and second injector nozzles that operated on pure oil were more coated by carbonaceous deposits than control injector nozzles that operated simultaneously on Diesel fuel.     

Fuzzynet: Ringless routing in a ring-like structured overlay

Many structured overlay networks rely on a ring invariant as a core network connectivity element. The responsibility ranges of the participating peers and navigability principles (greedy routing) heavily depend on the ring structure. For correctness guarantees, each node needs to eagerly maintain its immediate neighboring links - the ring invariant. However, the ring maintenance is an expensive task and it may not even be possible to maintain the ring invariant continuously under high churn, particularly as the network size grows. Furthermore, routing anomalies in the network, peers behind firewalls and Network Address Translators (NATs) create non-transitivity effects, which inevitably lead to the violation of the ring invariant. We argue that reliance on the ring structure is a serious impediment for real life deployment and scalability of structured overlays. In this paper we propose an overlay called Fuzzynet, which does not rely on the ring invariant, yet has all the functionalities of structured overlays. Fuzzynet takes the idea of lazy overlay maintenance further by dropping any explicit connectivity and data maintenance requirement, relying merely on the actions performed when new Fuzzynet peers join the network. We show that with sufficient amount of neighbors (O(log N), comparable to traditional structured over-lays), even under high churn, data can be retrieved in Fuzzynet w.h.p. We validate our novel design principles by simulations as well as PlanetLab experiments and compare them with ring based overlays.     

Expanders and time-restricted branching programs

The replication number   of a branching program is the minimum number R$R$ such that along every accepting computation at most R$R$ variables are tested more than once; the sets of variables re-tested along different computations may be different. For every branching program, this number lies between 0$0$ (read-once programs) and the total number n$n$ of variables (general branching programs). The best results so far were exponential lower bounds on the size of branching programs with R=o(n/logn)$R=o(n/logn)$. We improve this to R≤?n$R\le ?n$ for a constant ?>0$?>0$. This also gives an alternative and simpler proof of an exponential lower bound for (1+?)n$(1+?)n$ time branching programs for a constant ?>0$?>0$. We prove these lower bounds for quadratic functions of Ramanujan graphs.