Lower bounds for testing triangle-freeness in Boolean functions

Given a Boolean function , we say a triple (x, y, x + y) is a triangle in f if . A triangle-free function contains no triangle. If f differs from every triangle-free function on at least points, then f is said to be -far from triangle-free. In this work, we analyze the query complexity of testers that, with constant probability, distinguish triangle-free functions from those -far from triangle-free. Let the canonical tester for triangle-freeness denotes the algorithm that repeatedly picks x and y uniformly and independently at random from , queries f(x), f(y) and f(x + y), and checks whether f(x) = f(y) = f(x + y) = 1. Green showed that the canonical tester rejects functions -far from triangle-free with constant probability if its query complexity is a tower of 2's whose height is polynomial in . Fox later improved the height of the tower in Green's upper bound to . A trivial lower bound of on the query complexity is immediate. In this paper, we give the first non-trivial lower bound for the number of queries needed. We show that, for every small enough , there exists an integer such that for all there exists a function depending on all n variables which is -far from being triangle-free and requires queries for the canonical tester. We also show that the query complexity of any general (possibly adaptive) one-sided tester for triangle-freeness is at least square root of the query complexity of the corresponding canonical tester. Consequently, this means that any one-sided tester for triangle-freeness must make at least queries.

Airblast spray in crossflow - Structure, trajectory and droplet sizing

This study reports results of an experimental investigation of airblast spray of water and ethanol in crossflow. Laser shadowgraphy and Particle/Droplet Imaging Analysis (PDIA) are used to derive spray trajectory and drop size information while Particle Tracking Velocimetry (PTV) is used to measure droplet velocities. A new phenomenon of spray bifurcation is observed for low Gas to Liquid Ratio (GLR) cases. The reasons for the spatial bifurcation can be attributed to a combination of reasons. These are (a) presence of large ligaments and droplets in the near-nozzle region for low GLRs (b) secondary breakup experienced by ligaments/droplets leading to formation of a large number of small droplets, and (c) the crossflow causing differential dispersion of the small and large droplets. A novel correlation for spray trajectory is proposed incorporating the momentum ratio and liquid surface tension. This correlation is shown to be effective in predicting the non-linear spray trajectory over a large range of conditions for not only water but ethanol and Jet-A also. It is observed that the larger droplets penetrate further into the crossflow, in the direction of injection. Thus, with increase in height of the measurement location from the injection plane, the droplet Sauter Mean Diameter (SMD) is found to increase. Moreover, as the droplets travel downstream in the crossflow direction, the droplet SMD is observed to decrease. The effect of drag is assessed by comparing velocity of different sizes of droplets at various locations. Smaller droplets are entrained into the crossflow at much lower elevations, whereas larger droplets tend to penetrate further into the crossflow. (C) 2015 Elsevier Ltd. All rights reserved.

Wireless Aircraft Fuel Quantity Indication System

A wireless fuel quantity indication system (FQIS) has been developed using an RFID-enabled sensing platform. The system comprises a fully passive tag, modified reader protocol, capacitive fuel probe, and auxiliary antenna for additional energy harvesting. Results of fluid testing show sensitivity to changes in fluid height of less than 0.25in. An RF-DC harvesting circuit was developed, which delivers up to 5dBm of input power through a remote radio frequency (RF) source. Testing was conducted in a loaded reverberation chamber to emulate the fuel tank environment. Results demonstrate feasibility of the remote source to power the sensor with less than 1W of maximum transmit power and under 100ms dwell time (100mW average power) into the tank. This indicates adequate coverage for large transport aircraft at safe operating levels with a sample rate of up to 1 sample/s.