Hansen, Kaplan, Zamir and Zwick (STOC 2019) introduced a systematic way to use “bias” for predicting an assignment to a Boolean variable in the process of PPSZ and showed that their biased PPSZ algorithm achieves a relatively large success probability improvement of PPSZ for Unique 3SAT. We propose an additional way to use “bias” and show by numerical analysis that the improvement gets increased further.

The Global Position System (GPS), which is well known as a global tool for positioning, is also the primary system for time transfer. GPS can deliver very precise time to every corner of the world. Usually, a GPS receiver indicates the precise time by means of the 1PPS (one pulse per second) signal. This paper studies the precise time transfer system structure of GPS receivers and then proposes an effective PPS signal generation method with predictive synchronous loop, combining phase error prediction and dynamic threshold adjustment. A GPS time transfer system is implemented and measured in detail to demonstrate the validity of the proposed algorithm. Assuming the receiver clock rate of 16.368MHz, the proposed method can achieve the accuracy of ±20ns in the scope 1δ which can meet the requirements of the vast majority of occasions. Through a long period of testing, we prove the feasibility of this algorithm experimentally.

A systematic method for connection-wise end-to-end delay analysis in asynchronous transfer mode (ATM) networks is proposed. This method consists of the followings: (i) per-stream nodal analysis; (ii) output processes characterization; and (iii) moment matching scheme. Following our previous work, we employ H-MMPPs/Slotted D/1 to model ATM queues. Each virtual connection (VC) in ATM networks can be regarded as a tandem configuration of such queues. In [1], the per-stream analytical results for such an H-MMPPs/Slotted D/1 queue have been provided. In this paper, not only the composite output process is exactly characterized, but also the component in an output process that corresponds to a specific traffic stream is approximated via a decomposition scheme. A moment matching scheme to emulate the per-stream output process as a two-state MMPP is further proposed. Through moment matching, we can then approximate the connection-wise end-to-end delay by recursively performing the nodal performance analysis. The connection-wise end-to-end delay is crucial to network resource decision or control problems such as call admission control (CAC) and routing.

A family of new generalized LR parsing algorithms are proposed which make use of a set of ancestors tables introduced by Kipps. As Kipps's algorithm does not give us a method to extract any parsing results, his algorithm is not considered as a practical parser but as a recognizer. In this paper, we will propose two methods to extract all parse trees from a set of ancestors tables in the top vertices of a graph-structured stack. For an input sentence of length n, while the time complexity of the Tomita parser can exceed O(n3) for some context-free grammars (CFGs), the time complexity of our parser is O(n3) for any CFGs, since our algorithm is based on the Kipps's recognizer. In order to extract a parse tree from a set of ancestors tables, it takes time in order n2. Some preliminary experimental results are given to show the efficiency of our parsers over Tomita parser.