The δ-Coin Problem is the problem of distinguishing between a sequence of coin tosses that come up Heads with probability either 1+δ/2 or 1−δ/2. The computational complexity of this problem in various models has been studied in many previous works with various applications related to derandomization, hierarchy theorems, cryptography and meta-complexity.

Technological interventions are becoming commonplace in everyday vehicles. But utilization of biosignals that can enhance the overall driving experience is still limited. Microsleep is one such issue that needs intervention, owing to the difficulty in its detection and social acceptance of using wearable BCI devices during transit. Microsleep is a short duration of sleep that lasts from few to several seconds. It could occur unconsciously without the person in context realizing it. This, therefore, happens before the deep sleep and could also occur when performing critical tasks such as driving on a highway. By using modern-day advancements in Internet of Things (IoT) and Machine Learning, we can provide efficient solutions to prevent accidents due to microsleep during vehicular transit. However, it is noteworthy that distinguishing microsleep using a single channel system is a challenge. We have explored this using datasets provided by International BCI Competition Committee. Given the fact that the participants’ values might not match the exact scenario, approaches for exploiting transitory phases using ANN/CNN have been developed and discussed in this paper. Transitory phases could include Wakefulness$\leftrightarrow $Non-Rapid Eye Movement-1 phase (NREM-1). Results show ≈95% increase in mean statistical agreements, which are represented by kappa values (CNN NREM$1~\rightarrow $CNN Transition) and ≈77% increase in mean kappa (ANN NREM$1~\rightarrow $ANN Transition). Hence, this work gives an initial indication whether classifiers trained on night sleep data can be used for microsleep detection in more real-world scenarios.

In this paper, we prove the first fixed-depth size-hierarchy theorem for uniform ${\mathrm{AC}}^0[\oplus]$. In particular, we show that for any fixed $d$ and integer parameter $k$, the class ${\mathcal{{C}}}_{d,k}$ of functions that have uniform ${\mathrm{AC}}^0[\oplus]$ formulas of depth $d$ and size $n^k$ form an infinite hierarchy. We show this by exhibiting the first class of functions that have uniform ${\mathrm{AC}}^0[\oplus]$ formulas of size $n^k$ but no ${\mathrm{AC}}^0[\oplus]$ formulas of size less than $n^{\varepsilon_0 k}$ for some absolute constant $\varepsilon_0 > 0$. The uniform formulas are designed to solve the $\delta$-coin problem, which is the computational problem of distinguishing between coins that are heads with probability $(1+\delta)/2$ or $(1-\delta)/2,$ where $\delta$ is a parameter that is going to $0$. We study the complexity of this problem and make progress on both upper bound and lower bound fronts. Regarding Upper bounds, for any constant $d\geq 2$, we show that there are uniform monotone ${\mathrm{AC}}^0$ formulas (i.e., made up of AND and OR gates only) solving the $\delta$-coin problem that have depth $d$, size $\exp(O(d\cdot(1/\delta)^{1/(d-1)}))$, and sample complexity (i.e., number of inputs) ${\mathop{\mathrm{poly}}}(1/\delta).$ This matches previous upper bounds of O'Donnell and Wimmer [ICALP 2007: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 4596, Springer, New York, 2007, pp. 195--206] and Amano [ICALP 2009: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 5555, Springer, New York, 2009, pp. 59--70] in terms of size (which is optimal), while improving the sample complexity from $\exp(O(d\cdot(1/\delta)^{1/(d-1)}))$ to ${\mathop{\mathrm{poly}}}(1/\delta)$. The improved sample complexity is crucial for proving the size-hierarchy theorem. Regarding Lower bounds, we show that the preceding upper bounds are nearly tight (in terms of size) even for the significantly stronger model of ${\mathrm{AC}}^0[\oplus]$ formulas (which are also allowed NOT and Parity gates): formally, we show that any ${\mathrm{AC}}^0[\oplus]$ formula solving the $\delta$-coin problem must have size $\exp(\Omega(d\cdot(1/\delta)^{1/(d-1)})).$ This strengthens a result of Shaltiel and Viola [SIAM J. Comput., 39 (2010), pp. 3122--3154], who prove an $\exp(\Omega((1/\delta)^{1/(d+2)}))$ lower bound for ${\mathrm{AC}}^0[\oplus]$ circuits, and a result of Cohen, Ganor, and Raz [APPROX-RANDOM, LIPIcs. Leibniz Int. Proc. Inform. 28, Schloss Dagstuhl, Leibniz-Zentrum fuer Informatik, Wadern, 2014, pp. 618--629], who show an $\exp(\Omega((1/\delta)^{1/(d-1)}))$ lower bound for ${\mathrm{AC}}^0$ circuits. The upper bound is a derandomization involving a use of Janson's inequality and an extension of classical polynomial-based combinatorial designs. For the lower bound, we prove an optimal (up to a constant factor) degree lower bound for multivariate polynomials over ${\mathbb{F}}_2$ solving the $\delta$-coin problem, which may be of independent interest.

The probabilistic degree of a Boolean function $f:\{0,1\}^n\rightarrow \{0,1\}$ is defined to be the smallest $d$ such that there is a random polynomial ${P}$ of degree at most $d$ that agrees with $f$ at each point with high probability. Introduced by Razborov [ Mat. Zametki, 41 (1987), pp. 598--607], upper and lower bounds on probabilistic degrees of Boolean functions---specifically symmetric Boolean functions---have been used to prove explicit lower bounds, design pseudorandom generators, and devise algorithms for combinatorial problems. In this paper, we characterize the probabilistic degrees of all symmetric Boolean functions up to polylogarithmic factors over all fields of fixed characteristic (positive or zero).

In this paper we prove two results about AC^0[oplus] circuits. (1) We show that for d(N) = o(sqrt(log N/log log N)) and N <= s(N) <= 2^(dN^(1/4d^2)) there is an explicit family of functions {f_N:{0,1}^N - > {0,1}} such that - f_N has uniform AC^0 formulas of depth d and size at most s; - f_N does not have AC^0[oplus] formulas of depth d and size s^epsilon, where epsilon is a fixed absolute constant. This gives a quantitative improvement on the recent result of Limaye, Srinivasan, Sreenivasaiah, Tripathi, and Venkitesh, (STOC, 2019), which proved a similar Fixed-Depth Size-Hierarchy theorem but for d << log log N and s << exp(N^(1/2^Omega(d))). As in the previous result, we use the Coin Problem to prove our hierarchy theorem. Our main technical result is the construction of uniform size-optimal formulas for solving the coin problem with improved sample complexity (1/delta)^O(d) (down from (1/delta)^(2^O(d)) in the previous result). (2) In our second result, we show that randomness buys depth in the AC^0[oplus] setting. Formally, we show that for any fixed constant d >= 2, there is a family of Boolean functions that has polynomial-sized randomized uniform AC^0 circuits of depth d but no polynomial-sized (deterministic) AC^0[oplus] circuits of depth d. Previously Viola (Computational Complexity, 2014) showed that an increase in depth (by at least 2) is essential to avoid superpolynomial blow-up while derandomizing randomized AC^0 circuits. We show that an increase in depth (by at least 1) is essential even for AC^0[oplus]. As in Viola’s result, the separating examples are promise variants of the Majority function on N inputs that accept inputs of weight at least N/2 + N/(log N)^(d-1) and reject inputs of weight at most N/2 - N/(log N)^(d-1).

In this work we prove the first Fixed-depth Size-Hierarchy Theorem for uniform AC0[⊕]. In particular, we show that for any fixed d, the class Cd,k of functions that have uniform AC0[⊕] formulas of depth d and size nk form an infinite hierarchy. We show this by exhibiting the first class of explicit functions where we have nearly (up to a polynomial factor) matching upper and lower bounds for the class of AC0[⊕] formulas.