Akanksha Agrawal
email: akanksha.agrawal.2029@gmail.com

Arindam Biswas
email: arindam.b@ftml.net

Edouard Bonnet
email: edouard.bonnet@ens-lyon.fr

Nick Brettell
email: nbrettell@gmail.com

Radu Curticapean
email: radu.curticapean@gmail.com

Dániel Marx
email: dmarx@cs.bme.hu

Miltzow Tillmann

Venkatesh Raman
email: vraman@imsc.res.in

Saket Saurabh

Édouard Bonnet

Tillmann Miltzow
email: t.miltzow@googlemail.com

Parameterized Streaming Algorithms for Min-Ones d-SAT

Keywords: 2012 ACM Subject Classification Theory of computation → Streaming models, Theory of computation → Fixed parameter tractability, Theory min, ones, sat, d-sat, parameterized, kernelization, streaming, space, efficient, algorithm, parameter Digital Object Identifier 10.4230/LIPIcs.FSTTCS.2019.8

à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The satisfiability problem (SAT) is among most studied NP-complete problems and serves as the canonical problem for NP, being the first problem which was shown to be NP-complete [START_REF] Cook | The Complexity of Theorem-proving Procedures[END_REF][START_REF] Richard | Reducibility among combinatorial problems[END_REF]. It is an important problem in both theory and practice, and together with its variants, it appears in nearly every domain of Computer Science (see for example [START_REF] Du | Satisfiability problem: theory and applications: DIMACS Workshop[END_REF][START_REF] Fortnow | The Status of the P Versus NP Problem[END_REF][START_REF] Gong | A survey of SAT solver[END_REF][START_REF] Gu | Algorithms for the satisfiability (sat) problem[END_REF][START_REF] Stützle | A review of the literature on local search algorithms for MAX-SAT[END_REF]). Because of this, the problem has been studied in various paradigms such as classical Complexity Theory [START_REF] Arora | Computational complexity: a modern approach[END_REF], Approximation Algorithms [START_REF] David | Approximation algorithms for combinatorial problems[END_REF][START_REF] Yannakakis | On the approximation of maximum satisfiability[END_REF], Exact Algorithms [START_REF] Fedor | Exact Exponential Algorithms[END_REF][START_REF] Woeginger | Exact algorithms for NP-hard problems: A survey[END_REF], Parameterized Complexity [START_REF] Cygan | Parameterized algorithms[END_REF][START_REF] Szeider | On fixed-parameter tractable parameterizations of SAT[END_REF], and Heuristics [START_REF] Gong | A survey of SAT solver[END_REF].

A variant which frequently appears in the literature is d-SAT (d ≥ 1), where problem instances have at most d variables per clause. While d-SAT is NP-complete for d ≥ 3, 2-SAT is a classic example of a tractable, i.e. polynomial-time-solvable problem. In this work, we study an optimization version of d-SAT in the framework of parameterized streaming, which combines streaming algorithms and parameterized algorithms.

The streaming framework was formulated to study the behaviour of algorithms that process large amounts of data in a sequential manner. The input appears as a sequence of items and the assumption is that the amount of read-write memory available to the algorithm is very limited, typically logarithmic in the total size of the input. Because of this, the algorithm is unable to store the entirety of its input in memory, and since the input appears in a sequence, the algorithm does not have random access to the it. It may however make multiple passes over the input. The goal in the streaming framework is to process the input by making as few passes (ideally, just one) over it as possible while using as little memory as possible. The study of problems in this framework dates back to the 1980s [START_REF] Flajolet | Probabilistic counting[END_REF]28], although the framework was formally established only in 1996 [START_REF] Noga Alon | The Space Complexity of Approximating the Frequency Moments[END_REF][START_REF] Rauch Henzinger | Computing on data streams[END_REF]. The other player in the combined framework that we employ is Parameterized Complexity -an approach pioneered by Downey and Fellows [START_REF] Downey | Fundamentals of Parameterized complexity[END_REF]. For details on Parameterized Complexity, we refer the reader to the books of Downey and Fellows [START_REF] Downey | Fundamentals of Parameterized complexity[END_REF], Flum and Grohe [START_REF] Flum | Parameterized Complexity Theory[END_REF], Niedermeier [START_REF] Niedermeier | Invitation to fixed-parameter algorithms[END_REF], and the recent book of Cygan et al. [START_REF] Cygan | Parameterized algorithms[END_REF]. Appendix A provides a short introduction to the subject.

It should be noted here that the problem 2-SAT admits a polynomial-time algorithm [START_REF] Aspvall | A Linear-Time Algorithm for Testing the Truth of Certain Quantified Boolean Formulas[END_REF][START_REF] Even | On the complexity of timetable and multicommodity flow problems[END_REF][START_REF] Melven R Krom | The decision problem for a class of first-order formulas in which all disjunctions are binary[END_REF]. Its minimization version however, being a generalization of Vertex Cover is NP-hard [START_REF] Yannakakis | Node-and Edge-Deletion NP-Complete Problems[END_REF]. Indeed, the graph in a Vertex Cover instance can be seen as a formula in which the vertices are variables and each edge is a monotone clause containing the two endpoints as (positive) literals.

Fafianie and Kratsch [START_REF] Fafianie | Streaming Kernelization[END_REF] considered the question of kernelizing d-Hitting Set, d-Set Matching and Edge Dominating Set in the streaming model. Chitnis et al. [START_REF] Chitnis | Parameterized Streaming: Maximal Matching and Vertex Cover[END_REF] studied the problems Maximal Matching and Vertex Cover in the parameterized streaming model. The space used by these algorithms is O(f (k) log n), where k is the parameter, n is the size of the input, and f : N → N is a computable function.

The parameterized streaming model relaxes the space constraint of the usual streaming model to f (k) log n, and allows the algorithm to make at most g(k) passes over its input, where g : N → N is a (preferably slowly-growing) computable function. The goal now is to make as few passes over the input as possible, relative to the parameter. Under these new constraints, it is possible to construct streaming algorithms that have more refined space requirements, and we can also perform a more delicate analysis of the streaming complexity of the problem in question. Our results here illustrate this fact.

Our Results. In Section 2, we describe a parameterized streaming algorithm for Min-Ones d-SAT (d ≥ 2) that solves instances (F, k) using O (kd ck + k d ) log n (c > 0, a constant) bits of space and makes k + 1 passes. We then show that by carefully simulating the execution stack of the standard branching algorithm for Min-Ones d-SAT, a (d + 1) k -pass, O(k log n)space algorithm can be obtained. We believe that such an approach will be useful in the design of parameterized streaming algorithms for other problems as well. As an application, we show how the two algorithms can be used to solve IP 2 (a restricted Integer Programming problem) in the parameterized streaming model.

Section 3 describes a streaming kernelization for Min-Ones 2-SAT and an application of the algorithm to IP 2 . By making k + 2 passes over the input formula, it produces a kernel with O k 6 clauses while using O k 6 log n bits of space. It is known that for d ≥ 3, Min-Ones d-SAT does not admit a polynomial kernel [START_REF] Kratsch | Two Edge Modification Problems without Polynomial Kernels[END_REF] under certain (fairly reasonable) assumptions, ruling out a generalization of this result to larger values of d. Our algorithm also provides an alternative to the known kernelization [START_REF] Misra | Solving Min Ones 2-Sat as Fast as Vertex Cover[END_REF] for the problem, since it can also be executed in the less restrictive random-access machine (RAM) model.

We then exhibit various lower bounds in Section 4 to complement the positive results above. For d ≥ 2, we show that any k-pass streaming algorithm for Min-Ones-d-SAT requires Ω max n 1/k /2 k , log (n/k) bits of space in the worst case. This result is obtained by combining a well-known lower bound for the DISJ k [START_REF] Kushilevitz | Communication Complexity[END_REF] problem from Communication Complexity and a lower bound for the streaming problem POT Pointer Chasing [START_REF] Guha | Tight Lower Bounds for Multi-Pass Stream Computation Via Pass Elimination[END_REF]. This (unconditional) lower bound implies, among other things, that the k + 1 pass Min-Ones d-SAT (d ≥ 2) algorithm of section 2 is pass-optimal.

The next result in the section shows that even for d = 1, any 1-pass algorithm for Min-Ones d-SAT requires space Ω(n). This is in contrast to the results of Fafianie and Kratsch [START_REF] Fafianie | Streaming Kernelization[END_REF] and Chitnis et al. [START_REF] Chitnis | Parameterized Streaming: Maximal Matching and Vertex Cover[END_REF], who independently showed that there are 1-pass parameterized streaming algorithms for the Vertex Cover problem (a restriction of Min-Ones 2-SAT). Finally, we show that any p-pass algorithm for Min-Ones d-SAT (d ≥ 1), where p may be a function of both n and k, requires space O(n/p). Note 1.1. Although we do not provide an explicit accounting of the time used by our algorithms, it is not difficult to see that the streaming FPT algorithms all run in FPT time overall and the kernelizations, in polynomial time. [START_REF] Gusfield | A Bounded Approximation for the Minimum Cost 2-Sat Problem[END_REF], who gave a polynomial-time 2-approximation algorithm for the problem. Misra et al. [START_REF] Misra | Solving Min Ones 2-Sat as Fast as Vertex Cover[END_REF] exhibited an equivalence between Min-Ones-2 AT and Vertex-Cover via a polynomialtime parameter-preserving reduction. Fafianie and Kratsch [START_REF] Fafianie | Streaming Kernelization[END_REF], and Chitnis et al. [START_REF] Chitnis | Parameterized Streaming: Maximal Matching and Vertex Cover[END_REF] showed that Vertex Cover admits a single-pass, O k 2 -space algorithm. As noted earlier, Min-Ones 2-SAT generalizes Vertex Cover. Analogously, Min-Ones d-SAT generalizes d-Hitting Set. The question of kernelizing d-Hitting-Set was studied by Abu-Khzam [START_REF] Faisal | Kernelization Algorithms for D-Hitting Set Problems[END_REF], and Fafianie and Kratsch [START_REF] Fafianie | Streaming Kernelization[END_REF], who gave a single-pass algorithm that produces a kernel with O k d sets.

F S T T C S

Preliminaries. Here we introduce some basic concepts and notation used in the rest of the paper. A conjunction (AND) of clauses is called a CNF formula. When each clause has at most d literals, it is called a d-CNF formula. An assignment for a CNF formula F over the variable set V is a subset S ⊆ V . The assignment satisfies a clause if there is a variable in S that appears unnegated in the clause or a variable in V \ S that appears negated in the clause. An assignment which satisfies all clauses in a formula is called a satisfying assignment for the formula.

Streaming FPT Algorithms

The main result of this section is an algorithm that solves instances (F, k) of Min-Ones d-SAT in k + 1 passes using space O (kd ck + k d ) log n (c > 0, a constant). We also describe how to simulate the execution of the standard branching algorithm for the problem to solve in instances in (d + 1) k passes using space O(k log n) (see Appendix B.1).

Using these algorithms as subroutines, we then show how IP 2 , a restricted version of the Integer Programming problem, where every constraint has at most two variables, can be solved in the parameterized streaming model (see Appendix D). The (k + 1)-pass algorithm begins by a making a single pass over the formula and obtains a set of minimal assignments for certain "essential" monotone clauses in the formula. In the next k -1 passes, these assignments are extended as much as possible using the implications appearing in the formula. Finally, the algorithm makes an additional pass to check if the formula as a whole is satisfied by one of the extended assignments.

Let (F, k) be an instance of Min-Ones 2-SAT on the variable set V = {x 1 , x 2 , . . . , x n }. The next result shows how a streaming kernelization for d-Hitting Set (defined below) can be used to enumerate minimal solutions for a certain hitting set problem. The following result follows from Observation 1, Theorem 1 and Lemma 7 of [START_REF] Fafianie | Streaming Kernelization[END_REF].

d-Hitting Set

Proposition 2.2.

There is a 1-pass streaming algorithm called Stream-HS for d-Hitting-Set, which given an instance I = (X , U, k) with u max as the maximum element of U , returns an (equivalent instance) We note that in item 1 of Proposition 2.2, the size of I can be bounded by O k d log k , by relabeling, but we want to preserve the exact variables, so we do not use relabeling.

I = (X , U ⊆ U, k) using O k d log
Next, we apply the algorithm Stream-HS of Proposition 2.2 to obtain a set, which we call a set of essential monotone clauses, C 1 , and the set S 1 of all minimal assignments (as sets of variables set to 1) for them of size at most k, as follows. Observation 2.4. S 1 is the set of all minimal satisfying assignments of size at most k for both F + and F + 1 .

Pass 1. For each monotone clause

C = (x 1 ∨x 2 ∨• • •∨x d ) (where d ≤ d) seen in the stream, pass the set {x 1 , x 2 , . . . , x d } to Stream-HS. Let I t = (X t , U t , k)
The next observation relates satisfying assignments to F and the family S 1 .

Observation 2.5 (♠). Let S be the set of all minimal satisfying assignments of size at most k for F. Then for each S ∈ S, there is S ∈ S 1 , such that S ⊆ S. Now we describe the next k -1 passes. The algorithm constructs a set S prm of prime partial assignments, which will be enough to resolve the instance. Initially, we set S prm = S 1 .

Pass (2 ≤ ≤ k). Consider a non-monotone clause

C = (x C 1 ∨ x C 2 • • • ∨ x C d1 ∨ ¬y C 1 ∨ ¬y C 2 ∨ . . . ¬y C d2 ) (where d 1 + d 2 ≤ d) seen in the stream. For each S ∈ S prm , such that {y C 1 , y C 2 , . . . y C d2 } ⊆ S and {x C 1 , x C 2 , . . . x C d1 } ∩ S = ∅ we do the following. If |S| = k, then remove S from S prm . Otherwise, |S| ≤ k -1. Let S prm = S prm , and for i ∈ [d 1 ], let S i = S ∪ {x C i }. Set S prm = (S prm \ {S}) ∪ {S i | i ∈ [d 1 ]}.
Clearly, Pass , where 2 ≤ ≤ k, on reading a clause C uses time O(|S 1 |dk). Moreover, it modifies the sets in S prm (increasing |S prm | by at most a factor of d), by either removing a set S ∈ S 1 completely, or adding one more element to S (when the size is less than k). The above procedure is executed only for k -1 passes. Thus, it always maintains that |S prm | ∈ O d O(k) (see Proposition 2.1) and each set in S prm has at most k elements (each representable by log n bits). Thus, the (total) space used by the algorithm is bounded by O

(k d + d O(k) )k log n .
For simplicity of description, we introduce the following notation. We set S 1 prm = S 1 and for each ∈ [k], we let S prm denote the the set S prm after the execution of Pass . We let ρ = (Q 1 , Q 2 , . . . , Q t ) be the sequence of non-monotone clauses in F, where the ordering is given by the order of their appearance in the stream. For ∈ [k] \ {1}, i ∈ [t], we let S prm (i) be the set S prm (after modification, if any) at Pass after reading the clause Q i . Furthermore, we let S prm (0) be the set S -1 prm . Next, we prove some results that will be useful in establishing the correctness of the algorithm. Lemma 2.6. Let S be the set of all minimal assignments for F of size at most k. For each ∈ [k] and S ∈ S, there is S ∈ S prm , such that S ⊆ S.

Proof. We prove this using induction on . The claim follows for = 1 from Observation 2.5. This forms the base case of our induction. Next, we assume that the claim holds for each ≤ z (for some 1 ≤ z ≤ k -1) and then we prove it for = z + 1. At the beginning of th pass when no non-monotone clause is read from the stream, we have for each S ∈ S, there is S ∈ S prm (0), such that S ⊆ S. This follows from the fact that S prm (0) = S -1 prm . Next, we assume that at Pass , the claim holds after reading the clause

Q i , for each i ≤ p, where p ∈ [t -1] ∪ {0}. Now we prove the claim for Q p+1 = (x p+1 1 ∨ x p+1 2 • • • ∨ x p+1 d1 ∨ ¬y p+1 1 ∨ ¬y p+1 2 ∨ . . . ¬y p+1 d2
). Consider S ∈ S and let Ŝ ∈ S prm (p), such that Ŝ ⊆ S. We will show that there is a set S ∈ S prm (p + 1), such that S ⊆ S. Let X = {x p+1

For i ∈ [d 1 ], let Ŝi = Ŝ ∪ {x p+1 i }. Recall that S prm (p + 1) = (S prm (p) \ { Ŝ}) ∪ { Ŝi | i ∈ [d 1 ]}.
From the above we can conclude that Ŝi * ⊆ S and Ŝi * ∈ S prm (p + 1). This concludes the proof.

Q = (x 1 ∨ x 2 • • • ∨ x d1 ∨ ¬y 1 ∨ ¬y 2 ∨ . . . ¬y d2 ), such that {y 1 , y 2 , . . . , y d2 } ⊆ S and {x 1 , x 2 , . . . , x d1 } ∩ S = ∅.
But we also encountered Q at ( -1)th pass, and S should have been modified/deleted, which is a contradiction. Lemma 2.8. Let S be the set of all assignments for F of size at most k. For every S ∈ S, there is S ∈ S prm , such that S ⊆ S and S satisfies every clause of F.

Proof. Consider S ∈ S and let S ∈ S prm = S k

prm be a set such that S ⊆ S. The existence of S is guaranteed by Lemma 2.6. We will show that S satisfies all the clauses of F. By the construction of S prm , there is a set Ŝ ∈ S 1 , such that Ŝ ⊆ S . Thus, S satisfies each monotone clause of F (see Proposition 2.1 and 2.

= (x 1 ∨ x 2 • • • ∨ x d1 ∨ ¬y 1 ∨ ¬y 2 ∨ . . . ¬y d2
) be a non-monotone clause in F which is not satisfied by S , and let X = {x 1 , x 2 , . . . , x d1 } and Y = {y 1 , y 2 , . . . , y d2 }. Since S does not satisfy C, we have Y ⊆ S and X ∩ S = ∅. Notice that Y ⊆ S as S ⊆ S. As S satisfies C, we have S ∩ X = ∅. This together with the fact that X ∩ S = ∅ implies that |S | ≤ k -1. We can assume that Ŝ = ∅, as S prm can be assumed to contain only non-empty sets, otherwise, ∅ is a solution to F. The above discussions together with Observation 2.7 and the fact that

|S | ≤ k -1, implies that S ∈ S k-1
prm (and we have S ∈ S k prm ). But then at the kth pass, we would have encountered C, and S would be replaced by d 1 many sets, namely S ∪ {x i }, for each i ∈ [d 1 ]. This concludes the proof.

In the (k + 1) th pass, the algorithm performs the following steps, whose correctness is established by the discussion above.

Pass k + 1. Consider a clause C seen in the stream. If there is S ∈ S prm , such that S does not satisfy C, then remove S from S prm . When the stream is over, if S prm = ∅, then return yes, and otherwise, return no.

We now have the following theorem.

Theorem 2.9.

Instances (F, k) of Min-Ones d-SAT (d ≥ 2) can be solved in k + 1 passes using space O (kd ck + k d ) log n (c > 0, a constant).
By carefully adapting the standard branching algorithm for Min-Ones-d-SAT, we obtain the following theorem. k passes using space O(k log n).

Using Theorem 2.9 and 2.10 we can obtain the following result for IP 2 , a restricted Integer Programming problem in which every constraint has at most 2 variables (see Appendix D for details).

Theorem 2.11 (♠). IP 2 admits algorithms that solve instances (P, k) in k + 1 passes using space O(f (k) log n) (f : N → N, a computable function), and in 3 k passes using space O(f (k) log n).

Streaming Kernelizations

In this section, we describe a kernelization for Min-Ones 2-SAT that makes k + 2 passes over instances (F, k) using space O k 6 log n and produces a kernel with O k 6 clauses. In the first pass, the algorithm computes a set of monotone clauses as in Section 2. Then over k more passes, for each variable x appearing in these clauses, the algorithm computes a set of variables which must be set to one if x is set to 1, and the implications that force this. In the last pass, it collects all anti-monotone clauses which only contain variables that also appear in the stored clauses. We now formally describe our algorithm. Let (F, k) be an instance of Min-Ones 2-SAT on n variables. In the first pass we apply the algorithm Stream-HS of Proposition 2.2 to obtain a set of monotone clauses, C 1 . That is, we do the following.

F S T T C S 2 0 1 9

Pass 1. Obtain a set C 1 of monotone clauses of F using the same procedure as the first pass of Section 2.

Let V be the set of variables appearing in F, V 1 be the set of variables appearing in C 1 . For each variable v ∈ V 1 , we maintain a set of variables P v and a set of clauses P v . Initially, P v = {v} and P v = ∅, for v ∈ V 1 . Now we are ready to describe our next k passes.

Pass . Consider a non-monotone clause C = (x ∨ ¬y) seen in the stream. For each v ∈ V 1 such that y ∈ P v , x / ∈ P v , C / ∈ P v , and |P v | ≤ k, add x and C to the sets P v and P v , respectively.

For v ∈ V 1 and ∈ [k + 1], by P v ( ) we denote the set P v at the end of pass (or at the beginning of pass + 1, when = 1). Furthermore, we let P = ∪ v∈V1 P v and P = ∪ v∈V1 P v .

Observation 3.1 (♠). Let i ∈ [k] and v ∈ V 1 , such that |P v (i)| = |P v (i + 1)|. For all ∈ {i, i + 1, . . . , k + 1}, we have |P v ( )| = |P v (i)|.
Lemma 3.2. Let S be an assignment which satisfies all clauses in P.

For each v ∈ V 1 ∩ S, we have P v ⊆ S.
Proof. Consider v ∈ V 1 ∩S and let ρ = (C 1 = (x 1 ∨¬y 1 ), C 2 = (x 2 ∨¬y 2 ), . . . , C t = (x t ∨¬y t )) be the order in which the clauses in P v were added. Note that P x = {x i | i ∈ [t]}. We will show by induction on the index i ∈ [t] that each x i ∈ S. Before reading C 1 , the only element in P v was v. As C 1 was added to P v , it must hold that y 1 = v. Since v ∈ S, and S satisfies each clause in P, S must contain x 1 . For the induction hypothesis, we suppose that for some p ∈ [t -1], we have {x i | i ∈ [p]} ⊆ S. We will now show that x p+1 ∈ S. Since C p+1 ∈ P v and C p+1 appears after C i in ρ, for each i ∈ [p], there exists z ∈ {x i | i ∈ [p]}, such that z = y p+1 . But since z ∈ S and S satisfies each clause in P, we have that x p+1 ∈ S.

Let F be the 2-CNF formula containing all the anti-monotone clauses of F and all the clauses in C 1 ∪ P.

Lemma 3.3. (F, k) is a YES instance of Min-Ones 2-SAT if and only if (F , k) is a YES instance of Min-Ones 2-SAT.
Proof. The forward direction follows from the fact that each clause in F is also a clause in F. In the backward direction, let S be a solution to Min-Ones 2-SAT in (F , k), and S = v∈V1∩S P v . We show that S is a solution to Min-Ones-2-SAT in (F, k). Since V 1 ∩ S ⊆ S , from Proposition 2.2 we have that S satisfies each monotone clause of F. From Lemma 3.2 we have S ⊆ S. Thus, S satisfies each anti-monotone clause of F (F contains all of them). If S satisfies each non-monotone clause of F, then the claim follows. Otherwise, we have a non-monotone clause C = (x ∨ ¬y) in F, which is not satisfied by S . We have that x / ∈ S and y ∈ S . Let

V y = {v ∈ V 1 | y ∈ P v }.
The construction of S implies that there is v * ∈ V y such that v * ∈ S. From the construction of S we have that x / ∈ P v * . The above discussions together with Observation 3.1 implies that we would have encountered C at a pass i ≤ k, and we did not add x to P v * . This means that |P v * | ≥ k + 1. But this contradicts the fact that S has size at most k (note that from Lemma 3.2 we have P v * ⊆ S).

Let V 2 = V 1 ∪ v∈V1 P v .
We will construct a set B of anti-monotone clauses. Initially, B = ∅. We now describe the (k + 2) th pass of our algorithm, which constructs the set B.

Pass k + 2. For each anti-monotone clause C = (¬x ∨ ¬y) in the stream with {x, y} ⊆ V 2 and C / ∈ B, add C to B. Then forget the sets P v , where v ∈ V 1 . Let F be the 2-CNF formula obtained from F by removing all anti-monotone clauses that are not in B.

Lower Bounds

We begin this section by exhibiting a reduction from the POT Pointer Chasing problem (defined later) to Min-Ones 2-SAT and use it to prove the following theorem. For some background on DISJ k and other problems (INDEX and DISJ) appearing in the proofs below, the reader is referred to Kushilevitz and Nisan's standard work on Communication Complexity [START_REF] Kushilevitz | Communication Complexity[END_REF].

Using the bound of Proposition 4.2, it is possible to prove the intuitively obvious notion that a streaming algorithm which needs to keep track of locations in its input must use space Ω(log n), where n is the size of its input. The process is repeated for as many passes as the algorithm requires over F S ∧ F T . Once the algorithm halts, Bob returns its output as his answer. 2) f( 3) f( 4) f( 5) f( 6) f( 7) f( 8) f( 9) f( 10) f( 11) f( 12) f( 13) Since MOdSSolve outputs YES if and only if (F S ∧ F T , k) is a YES instance, the protocol is valid. The amount of communication per pass between Alice and Bob is at most 2g(n, k), so the total amount of communication is at most 2pg(n, k). From Proposition 4.2, we have 2pg(n, k) = Ω log n k , i.e. g(n, k) = Ω (1/p) log n k .

F S T T C S

The above result shows an Ω(log n) lower bound on the space used by any algorithm that solves instances (F, k) of Min-Ones d-SAT in Ω(k) passes. This is quite weak, but it is possible to strengthen the result substantially using a lower bound for the following POT Pointer Chasing problem.

Consider a complete t-ary tree T with l + 1 levels rooted at the vertex r. Let the levels be numbered from 1 to l + 1, with the root being on level 1. For each non-leaf vertex v, define v i to be the i th child of v (in the lexicographic ordering of its children). Given a function f : V(T ) → {0, . . . , t -1}, define f * (v) = v f (v) for non-leaf vertices v and f * (v) = f (v) for leaf vertices. For i ∈ N, (f * ) i (r) denotes the result of applying f * to r repeatedly, i times.

POT Pointer Chasing

Instance: (T, f ), where T is a complete t-ary tree with l + 1 levels rooted at r, encoded as a post-order traversal of its vertices, and f : V(T ) → {0, . . . , t -1}. Question: Is (f * ) l (r) = 1?

Figure 1 shows an instance with parameters t = 3 and l = 2. The following result exhibits a tradeoff between the number of passes made by a streaming algorithm for POT Pointer Chasing and the space it requires. Proposition 4.4 (Guha and McGregor [18], Theorem 1). Any p-pass streaming algorithm that solves POT Pointer Chasing instances over t-ary trees with (p + 1) levels requires space Ω(t/2 p ) in the worst case. Proof. The tree T has levels 1, . . . , k + 1, with the root r on level 1 and the leaves on level k + 1. Since each internal vertex has t children,

|V (T )| = t k+1 -1 t-1 = O t k . Consider the following boolean formula F with n = t k -1 t-1 = Θ t k-1 variables.
Let w = f * (r), i.e. the f (r) th child of r, and T w be the subtree of T rooted at w. The variable set of

F is {x v | v ∈ V(T w )}. For each vertex v on level i = 2, . . . , k of T , F has the clause x v → x f * (v) ≡ ¬x v ∨ x f * (v) .
For each leaf vertex v, F has the clause ¬x v ∨ ¬x v if and only if f (v) = 0. In addition, F has the clause x w ∨ x w .

We now show that (F, k) is an equivalent instance of Min-Ones 2-SAT. Consider the leaf vertex z = (f * ) k (r), i.e. the vertex reached by chasing pointers from the root of T . If (T, f ) is a YES-instance, i.e. f (z) = 1, then F can be satisfied by setting k variables (corresponding to variables on the w-z path in T ) to 1, i.e. (F, k) is a YES instance. In the other case, i.e. f (z) = 0, F is unsatisfiable: F contains the clause x w ∨ x w , a chain of implications from w to z, and the clause ¬x z ∨ ¬x z , which cannot be satisfied simultaneously. Thus, (F, k) is a NO instance.

Observe that the implication x v → x f (v) can be produced by simply reading off the value f (v). This is because in the stream, the values of f appear as in the (lexicographic) post-order traversal of T , and knowing the value f (v) and the position of f (v) in the stream is enough to determine the f (v) th child of v. Thus, the clauses can be produced on the fly while making a pass over the post order traversal of T .

We now prove Theorem 4.1.

Proof. Let MOdSSolve be a k-pass streaming algorithm for Min-Ones 2-SAT that uses space g(n, k) on inputs (F, k) over n variables. Consider an algorithm that takes as input an instances (T, f ) of POT Pointer Chasing over trees with k + 1 levels, producing instances (F, k) (over n = Θ t k-1 variables) of Min-Ones 2-SAT on the fly as above, and feeding them as input to MOdSSolve. Because of Lemma 4.5, the output of A on (F, k) correctly decides (T, f ). The algorithm makes k passes over its input and the amount of space used overall is O(g(n, k) + log n). This value is Ω t/2 k , by Proposition 4.4. Since n = Θ t k , we have g(n, k) + log n = Ω n 1/k /2 k . Consider the case k ≥ √ log n. The expression n 1/k /2 k is o(1), so g(n, k) = Ω n 1/k /2 k holds trivially. In the other case, i.e. k < √ log n, we have g(n, k) = Ω(log n) by Lemma 4.3, so g(n, k)

+ log n = O(g(n, k)), i.e. g(n, k) = Ω n 1/k /2 k .
Observe that the bound g(n, k) = Ω log n k holds for any k ≤ n/2 (Lemma 4.3), and for k > n/2 , g(n, k) = Ω log n k holds trivially. Therefore, we have g

(n, k) = Ω max n 1/k /2 k , log n k . Suppose a streaming algorithm for Min-Ones 2-SAT uses space O f (k)n 1/k-( > 0, a constant) to decide instances (F, k) over n variables. Observe that lim n→∞ f (k)n 1/k- n 1/k /2 k = 0
for any function f . Thus, we have the following corollary. Corollary 4.6. Let > 0 be a number. Any streaming algorithm for Min-Ones 2-SAT that uses space O f (k)n 1/k-must make at least k + 1 passes over its input.

The preceding corollary shows that the algorithm of Theorem 2.9, which makes k + 1 passes over (F, k), is the best possible inasmuch as the number of passes is concerned. We now exhibit two lower bounds on the space complexity of Min-Ones 2-SAT using Communication Complexity similar to those in Lemma 4.

F = a[i]=1 ¬x i ∧ (x b ). (F, 1) is a NO instance if and only if a[b] = 1.
Suppose there is a 1-pass algorithm for Min-Ones d-SAT that uses space f (k)g(n) on n-variable inputs with parameter k. Alice runs the algorithm on a[i]=1 ¬x i and passes the algorithm's memory to Bob. Bob resumes executing the algorithm on the memory and feeds it the additional clause x b . Using the output of the algorithm, Bob can determine the value a [b].

It is known that any deterministic 1-pass protocol for INDEX requires Ω(n) bits of communication (Kushilevitz and Nisan [26], Example 4.19). Because Alice passes the algorithm's memory to Bob, the size of this memory must be Ω(n), i.e. f (1)g(n) = Ω(n). Thus, there are no 1-pass parameterized streaming algorithms for Min-Ones d-SAT (d ≥ 1) that use space O(f (k)g(n)) with g = o(n).

The above theorem shows that even in the case where every clause consists of exactly one literal, it is not possible to solve an instance of Min-Ones d-SAT in a single pass without using space Ω(n). Unlike Theorem 4.1, the next result holds in cases where p, the number of passes made by the algorithm, is a more general function of k.

Conclusion

In this work, we have proved a variety of results that together provide a complete picture of the parameterized streaming complexity of Min-Ones d-SAT. One of the main results is the streaming algorithm for Min-Ones d-SAT which solves instances (F, k) in (k + 1) passes using space O (kd ck + k d ) log n (c > 0, a constant). The matching (k + 1)-pass lower bound shows that in terms of the number of passes, this result is the best possible.

It is pertinent to note that such results, i.e. which show a sharp tradeoff between the space complexity of a parameterized streaming problem and the number of passes allowed, are quite scarce in the literature. It would be interesting to see which other parameterized streaming problems exhibit such behaviour.

Proof of Observation 2.5

Any minimal satisfying assignment S ∈ S is also a satisfying assignment for F + . From Observation 2.4 we know that S 1 is the set of all minimal satisfying assignments of size at most k for F + . Hence, it follows that there is S ∈ S 1 , such that S ⊆ S. Let (F, k) be an instance of Min-Ones-d-SAT. By S, we denote the stream of clauses in F. We give our (O d k , O(k))-streaming-FPT algorithm Stream-MOS, for Min-Ones-d-SAT algorithm in Algorithm 2. In the following, we describe various functions of the algorithm Stream-MOS. We note that each of the functions have access to the stream S and a global variable called pass-count.

The function FinishScan takes no input and returns no output (only updates pass-count).

Its goal is only to read the stream till the end and update pass-count, which stores the number of passes we have made through S. When we enter this function, the pass number is updated. If we are already at the end of the stream S, then it exits without doing any other operation. Otherwise, it read S till the end and exits. The purpose of defining this function (and maintaining pass-count) is to simplify the analysis of the algorithm. 2. The function TestSatisfiability takes as input a set S, and its objective is to determine whether or not S satisfies each clause of F. A call to TestSatisfiability, makes a complete scan through S and we explicitly ensure that whenever it is called, we are at the beginning of the stream. Whenever we find a clause unsatisfied by S in the stream, the function calls FinishScan to complete the scanning through remaining clauses of S and update pass-count, and then it exits after returning 0. In the case when there is no clause which is not satisfied by S, it makes a call to FinishScan to update pass-count, and exits after returning 1.

3.

The function FindBranchClause takes as input a set S. Its objective is to find a clause C which cannot be satisfied (by just) setting variables in S to 1. More precisely, it returns a clause C (if it exists) which satisfies two conditions (to be stated, shortly). Let X and Y be the sets of variables which appear positively and negatively in C, respectively. It must hold that Y ⊆ S and X ∩ S = ∅. Notice that for a satisfying assignment S for F, such that S ⊆ S , it must hold that S ∩ X = ∅. Moreover, as S ∩ X = ∅, S must contain at least one more vertex (from X), which is not present in S. We will later see how we use C to progress our branching procedure. To find C, FindBranchClause makes a complete scan through S. If it finds a clause C with the desired properties, it makes a call to FinishScan to complete the scan through S and update pass-count, and then it exits after returning C. If a clause with the desired properties is not found even when we reach the end of the stream S, it makes a call to FinishScan to update pass-count, and then exits after returning ♦ (indicating that a clause with the desired property could not be found). 4. The function DetectSolution takes as input a set S, and its objective is to determine whether or not there is a solution for (F, k) which sets each variable in S to 1. This function is defined because our algorithm is a recursive procedure, and as the algorithm progresses, we maintain a set of variables that have already been set to 1. We note that at any point of time we allocate memory only for one such set, and whenever we make calls to other functions, we send the memory location, instead of a separate copy of the set itself. At some steps we call other functions with a modified set (with an element added to S), in this case also we send the memory address after appending the new element (in the front). The above can be achieved by using appropriate memory pointers. Next, we describe the working of DetectSolution. If |S| > k, then it (correctly) return 0, indicating that there is no satisfying assignment of size at most k containing S. Hereafter, we assume that |S| ≤ k. Now the function checks if S is a satisfying assignment for F, by making a call to TestSatisfiability with (memory location of) S as the argument.

If TestSatisfiability(S) returns 1, then the function exits after (correctly) returning 1. Otherwise, it makes a call to FindBranchClause with (memory location of) S as the argument, and stores the output of it in C. Next, it considers the case when C = ♦. Let X and Y be the sets of variables appearing positively and negatively in C, respectively. By the properties of the clauses returned by FindBranchClause, we know that X ∩S = ∅ and Y ⊆ S. Thus, for any satisfying assignment S for F with S ⊆ S , S ∩ X = ∅ must hold. As X ∩ S = ∅, S must contain at least one vertex from X and this vertex does not belong to S. If |S| = k, then there cannot be a satisfying assignment of size at most k containing S, as otherwise, it will not satisfy C. Thus, in the above case, the function correctly returns 0, and exits. Next, the function deals with the case when |S| < k. For any x ∈ X, it checks if there is a satisfying assignment for F of size at most k containing S ∪ {x}. This is done by making a recursive call to DetectSolution with (the memory location of) S ∪ {x} as the argument. If for any x ∈ X, DetectSolution(S ∪ {x}) returns 1, then the function exits after (correctly) returning 1. If for no x ∈ X, DetectSolution(S ∪ {x}) returns 1, then the function exits after (correctly) returning 0. If none of the above statements could be used to return an answer, then the algorithm returns 0 and exits. 5. The function MainMOS is the main function of the algorithm, where the algorithm begins its execution. The objective of MainMOS is to return 1 if (F, k) is a yes-instance of Min-Ones-d-SAT and return 0, otherwise. Thus, we have only statement, namely, DetectSolution(∅) in this function. The correctness of this function follows from the correctness of DetectSolution.

Next, we state a lemma regarding Stream-MOS, which will be used to establish the main theorem of this section. Proof. The correctness of Stream-MOS is immediate from the correctness of each of its functions (which is apparent from their respective descriptions). We now bound the space used by the algorithm and the number of passes it makes over S. The space bounds follows from the facts that at any point of the time, we have at most O(k) active instances of DetectSolution and whenever we pass a set as an argument to a function, its memory is passed, rather than a copy of the set itself. To bound the number of passes that the algorithm makes over S, it is enough to bound pass-count. Recall that pass-count is updated only when TestSatisfiability or FindBranchClause is called by DetectSolution. In the above, the pass-count is updated by TestSatisfiability or FindBranchClause by making a call to FinishScan, which increments pass-count exactly by 1. Observe that the total number of (recursive) calls to TestSatisfiability or FindBranchClause, made by DetectSolution is bounded by O d k . Thus, pass-count is bounded by O d k . This concludes the proof.

The proof of Theorem 2.10 follows from Lemma B.1.

2 0 1 9 8: 4 Parameterized

 94 Streaming Algorithms for Min-Ones d-SAT Related Results. Min-Ones 2-SAT was first studied by Gusfield and Pitt

  Instance: (U, F, k), where F is a family of subsets of U of size at most d, and k ∈ N. Question: Is there a set S ⊆ U of size at most k such that S ∩ A = ∅ for all A ∈ F ? Proposition 2.1 (♠ 1 ). There is an algorithm Enum-d-HS, that finds the set S k , of all minimal d-hitting sets of size at most k, for an instance I = (X , U, k) of d-Hitting Set in time O d k |I| . Moreover, |S k | ∈ O d k and the algorithm uses space O k|I| + kd k b U , where |I| is the size of I and b U is maximum size of the elements of U in bits.

  be the output of Stream-HS once the entire stream has been read. Set C 1 = X t . Using Proposition 2.1, compute the set S 1 , of all minimal d-hitting sets of size at most k for I t . The next lemma bounds the time and the space used in Pass 1. Lemma 2.3 (♠). Pass 1 uses space O (k d + d k )k log n and time O d k k d log n after reading each clause from the stream. Let C + be the set of all monotone clauses of F, let F + = ∧ C∈C + C and F + 1 = ∧ C∈C1 C. Recall that C 1 is the set of clauses computed in Pass 1. We have the following observation, which follows from Proposition 2.1 and item 3 of Proposition 2.2.

1 , x p+1 2 , 1 , y p+1 2 , 1 , x p+1 2 ,

 121212 . . . , x p+1 d1 } and Y = {y p+1 . . . , y p+1 d2 }. If Y ⊆ Ŝ or X ∩ Ŝ = ∅, then Ŝ ∈ S prm (p + 1). Hence, S = Ŝ is a set such that S ⊆ S. Otherwise, we have Y ⊆ Ŝ and X ∩ Ŝ = ∅. Since S satisfies Q p+1 , it must contain a variable, say x p+1 i * from {x p+1 . . . , x p+1 d1 }. As X ∩ Ŝ = ∅, Ŝ ⊆ S, |S| ≤ k, and x p+1 i * ∈ S, we have that |S| ≤ k-1.

  2). Next, consider an anti-monotone clause C = (¬y 1 ∨ ¬y 2 ∨ . . . ¬y d ) (where d ≤ d), and let Y = {y 1 , y 2 , . . . , y d }. Since S satisfies C, Y S = Y \ S is a non-empty set. As S ⊆ S, we have S ∩ Y S = ∅. Thus, S satisfies C. If S satisfies all the non-monotone clauses of F, then the claim follows. Otherwise, let C

Theorem 2 .

 2 10 (♠). Instances (F, k) of Min-Ones d-SAT (d ≥ 2) can be solved in (d + 1)

Lemma 3 . 4 Theorem 3 . 5 .

 3435 (♠). (F, k) is a yes-instance of Min-Ones-2-SAT if and only if ( F, k) is a yes-instance of Min-Ones 2-SAT. Notice that we have stored the sets of clauses C 1 , P, and B, of sizes O k 2 , O k 3 , and O k 6 , respectively. This results in the instance ( F, k) of Min-Ones 2-SAT. The above discussions together with Lemma 3.4 implies the following theorem. Min-Ones-2-SAT admits an algorithm that kernelizes instances (F, k) in k + 2 passes using space O k 6 log n and produces a kernel with O k 6 clauses.

Theorem 4 . 1 .

 41 Any streaming algorithm that solves instances(F, k) of Min-Ones d-SAT (d ≥ 2) in k passes requires space Ω max n 1/k /2 k , log n k, where n is the number of variables in F .The well-known truncated disjointness problem of Communication Complexity has the following lower bound.

Proposition 4 . 2 (

 42 Kushilevitz and Nisan [26], Example 2.12). Let n, k ∈ N with 0 ≤ k ≤ n/2 . Any deterministic protocol for DISJ k requires Ω log n k bits of communication overall .

Lemma 4 . 3 .

 43 Let MOdSSolve be a streaming algorithm for Min-Ones d-SAT (d ≥ 2) that solves instances (F, k) of Min-Ones d-SAT on n variables using space g(n, k). For any k ∈ {1, . . . , n/2 }, if MOdSSolve makes p passes to solve instances (F, k), then g(n, k) = Ω (1/p) log n k . Proof. Consider the following protocol for DISJ k , in which Alice receives the set S ⊆ {1, . . . , n} and Bob receives the set T ⊆ {1, . . . , n} (|S|, |T | = k). Alice constructs the forumla F S = i∈S ¬x i ∨ ¬x i and Bob constructs the formula F T = i∈T x i ∨ x i . Observe that (F S ∧ F T , k) is a YES instance of Min-Ones 2-SAT if and only if S ∩ T = ∅. Now alice runs MOdSSolve with parameter k and F S as partial input, and passes its memory r S to Bob. Bob resumes execution of MOdSSolve on the memory r S and feed it the formula F T . With this, the algorithm makes the first pass over F S ∧ F T . Bob then passes the algorithm's memory r T back to Alice. Using r T , Alice resumes execution of MOdSSolve.

Figure 1

 1 Figure[START_REF] Faisal | Kernelization Algorithms for D-Hitting Set Problems[END_REF] An instance of POT Pointer Chasing with parameters t = 3 and l = 2. The stream consists of t, k and the values of f appearing as in the lexicographic post-order traversal of the tree. In the tree, labels appear in black next to vertices, and the corresponding values of f appear in grey. The chain of pointers leads to the vertex labelled 3, with f (3) = 0.

Lemma 4 . 5 .

 45 Let (T, f ) be an instance of POT Pointer Chasing, where T is a t-ary tree with k + 1 levels. A boolean formula F can be constructed such that (T, f ) is a YES instance of POT Pointer Chasing if and only if (F, k) is a YES instance of Min-Ones 2-SAT.

1 . 4 . 7 .F

 147 3, which apply to Min-Ones d-SAT even when d = Theorem There are no 1-pass streaming algorithms for Min-Ones d-SAT (d ≥ 1) that use space f (k)g(n) (f, g : N → N, computable functions; g = o(n)) on instances (F, k) with n variables. for Min-Ones d-SAT Proof. Observe that any instance (a, b) of INDEX can be encoded as the formula

Theorem 4 . 8 .

 48 Any p-pass streaming algorithm for Min-Ones d-SAT (d ≥ 1) requires space Ω(n/p). Proof. The claim follows from the fact that instances of DISJ can be encoded as SAT formulas in which every clause comprises one literal. Consider the formula F = (C S ∪ C T ), where C S = {x i | i ∈ S} and C T = {¬x i | i ∈ T }. S ∩ T = ∅ if and only if F is satisfiable. By standard arguments from Communication Complexity, any p-pass streaming algorithm for Min-Ones 2-SAT must use space Ω(n/p).

B. 1 (

 1 O d k , O(k))-streaming-FPT Algorithm for Min-Ones-d-SAT In this section, we design an (O d k , O(k))-streaming-FPT algorithm for Min-Ones-d-SAT. The algorithm closely follows the standard O d k (n + m) O(1) branching algorithm for Min-Ones-d-SAT, where n and m are the number of variables and clauses in the input instance.

Algorithm 2 4 if 5 return; 6 while 7 8 return; 9 Function 10 while 13 FinishScan 17 Function 18 while 21 FinishScan 29 C 30 if C = ♦ then 31 if |S| = k then 32 return 0; 33 Let X = {x 1 34 ans = 0; 35 for i = 1 to d do 36 ans

 24567891013171821293031331343536 Algorithm Stream-MOS. Input: A stream of clauses S for an instance (F, k) of Min-Ones-d-SAT. 1 pass-count=0; 2 Function FinishScan() 3 pass-count = pass-count+1; at end of the stream S then end of the stream S is not reached do Read the next clause in the stream; TestSatisfiability(Set S) end of the stream S is not reached do 11 Read the next clause C in the stream; 12 if C is not satisfied by S then FindBranchClause(Set S) end of the stream S is not reached do 19 Read the next clause C in the stream, and let X and Y be the sets of variables in C appearing positively and negatively, respectively; 20 if Y ⊆ S and S ∩ X = ∅ then = FindBranchClause(S); , x 2 , . . . , x d } (where d ≤ d) be the set of variables appearing positively in C; = ans ∨ DetectSolution(S ∪ {x i });

Lemma B. 1 .

 1 Stream-MOS correctly resolves an instance Min-Ones-d-SAT (presented as a stream S, of clauses). Moreover, it uses space bounded by O(k log n) and makes at most O d k passes over S.

  For n ∈ N, [n] denotes the set {1, 2, . . . , n}. Let x ∈ {0, 1} n and i ∈ [n]. The i th coordinate of x is denoted by x[i]. Consider a set of variables V = {x 1 , . . . , x n }. A literal is a variable x i (called an unnegated literal) or its negation ¬x i (called a negated literal). A clause is a disjunction (OR) of literals, e.g. (x 1 ∨ ¬x 2 ∨ ¬x 3 ). It is called monotone if it consists entirely of unnegated literals, and is called anti-monotone if it consists entirely of negated literals. Clauses containing both negated and unnegated literals are called non-monotone.

  |U | bits of memory and O k d time at each step, such that the following conditions are satisfied. 1. |X | ∈ O k d and the bit size of I is bounded by O k d log |U | . 2. Elements of U are represented using log |U | bits. 3. S ⊆ U (or U ) of size at most k is a solution to I if and only if it is a solution to I .

Observation 2.7. For

  i+1 prm . Let ∈ {i + 2, i + 3 . . . , k} be the lowest integer, such that S / ∈ S prm (if such an does not exist, the claim trivially holds). Since S ∈ S -1 prm and S / ∈ S prm , there is a non-monotone clause

i ∈ [k -1] and a set S ∈ S i prm , if S ∈ S i+1

prm , then for each ∈ {i, i + 1, . . . , k}, we have S ∈ S prm .

Proof. Consider i ∈ [k -1] and a set S ∈ S i prm , such that S ∈ S

Proofs of results marked with a ♠ can be found in the appendices.F S T T C S

0 1 9

A A Brief Introduction to Parameterized Complexity

A parameterized problem Π is a subset of Γ * × N, where Γ is a finite alphabet. An instance of a parameterized problem is a tuple (x, k), where x is a classical problem instance and k is an integer, which is called the parameter. The framework of parameterized complexity was originally introduced to deal with NP-hard problems, with the aim to limit the exponential growth in the running time expression to the parameter alone. A central notion in parameterized complexity is fixed-parameter tractability (FPT) which means, for a parameterized problem Π, there is an algorithm that given an instance (x, k), decides whether or not (x, k) is a YES instance of Π in time f (k) • p(|x|), where f is a computable function of k and p is a polynomial in the input size. Another central notion in parameterized complexity is kernelization, which mathematically captures the efficiency of a data preprocessing. A typical goal of a kernelization algorithm is to store only "small" amount of information, which is enough to recover the answer to the original instance. The "smallness" of the stored information is quantified by the input parameter. Formally, a kernelization algorithm or a kernel for a parameterized problem Π is given an input (x, k), and the goal is to obtain an equivalent instance (x , k ) of Π in polynomial time, such that |x | + k ≤ g(k). Here, g is some computable function whose value only depends only on k, and depending on whether it is a linear, polynomial, or exponential function, the kernel is called a linear, polynomial, or exponential kernel, respectively. It is well known that a parameterized problem is FPT if and only if it admits a kernel. Thus, in the literature, the term "kernel" is used for polynomial kernels (unless stated otherwise). For more details on parameterized complexity, we refer the reader to the books of Downey and Fellows [START_REF] Downey | Fundamentals of Parameterized complexity[END_REF], Flum and Grohe [START_REF] Flum | Parameterized Complexity Theory[END_REF], Niedermeier [START_REF] Niedermeier | Invitation to fixed-parameter algorithms[END_REF], and the recent book by Cygan et al. [START_REF] Cygan | Parameterized algorithms[END_REF].

B Missing Proofs from Section 2

Proof of Proposition 2.1

The algorithm Enum-d-HS is given in Algorithm 1. We start by proving the correctness of the algorithm by induction on k. When k ≤ 0, then the algorithm correctly computes the set S k (see . Let us assume that the algorithm returns the correct output for all k ≤ t, where t ∈ N. We will now prove that the output of the algorithm is correct for

14 Remove those sets from S k which are not minimal solutions to (X , U, k);

If there is no non-empty set in X , then the algorithm returns the correct output (Steps 1-2 and 5-6). Hereafter, we assume that Steps 1-6 are not executed (otherwise, we already have the correct output). Also, we have that k ≥ 1 and there is a non-empty set X = {x 1 , x 2 , . . . , x d } ∈ X . Any d-hitting set must contain at least one element from X. By induction hypothesis, for each i ∈ [d ], we (correctly) compute the set S i of all minimal d-hitting sets of size at most k -1, for the instance (X i , U \ {x i }, k -1). Notice that each set S ∈ S i , intersects each set in X i and may not intersect X. Moreover, S ∪ {x i } is a d-hitting set for (X , U, k). From the above discussion (together with the induction hypothesis), we obtain that

k is a set containing all minimal d-hitting sets for (X , U, k). Moreover, by construction we have that

k with non-minimal solutions removed, is the output returned by the algorithm at Step 17. This concludes the proof of correctness of the algorithm.

We now move to the running time analysis of the algorithm. Notice that the running time of the algorithm is given by the recurrence:

Proof of Lemma 2.3

From Proposition 2.2, Pass 1 can compute I t = (X t , U t , k) after reading all the clauses from the stream using O k d log n space, and using O k d time after reading a clause from the stream. Furthermore, |X t | ∈ O k d , and elements of U t are represented using log n bits (by Proposition 2.2 and our assumption that variables of F are x 1 , x 2 , . . . , x n ). Now using Enum-d-HS of Proposition 2.1, the algorithm computes

, there is a non-monotone clause Q = (x ∨ ¬y), such that y ∈ P v ( -1) and x / ∈ P v ( -1). But we also encountered C in pass ( -1), and P v should have been modified, which is a contradiction.

Proof of Lemma 3.4

From Lemma 3.3, it is enough to show that (F , k) is a yes-instance of Min-Ones-2-SAT if and only if ( F, k) is a yes-instance of Min-Ones 2-SAT.

The forward direction follows from the fact that each clause in F is also a clause in F. In the backward direction, let S be a solution to Min-Ones 2-SAT in ( F, k). Notice that S satisfies all monotone and non-monotone clauses of F . For an anti-monotone clause C = (¬x ∨ ¬y), if at least one of x or y is not in V 2 , say x / ∈ V 2 , then x / ∈ S (since S ⊆ V 2 ). Otherwise, x, y ∈ V 2 , and then C is also a clause in F. Thus, C is satisfied by S.

D Streaming FPT Algorithm for IP 2

In this section, we consider a restriction of the integer programming problem, IP 2 (defined below). We show how to convert an instance of IP 2 to an instance of Min-Ones 2-SAT under parameterized streaming constraints, using the approach of Hochbaum et al. [START_REF] Hochbaum | Tight Bounds and 2-Approximation Algorithms for Integer Programs with Two Variables per Inequality[END_REF]. This allows us to use the algorithms for Min-Ones 2-SAT to solve IP 2 . We consider integer programs on n variables and m constraints that have the following form.

Minimize n j=1 w j x j , subject to

), and

where the coefficients appearing in the constraints are integers, and for all j ∈ [n], w j ∈ N. Such integer programs (hereafter called bounded integer programs) were considered by Hochbaum et al. [START_REF] Hochbaum | Tight Bounds and 2-Approximation Algorithms for Integer Programs with Two Variables per Inequality[END_REF], who showed that by applying a transformation to the variables of the program, the problem of finding a feasible solution becomes equivalent to 2-SAT. We consider the following problem.

IP 2

Input: A bounded-IP P, where we want to minimize n j=1 w j x j , subject to a i x pi +b i x qi ≥ c i , for i ∈ [m] and 0 ≤ x j ≤ u j , for j ∈ [n], and an integer k ∈ N. Question: Is there a is feasible solution for P, such that n j=1 w j x j ≤ k? Let (P, k) be an instance of bounded-IP, where P is provided as a stream of w i , for i ∈ [n], followed by the constraints. As a constraint arrives, we show how we create 2-CNF clauses for it. This will give us an instance of (F, k), such that (P, k) is a yes-instance of IP 2 if and only if (F, k) is a yes-instance of Min-Ones-2-SAT. We note that both the construction and the equivalence of the instances follows from [START_REF] Hochbaum | Tight Bounds and 2-Approximation Algorithms for Integer Programs with Two Variables per Inequality[END_REF], therefore, we only briefly explain the construction of F. We use the approach described in Section 4 of [START_REF] Hochbaum | Tight Bounds and 2-Approximation Algorithms for Integer Programs with Two Variables per Inequality[END_REF] to construct F. Consider the variable constraint 0 ≤ x p ≤ u p , for p ∈ [n]. By replacing x p with u p binary variables x p,l (l ∈ [u p ]) and introducing the constraints x p,l ≥ x p,l+1 (l ∈ [u p -1]), we obtain an injective correspondence between x p and (x p,1 , . . . , x p,ui ): x p = up l=1 x p,l . To model these constraints, we add the clause (x p,l ∨ ¬x p,l+1 ) to F, for each l ∈ [u p -1].

Let a i x p + b i x q ≥ c i be a constraint. We only state the case where a p , b q > 0 (for more details, see [START_REF] Hochbaum | Tight Bounds and 2-Approximation Algorithms for Integer Programs with Two Variables per Inequality[END_REF]). For i ∈ [m] and l ∈ {0, . . . , u p }, let α i,l = (c i -la i )/b i -1. The constraint can be expressed by adding the clauses to F as follows.

x p,l+1 ∨ x q,α k,l+1 , for every l ∈ {0, . . . u p -1} with 0 ≤ α i,l < u q .

x p,l+1 , for every l ∈ {0, . . . , u p -1} with α k,l ≥ u q .

x q,α i,l for l = u p with α k,up ≥ 0.

Next, we state how weights (and the function to be minimized) are encoded. Note that the weights appearing in the objective function are nonnegative integers. Let x p be a variable with w p > 1. To express the effect of setting x p to 1 on the objective function, we introduce w p -1 additional variables y p,1 , . . . , y p,wi-1 and the clauses (¬x p ∨ y p,j ) to F, for all j ∈ [w i -1].

Producing the clauses as a stream. Under the reasonable assumption that the clauses of P can each be stored in working memory, i.e. in O(f (k) log n) bits of space, and by the construction of F, it is easy to see that as a constraint of P arrives, we can construct the of corresponding clauses for that constraint in space bounded by O(g(k) log n). The above discussions together with the algorithms of Section 2 and B.1, implies the proof of Theorem 2.11.


Sebastien Fregonese
email: sebastien.fregonese@ims-bordeaux.fr

Marco Cabbia

Soumya Ranjan Panda

IEEE member, Soumya Marina Deng

Magali De Matos

Senior Member, IEEE Thomas Zimmer

Yadav Chandan

Yadav

Didier

Anjan Chakravorty

Chandan Yadav

Ranjan Panda

Magali De Matos

Didier Céli

Analysis of high frequency measurement of transistors along with electromagnetic and SPICE co-simulation

Keywords: On-wafer, s-parameter measurement, HBT, MOSFET, HEMT, high frequency, millimeter-wave, THz, EM simulation, calibration, probes, compact model, fMAX, HICUM, deembedding, TRL

THz silicon based electronics is undergoing rapid developments. In order to keep this momentum high, an accurate and optimized on-wafer characterization procedure needs to be developed. While evaluating passive elements, the measured sparameter data can be verified by a direct use of EM simulation tools. However, this verification requires to precisely introduce part of the measurement environment such as the probes, the pads and access lines to accurately predict the impact of calibration and layout for on-wafer measurements. Unfortunately, this procedure is limited to passive elements. Hence, in this work, we propose a new procedure to emulate the measurement of active devices using an electromagnetic-SPICE co-simulation. By this method, one can clearly highlight that a measurement artefact that was observed for the transistor measurement can be reproduced. One of the most representative example of measurement artefact involves the measurement and estimation of fMAX which is not constant over all frequency band. Also the measurement is difficult to perform above 40 GHz. This typical problem is now undoubtedly attributed to the probe-to-substrate coupling and probe-to-probe coupling which are strongly dependent on the probe geometry. Finally, this co-simulation procedure evidently underlines the need for an optimized de-embedding procedure above 200 GHz.

I. INTRODUCTION

HE THz based silicon electronics has been under development for about fifteen years and has undergone a rapid acceleration in the last five years. Its main advantages include its moderate cost compared to that of the III-V technologies for large market volume [START_REF] Hillger | Terahertz Imaging and Sensing Applications With Silicon-Based Technologies[END_REF] and its capability to integrate different parts of the system such as THz sensor, frequency mixer, etc., and digital information processing unit within a single chip removing the complexity of packaging different modules required in more conventional THz technologies [START_REF] Soumya Ranjan Panda | TCAD simulation and assessment of anomalous deflection in measured S-parameters of SiGe HBTs in THz range[END_REF].

Manuscript received December 13, 2019. This work is partly funded by the French Nouvelle-Aquitaine Authorities through the FAST project. The authors also acknowledge financial support from the EU under Project Taranto (No. 737454). The authors would like to thank STMicroelectronics for supplying the Silicon wafer.

Furthermore, the competitive and rapid development of a silicon based THz system requires accurate CAD software with advanced capabilities such as a EM-Spice approach. These CAD models involve calibrated models from DC and high frequency measurements. Hence it is of utmost importance to understand the transistor s-parameters measurement results and subsequently to verify the validity of the model in the upper frequency range, i. e. above 40 GHz. One of the most typical examples that highlights the complexity of the measurement is the shape of frequency dependent unilateral power gain (U) plot that theoretically drops with -20 dB/dec [START_REF] Teppati | Accuracy of Microwave Transistor \rm T and \rm MAX Extractions[END_REF] and thus the maximum oscillation frequency (fMAX) can be obtained through the constant gain x bandwidth product assumption. For example, Fig. 1 (from [START_REF] Heinemann | SiGe HBT with fx/fmax of 505 GHz/720 GHz[END_REF]) depicts the fMAX determination of the same device measured at two different laboratories showing two different results with two different trends above 40 GHz. Unfortunately high frequency measurement on silicon technology is still a challenge even above 40 GHz when analyzing sensitive parameters such as fMAX. This is due to numerous uncertainties and inaccuracies [START_REF] Sia | Minimizing discontinuities in wafer-level sub-THz measurements up to 750 GHz for device modelling applications[END_REF]- [START_REF] Fregonese | Comparison of On-Wafer TRL Calibration to ISS SOLT Calibration With Open-Short De-Embedding up to 500 GHz[END_REF] summarized below. This problem is strongly increased at higher frequency.

First, on-wafer TRL calibration is commonly admitted as a reference method for high frequency measurement since the reference plane is well defined and because the probe environment does not change between calibration and measurement (calibration standards and DUTs are on the same substrate). Unfortunately, it imposes the shift of one of the two probes to measure the line. This can induce discrepancies in probe positioning [START_REF] Fregonese | On-Wafer Characterization of Silicon Transistors Up To 500 GHz and Analysis of Measurement Discontinuities Between the Frequency Bands[END_REF], [START_REF] Sakamaki | Uncertainty Analysis Method Including Influence of Probe Alignment on On-Wafer Calibration Process[END_REF], [START_REF] Phung | Influence of Microwave Probes on Calibrated On-Wafer Measurements[END_REF], especially when a manual probe positioner is used.

Second, the pad layout design combined with the probe geometry can strongly influence the probe-to-substrate coupling as demonstrated in [START_REF] Seelmann-Eggebert | On the Accurate Measurement and Calibration of S-Parameters for Millimeter Wavelengths and Beyond[END_REF]. Also, we have shown, by employing a specific EM probe model for each of the frequency bands (WR2.2 (325-500 GHz), WR3.4 (220-325 GHz), WR5 (140-220 GHz)) that each probe has a specific geometry enabling a different EM field confinement that entails a TED-2020-06-1251-R 2 different substrate-to-probe coupling. This can lead to erroneous trends and results in inaccurate s-parameter measurements.

Third, different research labs [START_REF] Andrei | Coupling on-wafer measurement errors and their impact on calibration and de-embedding up to 110 GHz for CMOS millimeter wave characterizations[END_REF], [START_REF] Phung | Parasitic effects and measurement uncertainties in multi-layer thin-film structures[END_REF], [13] [5] have shown that measurement results can be influenced by the adjacent structures, resulting in erroneous s-parameters. On the other hand, advanced technologies have a high cost per square millimeter which imposes to increase the density of the test structures for device compact modelling. Hence, a problematic trade-off appears between the cost and measurement accuracy.

Finally, the conventional de-embedding procedure is based on lumped elements approach. Hence, the validity range of deembedding is evidently a function of frequency and structure size. Please note that although more complex approaches have been proposed, they are still not widespread [START_REF] Yau | Device and IC Characterization Above 100 GHz[END_REF], [START_REF] Quan | Iterative De-Embedding and Extracted Maximum Oscillation Frequency $f_\textMAX$ in mm-Wave InP DHBTs: Impact of Device Dimensions on Extraction Errors[END_REF], [START_REF] Mangan | De-embedding transmission line measurements for accurate modeling of IC designs[END_REF]. The whole set of possible uncertainties makes the analysis of the s-parameter measurement extremely difficult and a methodology to verify the measurement is of utmost importance. In the case of passive element characterization, the EM simulation is a very reliable tool to verify the accuracy of the measurement [START_REF] Fregonese | On-Wafer Characterization of Silicon Transistors Up To 500 GHz and Analysis of Measurement Discontinuities Between the Frequency Bands[END_REF], [START_REF] Fregonese | Comparison of On-Wafer TRL Calibration to ISS SOLT Calibration With Open-Short De-Embedding up to 500 GHz[END_REF]. But in the case of active devices this approach is not applicable and alternative routes must be explored. First, one can compare compact model simulation results to calibrated and de-embedded measurements but this method does not bring insight by itself since high frequency parameters are not calibrated at the first stage of the study. Indeed, the compact model requires parameter tuning or extraction for lateral and vertical non-quasi-static effects as well as for substrate model but this cannot be performed without considering the influence of the measurement environment and of the calibration-de-embedding procedure at such high frequency. Another procedure is a direct comparison between the calibrated and de-embedded measurement to TCAD data [START_REF] Soumya Ranjan Panda | TCAD simulation and assessment of anomalous deflection in measured S-parameters of SiGe HBTs in THz range[END_REF]. This method has the advantage of having accurate frequency-dependent s-parameters and figures of merit (FOM) allowing one to differentiate the physical effects from any unwanted or unexpected effects coming from the measurement set-up and procedure. Unfortunately, setting up a TCAD approach is a very complex task and is not considered in this work.

In this work for the first time a new multi-physics approach combining electromagnetic simulation with SPICE simulation is proposed to emulate the complete active device embedded in the measurement environment including probes, pads and test structures. This approach helps to clearly distinguish the transistor behavior from measurement set-up contribution. Also, the HICUM parameters correlated to high frequency, i. e., lateral, vertical non-quasi-static effects (NQS) and substrate part are tuned by integrating the EM environment, calibration and de-embedding. The first part of the paper presents the calibrated compact model validated in the lower frequency band. In the second part, the test structures as well as the EM simulation and EM-SPICE cosimulation procedure are presented. The third part presents the results, concludes on the multi-physics approach and discusses the accuracy of the HBT measurement. The optimization of the on wafer TRL calibration and de-embedding procedure is finally proposed.

II. CALIBRATION OF THE COMPACT MODEL

The first step consists in parameter extraction for the electrical compact model. For this purpose, DC and s-parameter measurements up to 40GHz on specific test structures are required. The B55 technology [START_REF] Chevalier | A 55 nm triple gate oxide 9 metal layers SiGe BiCMOS technology featuring 320 GHz fT / 370 GHz fMAX HBT and high-Q millimeter-wave passives[END_REF] from STMicroelectronics was used with the standard HBT having an emitter area of 0.09x4.8µm² and the HICUM model [START_REF] Schroter | A generalized integral charge-control relation and its application to compact models for silicon-based HBT's[END_REF], [START_REF] Schroter | Physics-based minority charge and transit time modeling for bipolar transistors[END_REF], [22] has been selected for its accuracy. The s-parameter measurements are performed using a SOLT calibration on CSR8 calibration substrate and |Z|-probe. To assess the accuracy of the compact model and the associated model parameter set, the Gummel plot, output curves, transit frequency fT and maximum oscillation frequency fMAX curves are shown in Figs.

A. Test structures

The layout of the test structures is presented in Fig. 3. It is an optimized version of the test structures compared to [START_REF] Yadav | Importance and Requirement of frequency band specific RF probes EM Models in sub-THz and THz Measurements up to 500 GHz[END_REF]: it is dedicated to on-wafer TRL calibration with a large space between structures and it uses staggered test structures to reduce the influence of adjacent structures. Also, the pad geometry has been optimized to be compatible with 100 and 50 µm pitch for millimeter-wave and sub-millimeter-wave measurements.

B. EM simulation

As described in [START_REF] Heinemann | SiGe HBT with fx/fmax of 505 GHz/720 GHz[END_REF], [START_REF] Schmückle | Mutual interference in calibration line configurations[END_REF], [START_REF] Quan | Iterative De-Embedding and Extracted Maximum Oscillation Frequency $f_\textMAX$ in mm-Wave InP DHBTs: Impact of Device Dimensions on Extraction Errors[END_REF], and in order to mimic the measurement environment, the probes are simulated together with the pads, access lines and intrinsic structures. Also, realistic probe models have been elaborated for each frequency band as shown in Fig. 4. The simulation is performed for thru (95µm including access line), reflect, line 1 (215 µm, not shown on Fig. 3), line 2 (619µm), load, transistor-open, transistorshort and finally a specific structure for the transistor that will be described in part C. The set of lines allows an accurate calibration from about 15 GHz to 500 GHz. EM simulation has shown that higher order propagation modes are canceled thanks to the scaling of the microstrip line. Also this is confirmed by the fact that the permittivity is constant within the frequency band starting from 20 GHz (see Fig. 5). The whole set of simulation data is computed using exactly the same procedure as done in the measurement applying a TRL calibration followed by the short-open deembedding. We call it "EM simulated experimental procedure" or EM SimExP.

C. EM-SPICE co-simulation

The next step consists in adding the intrinsic transistor (represented by the compact model simulation results) to the EM simulation environment. In order to have simulation data of the transistor embedded with vias, access lines, pads and probes, we modify the EM transistor-open structure adding two lumped ports for base and collector to connect the EM structure to the SPICE model. Hence, using an s-parameter box, we associate the 4 port matrix of the EM simulation (2 ports at the probe, one port for the base and one port for the collector) to the two-port matrix of the HBT. The whole procedure is described in Fig. 6(b) and the EM simulation structure is described in Fig. 6(a). In that case, we call it "EM-SPICE simulated experimental procedure" or EM-SPICE SimExP. Moreover, raw on-wafer measurements data have been recorded only to be post-processed by our in-house calibration tool to perform on-wafer TRL calibration.

IV. MEASUREMENT METHODOLOGY

V. RESULTS

A. Analysis

In a first step, the consistency of the EM probe models was investigated by comparing the measurement and simulation of the passive elements structures. Figs. 7(a The trends of the capacitor and inductor values are well described and clearly highlight the quality and accuracy of the EM models. Below 110 GHz, the measurement is noisier due to the fact that VNA equipment is from an older generation; nevertheless we can identify the unexpected behavior above 70 GHz with a drop of the C12 capacitance value. In WR5 band, the C12 capacitance becomes negative; this can be attributed to a pronounced probe-to-substrate coupling as well as the probeto-probe coupling in this band. The probe design and the pad layout are visibly incompatible in this frequency band. In addition, inaccuracies in the probe-pad contact were observed in this WR5.1 band, which increases the difficulty of comparing simulation and experiment. In contrast, the calibration in WR3.4 and 2.2 band gives more realistic results. As shown in [START_REF] Yadav | Importance and Requirement of frequency band specific RF probes EM Models in sub-THz and THz Measurements up to 500 GHz[END_REF], this is attributed to highly downscaled probes restraining and guiding the EM field towards the structure in a confined way. In a second step, the EM-SPICE co-simulation is carried out. The s-parameters of the probes with the pads and access lines and the compact model are concatenated. Then, these new sparameters are calibrated using the error terms obtained by the TRL calibration and finally a short-open de-embedding is performed. Assuming a perfect calibration method and a full valid de-embedding procedure, the obtained results are expected to match perfectly with the compact model simulation results. Thus, we obtain and compare three different data sets: (i) the calibrated/de-embedded measured data, (ii) the EM-SPICE (calibrated/de-embedded data from EM-SPICE cosimulation) and (iii) the compact model data.

First, we consider the comparison of the data sets (i) and (ii) that is to say, measurement and EM-SPICE SimExP data. This comparison helps us to understand if some unexpected trends in the measured results are intrinsically correlated to the measurement setup or are due to a user error: The error can be the probe positioning, the probe contact difficulties, the probe tilt or any inaccuracy within the probe's installation. The user error can be completely avoided in EM-SPICE co-simulation data. Fig. 8 presents magnitude and phase of the s-parameters for two different operating points up to 500 GHz. Analyzing the phase of S11, we observe that after a typical monotonous decrease of the phase up to about 250-330 GHz (bias point dependent), a slight increase of the phase appears and then again decreases after 450 GHz. While these effects, in general, are termed as unexpected and questionable, the co-EM-SPICE simulation reproduces the same. Since the eventual measurement uncertainties are suppressed in EM-Spice cosimulation, we deduce that the measurements are correct and the observed phenomenon is correlated to the methodology, to the probes and/or to the design of the test structures. Second, we compare the calibrated and de-embedded EM-SPICE co-simulation results of the transistor to the compact model data and use the former data as a reference. As already said, if the calibration/de-embedding methodology is faultless, the calibrated data will perfectly match the compact model data. In case of a divergence, we can conclude that the calibration method or the de-embedding procedure has some limitations in term of accuracy or their applicability is questionable in certain frequency bands. Keeping the example of the phase of S11 and comparing it to the reference data where a continuous decrease of the phase up to 500 GHz for both operating points can be noticed, we conclude that the calibration methodology together with the de-embedding procedure doesn't allow to obtain the expected results accurately above 250-330 GHz (bias point dependent).

Extending this approach to the whole set of s-parameters, we identify three types of mismatch that were observed in both the measurement and the EM-SPICE co-simulation with respect to the reference data. The first is related to the reflection coefficients S11 and S22, the second to the band discontinuity between two frequency bands and the third to the transmission coefficients S12 and S21 as explained here. First, the magnitude and phase of S11 as well as the phase of S22 show an unexpected behavior above 350-400 GHz. Secondly, some discontinuities appear at the band transition at 220 GHz considering the lower band WR5.1 and the upper band WR3.4. This is observed for measurement as well as in the EM-SPICE co-simulation and can be attributed to the probe-to-substrate coupling which is strong in the case of the WR5 band, but much less pronounced in the WR3.4 band. Third, the magnitude of S21 shows a slight change in slope above 400 GHz at VBE=0.8 V which is also observed through EM-SPICE co-simulation. This is attributed to crosstalk and confirmed also by an unreliable value of S12 above 400 GHz. More unexpectedly (and barely visible on s-parameters in the frequency range from 50 GHz to 110 GHz), a change of the slope of mag(S12) is observed which can also be attributed to the cross-talk effect. Please note that a similar effect has been observed on C12 (see Fig. 7a) for the transistor-open structure. Although the effect on S12 seems to be negligible, it has a strong impact on fMAX (see Fig. 8) with an unexpected and significant reduction on fMAX beyond 50 GHz that remained unexplained for a long time.

B. Improvement of the calibration/de-embedding methodology

The results presented above show that the measured data and the EM-SPICE co-simulation are reasonably well aligned, but differ from the compact simulation data over a certain frequency range, requiring us to review the calibration and deembedding procedures. In order to improve the calibration methodology, two main routes can be explored. The first one concerns the cross-talk above 400 GHz which requires to modify the probe-to-probe distance on the test-structures but that can be only investigated in a future chip design. The second one concerns the reflection s-parameters. Observing the TED-2020-06-1251-R 6transistor-open and transistor-short measurement and simulation results in Fig. 7, the capacitances and inductances are not completely constant with frequency. This frequency dependence (0.6fF / 100 GHz bandwidth) demonstrates a typical distributed behavior of the capacitance and is attributed to the access line. Hence, an easy way to proceed is to move the reference plane that is set at 15 µm after the pad to 40 µm after the pad. Doing so, by exploiting the same test structures design and raw measurements, the calibration plane is set closer to the DUT by simple matrices manipulation, so that the distributed effects are strongly reduced as observed for the capacitance and inductors (see Fig. 9). Applying this reference plane shift to the TRL then improves the accuracy of the phase of S11 and S22 in both the EM-SPICE co-simulation and the measurement, and they are approaching the compact model data used as reference (see Fig. 10 and Fig. 11). Also, an improvement can be observed for the magnitude of S11 and S22. On can note that the three sets of data, measurement, EM-SPICE co-simulation and reference, do not perfectly converge for the magnitude of S11. This is attributed to a perfectible calibration of the lateral non-quasi static effects in the HICUM model. Finally, an improvement is also noted for the maximum oscillation frequency but only at very high frequencies above 220 GHz.

Below 220 GHz, the fMAX curve is still questionable. In order to clarify the artefacts, we use the highly downscaled probe from the WR3.4 & WR2.2 band to simulate the calibration/deembedding procedure also for the lower frequency bands since this downscaled probe is less prone to cross-talk. Doing so and analyzing the magnitude of S12, we can observe that the unexpected decrease of S12 above 50 GHz is suppressed. Fig 11 shows the difference between the EM-SPICE SimExP data to the reference (HICUM model). The figure indicates that the error on magnitude of S12 with the set of probes used in experiment rises to 3 dB at 110 GHz and up to 6 dB at 220 GHz while with the WR3.4 & WR2.2 probe the difference is limited to less than 1 dB over the whole frequency band.

Moreover, the surprising frequency behavior observed for WR5 (140-220 GHz) band with strong discontinuities at the band edge is also suppressed. This can be explained by a decreased probe-to-substrate coupling as well as a reduced crosstalk thanks to a better design of the probe that helps to confine the EM field [START_REF] Yadav | Importance and Requirement of frequency band specific RF probes EM Models in sub-THz and THz Measurements up to 500 GHz[END_REF]. Secondly, this modification noticed for S12 directly affects the fMAX value. The previously observed sudden decrease for fMAX at a frequency higher than 50 GHz is quasi suppressed when using an optimized probe geometry. For example, the error for fMAX measurement is reduced by a factor four at 110GHz. The same observation can be made in the WR5 band (140-220 GHz) where the unexpected monotonic increase of fMAX is replaced by a monotonic decrease. Hence, the commonly known noisy fMAX curve is strongly impacted by the measurement set-up, especially by the probes topology, the layout of the pads and test structures. Therefore, the double verification of fMAX with two different benches having different probes as demonstrated in [START_REF] Heinemann | SiGe HBT with fx/fmax of 505 GHz/720 GHz[END_REF] and shown in Fig. 1 is very relevant. In summary, the change in the TRL reference plane closer to the DUT and the use of optimized probe such as the WR2.2 from Picoprobe GGB shows that the measurement can be performed with an accuracy better than 0.3 dB in terms of magnitude and 5 degree in terms of phase of S parameters for this particular test structures up to 400 GHz. fT and fMAX measurement accuracy would be better than 5% which is very reasonable.

VI. CONCLUSION

A simulation methodology using EM-SPICE approach is proposed to verify the consistency of high frequency transistor measurements. This new method is based on EM-SPICE cosimulation including the simulation of the RF probes, the pads, the access lines as well as all the DUTs and to apply the onwafer TRL calibration and de-embedding procedure. Although, this method is applied to SiGe HBT in this work, it can be directly transferred to III-V HBTs, HEMTs, or silicon FET transistors which face similar issues in high frequency measurements.

With this method we have clearly identified some artefacts that can be attributed to a combination of different effects such as probe-to-substrate coupling, calibration together with deembedding method and layout design. The unexpected trend of the key figures of merit i. e. the fMAX of high speed transistors has been explained for the first time. One possible solution of the fMAX measurement improvement requires the downscaling of probes below 220 GHz.

Fig. 1 :

 1 Fig. 1: Dependence of fT and fMAX on extrapolation frequency for the same HBT measured at IHP and Infineon. SOLT calibration with an impedance standard substrate (ISS) -adapted from [2] -(Permission to reuse to IEEE will be done prior publication)

  2 (a), (b), (c), and (d) respectively.

Fig. 2 :

 2 Fig. 2: Verification of HICUM model simulation with measurement: a) Gummel plot, b) Output curves, c) Transit frequency, d) Maximum oscillation frequency-B55 technology HBT 0.09*4.8µm² from STMicroelectronics-c and d are computed at 38 GHz.

Fig. 3 :

 3 Fig. 3: Layout of the main test-structures used for TRL calibration and deembedding -B55 technology-STMicroelectronics

Fig. 4 .

 4 Fig. 4. EM probe models corresponding to (a) 1 GHz -110 GHz, (b) WR5, (c) WR3.4 and WR2.2. In all models, white=coaxial insulator, gray=solder, yellow=metal.

Fig. 5 .

 5 Fig. 5. a) Real and imaginary part of the effective dielectric, measurement, EM and EM intrinsic simulation. (Intrinsic simulation means that the EM port have been considered after the pad, see fig. 3)

FourFig. 6 :

 6 Fig. 6: a) EM simulation structure with zoom on bottom view for the transistor simulation, b) Description of the EM-SPICE simulation of experimental procedure (SimExP) used to simulate the transistor calibration with deembedding including the EM environment.

  ) and 7(b) present the calibrated transistor-open and transistor-short data up to 500 GHz, respectively.

Fig. 7 :

 7 Fig. 7: a) Capacitances of the transistor-open; b) Inductors of the transistorshort; c) S11 of transistor open, d) S11 of transistor short; measurement (symbols), EM SimExP (EM with probe and calibration) (solid line) and EM intrinsic simulation (dashed line) up to 500 GHz using an on-wafer TRL (thru of 65µm) -B55 technology -STMicroelectronics

  ports EM simulation structure, zoom of bottom view of half structure

Fig. 8 :

 8 Fig. 8: Magnitude and phase of the S parameters for two different operating points, transit frequency and maximum oscillation frequency extrapolation. Measurement (symbols), EM-SPICE SimExP data (EM-HICUM with probe with calibration-de-embedding) (solid line) and HICUM simulation (dashed line). Both are calibrated using an on-wafer TRL (reference plane: through of 65µm) with de-embedding -Dashed line is HICUM model of the transistor (B55 technology-STMicroelectronics).

Fig. 9 .

 9 Fig. 9. a) Capacitances of the transistor open; b) Inductors of the transistor short; measurement (symbols), EM SimExP (solid line) and EM intrinsic simulation (dashed line) up to 500 GHz using an on-wafer TRL with the second reference plane (thru of 15µm) -B55 technology-STMicroelectronics

Fig. 10 :

 10 Fig. 10: Magnitude and phase of the S parameters, transit frequency and maximum oscillation frequency extrapolation. Measurement (symbols), EM-SPICE SimExP data (EM-HICUM with probe with calibration-de-embedding) (solid line) and HICUM simulation (dashed line). Both are calibrated using an on-wafer TRL (reference plane: through of 15µm) with de-embedding-Dashed line is HICUM model of the transistor (B55 technology-STMicroelectronics).

Fig. 11 .

 11 Fig. 11. Error assessment for EM-SPICE SimExP data using a WR2.2 (325-500 GHz) for the whole frequency band (1-500GHz) compared to the EM-SPICE SimExP using each probe topology of fig. 4 and for the two calibration reference plane (14.5 and 65 µm): Magnitude and phase of S parameter, error in GHz for the transit frequency and maximum oscillation frequency extrapolation..


J Moses

P Tremblin

O Venot

Y Miguel

Predicted ARIEL Phase-Curve Observations of Neptune-Class Exoplanets from 2D Chemical and Thermal Modeling

Bulletin of the AAS • Vol. 52, Issue 6 (DPS52 Abstracts)

Predicted ARIEL Phase-Curve Observations of Neptune-Class Exoplanets from 2D Chemical and Thermal Modeling 2 ESA's Atmospheric Remote-sensing Infrared Exoplanet Large-survey (ARIEL) mission, due to launch in 2028, will acquire simultaneous visible photometry and near-infrared spectra of ~1000 exoplanets that transit their host stars (Tinneti et al. 2018, Exp. Astron. 46, 135). The infrared molecular bands of many species that are expected to reside in the atmospheres of transiting-exoplanet targets are included in the 1.25-7.8 micron spectral range covered by ARIEL. To investigate the role of chemistry in ARIEL phase-curve observations, we use a two-dimensional (2D) thermal-structure model and pseudo-2D chemical kinetics model to predict the altitude and longitude variation of atmospheric temperatures and constituent abundances at low latitudes on Neptune-class exoplanets that orbit at different distances from their host stars. Our models predict that the low-latitude vertical profiles of temperature and species' abundances vary significantly with longitude and with planetary equilibrium temperature (T eq ). Day-night temperature contrasts are found to increase with increasing planetary T eq . We also find that horizontal transport-induced quenching acts to homogenize species' abundances with longitude on our Neptune-class exoplanets, similar to what is expected to occur on hot Jupiters (Cooper & Showman 2006, ApJ 649, 1048;Agúndez et al. 2014, A&A 564, A73). Our models have implications with respect to phase-curve observations of Neptune-class exoplanets with ARIEL. For example, we find that that the atmosphere remains near thermochemical equilibrium and that temperature variations dominate phase-curve variations on very hot Neptunes, whereas disequilibrium chemistry is important on cool Neptunes but their emission emission does not vary much with planetary phase. Our models reveal a "sweet spot" in T eq space such that intermediatetemperature Neptunes have phase curves that are affected by both global temperature and abundance variations, revealing interesting atmospheric processes. This sweet spot in T eq shifts to lower temperatures as metallicity is increased, making cool higher-metallicity Neptune-class planets appropriate targets for ARIEL phase-curve observations.