For a large class of random constraint satisfaction problems (CSP), deep but non-rigorous theory from statistical physics predict the location of the sharp satisfiability transition. The works of Ding, Sly, Sun (2014, 2016) and Coja-Oghlan, Panagiotou (2014) established the satisfiability threshold for random regular $k$-NAE-SAT, random $k$-SAT, and random regular $k$-SAT for large enough $k\geq k_0$ where $k_0$ is a large non-explicit constant. Establishing the same for small values of $k\geq 3$ remains an important open problem in the study of random CSPs. In this work, we study two closely related models of random CSPs, namely the $2$-coloring on random $d$-regular $k$-uniform hypergraphs and the random $d$-regular $k$-NAE-SAT model. For every $k\geq 3$, we prove that there is an explicit $d_{\ast}(k)$ which gives a satisfiability upper bound for both of the models. Our upper bound $d_{\ast}(k)$ for $k\geq 3$ matches the prediction from statistical physics for the hypergraph $2$-coloring by Dall'Asta, Ramezanpour, Zecchina (2008), thus conjectured to be sharp. Moreover, $d_{\ast}(k)$ coincides with the satisfiability threshold of random regular $k$-NAE-SAT for large enough $k\geq k_0$ by Ding, Sly, Sun (2014).

The smoothness of human-smartphone interaction directly influences users experience and affects their purchase decisions. A commonly used method to improve user interaction of smartphones is to optimize the CPU scheduler. However, optimizing the CPU scheduler requires a modification of operating system. In addition, the improvement of the smoothness of human-smartphone interaction may be limited because the display subsystem is not optimized. Therefore, in this paper, we design a motion prediction queuing system, named MPQS, to improve the smoothness of human-smartphone interaction. For this, we use the information of vector, speed, movement, provided by the queuing mechanism of Android, to predict the movement of user-smartphone interaction. Based on the prediction, we then utilize available execution time between frames to perform image processing. We conducted a set of experiments on beagleboard-xM to evaluate the performance of MPQS. Our experiment results show that the proposed method can reduce the number of jank by up to 21.75%.

BitTorrent's built-in mechanism can effectively encourage peers to upload while they are downloading, but it lacks a mechanism to incentivize peers to continually upload to benefit others after they have completed downloading. As such, many private BitTorrent sites have enforced a {sharing ratio} on their members to demand the minimum amount a peer must upload with respect to the amount it has downloaded. In this paper we study how sharing ratio enforcement affects download time by addressing the following problem: {Given a flash crowd of peers downloading a file, what is the time required for the last peer to finish downloading?} We propose two models to estimate the download time. The first model is simpler in the sense that it does not need to know peers' actual download rates during the downloading process. However, it needs to assume that every peer can fully utilize its uplink capacity. This assumption may not hold when there are much more peers to upload than to download, a scenario that is not uncommon in a system with sharing ratio enforcement. The second model lifts the assumption by extending an existing model for estimating peers' actual download rates in a system with no sharing ratio enforcement. However, estimating peers' actual download rates becomes very complex when the number of peers of different bandwidths increases.