Compact Numerical Quadrature Formulas for Hypersingular Integrals and Integral Equations

In the first part of this work, we derive compact numerical quadrature formulas for finite-range integrals $I[f]=\int^{b}_{a}f(x)\,dx$ , where f(x)=g(x)|x?t| ^?? , ?? being real. Depending on the value of ??, these integrals are defined either in the regular sense or in the sense of Hadamard finite part. Assuming that g??C ^??[a,b], or g??C ^??(a,b) but can have arbitrary algebraic singularities at x=a and/or x=b, and letting h=(b?a)/n, n an integer, we derive asymptotic expansions for ${T}^{*}_{n}[f]=h\sum_{1\leq j\leq n-1,\ x_{j}\neq t}f(x_{j})$ , where x _j =a+jh and t??{x ₁,??,x _n?1}. These asymptotic expansions are based on some recent generalizations of the Euler?CMaclaurin expansion due to the author (A.?Sidi, Euler?CMaclaurin expansions for integrals with arbitrary algebraic endpoint singularities, in Math. Comput., 2012), and are used to construct our quadrature formulas, whose accuracies are then increased at will by applying to them the Richardson extrapolation process. We pay particular attention to the case in which ??=?2 and f(x) is T-periodic with T=b?a and $f\in C^{\infty}(-\infty,\infty)\setminus\{t+kT\}^{\infty}_{k=-\infty}$ , which arises in the context of periodic hypersingular integral equations. For this case, we propose the remarkably simple and compact quadrature formula $\widehat{Q}_{n}[f]=h\sum^{n}_{j=1}f(t+jh-h/2)-\pi^{2} g(t)h^{-1}$ , and show that $\widehat{Q}_{n}[f]-I[f]=O(h^{\mu})$ as h??0 ???>0, and that it is exact for a class of singular integrals involving trigonometric polynomials of degree at most n. We show how $\widehat{Q}_{n}[f]$ can be used for solving hypersingular integral equations in an efficient manner. In the second part of this work, we derive the Euler?CMaclaurin expansion for integrals $I[f]=\int^{b}_{a} f(x)dx$ , where f(x)=g(x)(x?t) ^?? , with g(x) as before and ??=?1,?3,?5,??, from which suitable quadrature formulas can be obtained. We revisit the case of ??=?1, for which the known quadrature formula $\widetilde{Q}_{n}[f]=h\sum^{n}_{j=1}f(t+jh-h/2)$ satisfies $\widetilde{Q}_{n}[f]-I[f]=O(h^{\mu})$ as h??0 ???>0, when f(x) is T-periodic with T=b?a and $f\in C^{\infty}(-\infty,\infty)\setminus\{t+kT\}^{\infty}_{k=-\infty}$ . We show that this formula too is exact for a class of singular integrals involving trigonometric polynomials of degree at most n?1. We provide numerical examples involving periodic integrands that confirm the theoretical results.     

A note on balanced immunity

For a finite alphabet ∑ we define a binary relation on \(2^{\Sigma *} \times 2^{2^{\Sigma ^* } } \) , called balanced immunity. A setB ? ∑* is said to be balancedC-immune (with respect to a classC ? 2^Σ* of sets) iff, for all infiniteL εC, $$\mathop {\lim }\limits_{n \to \infty } \left| {L^{ \leqslant n} \cap B} \right|/\left| {L^{ \leqslant n} } \right| = \tfrac{1}{2}$$ Balanced immunity implies bi-immunity and in natural cases randomness. We give a general method to find a balanced immune set'B for any countable classC and prove that, fors(n) =o(t(n)) andt(n) >n, there is aB εSPACE(t(n)), which is balanced immune forSPACE(s(n)), both in the deterministic and nondeterministic case.     

Augmenting Edge-Connectivity between Vertex Subsets

Given a directed or undirected graph G=(V,E), a collection ${\mathcal{R}}=\{(S_{i},T_{i}) \mid i=1,2,\ldots,|{\mathcal{R}}|, S_{i},T_{i} \subseteq V, S_{i} \cap T_{i} =\emptyset\}$ of two disjoint subsets of V, and a requirement function $r: {\mathcal{R}} \to\mathbb{R}_{+}$ , we consider the problem (called area-to-area edge-connectivity augmentation problem) of augmenting G by a smallest number of new edges so that the resulting graph $\hat{G}$ satisfies $d_{\hat{G}}(X)\geq r(S,T)$ for all X?V, $(S,T) \in{\mathcal{R}}$ with S?X?V?T, where d _G (X) denotes the degree of a vertex set X in G. This problem can be regarded as a natural generalization of the global, local, and node-to-area edge-connectivity augmentation problems. In this paper, we show that there exists a constant c such that the problem is inapproximable within a ratio of $c\log{|{\mathcal{R}}|}$ , unless P=NP, even restricted to the directed global node-to-area edge-connectivity augmentation or undirected local node-to-area edge-connectivity augmentation. We also provide an ${\mathrm{O}}(\log{|{\mathcal{R}}|})$ -approximation algorithm for the area-to-area edge-connectivity augmentation problem, which is a natural extension of Kortsarz and Nutov’s algorithm (Kortsarz and Nutov, J. Comput. Syst. Sci., 74:662–670, 2008). This together with the negative result implies that the problem is ${\varTheta}(\log{|{\mathcal{R}}|})$ -approximable, unless P=NP, which solves open problems for node-to-area edge-connectivity augmentation in Ishii et al. (Algorithmica, 56:413–436, 2010), Ishii and Hagiwara (Discrete Appl. Math., 154:2307–2329, 2006), Miwa and Ito (J. Oper. Res. Soc. Jpn., 47:224–243, 2004). Furthermore, we characterize the node-to-area and area-to-area edge-connectivity augmentation problems as the augmentation problems with modulotone and k-modulotone functions.     

The structure of nonsingular polynomial matrices

LetK be a field and letL ∈ K ^{n × n [z]} be nonsingular. The matrixL can be decomposed as \(L(z) = \hat Q(z)(Rz + S)\hat P(z)\) so that the finite and (suitably defined) infinite elementary divisors ofL are the same as those ofRz + S, and \(\hat Q(z)\) and \(\hat P(z)^T\) are polynomial matrices which have a constant right inverse. If $$Rz + S = \left( {\begin{array}{*{20}c} {zI - A} & 0 \\ 0 & {I - zN} \\ \end{array} } \right)$$ andK is algebraically closed, then the columns of \(\hat Q\) and \(\hat P^T\) consist of eigenvectors and generalized eigenvectors of shift operators associated withL.     

hp Adaptive finite elements based on derivative recovery and superconvergence

In this paper, we present a new approach to hp-adaptive finite element methods. Our a posteriori error estimates and hp-refinement indicator are inspired by the work on gradient/derivative recovery of Bank and Xu (SIAM J Numer Anal 41:2294?C2312, 2003; SIAM J Numer Anal 41:2313?C2332, 2003). For element ?? of degree p, R(? ^p u _hp ), the (piece-wise linear) recovered function of ? ^p u is used to approximate ${|\varepsilon|_{1,\tau} = |\hat{u}_{p+1} - u_{p}|_{1,\tau}}$ , which serves as our local error indicator. Under sufficient conditions on the smoothness of u, it can be shown that ${\|{\partial^{p}(\hat{u}_{p+1} - u_{p})\|_{0,\Omega}}}$ is a superconvergent approximation of ${\|(I - R){\partial}^p u_{hp}\|_{0,\Omega}}$ . Based on this, we develop a heuristic hp-refinement indicator based on the ratio between the two quantities on each element. Also in this work, we introduce nodal basis functions for special elements where the polynomial degree along edges is allowed to be different from the overall element degree. Several numerical examples are provided to show the effectiveness of our approach.     

Rounds in Combinatorial Search

A set system $\mathcal{H} \subseteq2^{[m]}$ is said to be separating if for every pair of distinct elements x,y∈[m] there exists a set $H\in\mathcal{H}$ such that H contains exactly one of them. The search complexity of a separating system $\mathcal{H} \subseteq 2^{[m]}$ is the minimum number of questions of type “x∈H?” (where $H \in\mathcal{H}$ ) needed in the worst case to determine a hidden element x∈[m]. If we receive the answer before asking a new question then we speak of the adaptive complexity, denoted by $\mathrm{c} (\mathcal{H})$ ; if the questions are all fixed beforehand then we speak of the non-adaptive complexity, denoted by $\mathrm{c}_{na} (\mathcal{H})$ . If we are allowed to ask the questions in at most k rounds then we speak of the k-round complexity of $\mathcal{H}$ , denoted by $\mathrm{c}_{k} (\mathcal{H})$ . It is clear that $|\mathcal{H}| \geq\mathrm{c}_{na} (\mathcal{H}) = \mathrm{c}_{1} (\mathcal{H}) \geq\mathrm{c}_{2} (\mathcal{H}) \geq\cdots\geq\mathrm{c}_{m} (\mathcal{H}) = \mathrm{c} (\mathcal{H})$ . A group of problems raised by G.O.H. Katona is to characterize those separating systems for which some of these inequalities are tight. In this paper we are discussing set systems $\mathcal{H}$ with the property $|\mathcal{H}| = \mathrm{c}_{k} (\mathcal{H}) $ for any k≥3. We give a necessary condition for this property by proving a theorem about traces of hypergraphs which also has its own interest.     

Predicting the future of functions on flows

Let Ω be a topological space,S _t ∈ R (R the reals) a homeomorphism group on Ω andμ a Borel measure invariant with respect toS _t , (μ(Ω)=1); forP ∈Ω putS _t (P)=P _t . Assumef ∈L ₂(Ω,μ); according to E. Hopf there is for almost everyP ∈ Ω a well-determined spectral function σ(P,λ),λ ∈ R with lim \(T^{ - 1} \int_0^T {f(P_{t + s} )\overline {f(P_t )} dt = \int_{ - \infty }^{ + \infty } {e^{i\lambda s} d\sigma (P\lambda )} }\) . The question to be considered is:^*) if for a fixedP ∈ Ω we know the “past”f(P _t ), t ≦ 0, is it then possible to compute (or “predict”) the future valuesf(P _t ), t > 0? By using ideas from linear prediction theory we show that if \(\int_{ - \infty }^{ + \infty } {(1 + \lambda ^2 )\log \frac{d}{{d\lambda }}\sigma (P,\lambda )} d\lambda = - \infty\) then the prediction required by^*) is possible. An algorithm is described which accomplishes the prediction.     

A Simple D 2-Sampling Based PTAS for k-Means and Other Clustering Problems

Given a set of points \(P \subset\mathbb{R}^{d}\) , the k-means clustering problem is to find a set of k centers \(C = \{ c_{1},\ldots,c_{k}\}, c_{i} \in\mathbb{R}^{d}\) , such that the objective function ∑ _x∈P e(x,C)², where e(x,C) denotes the Euclidean distance between x and the closest center in C, is minimized. This is one of the most prominent objective functions that has been studied with respect to clustering. D ²-sampling (Arthur and Vassilvitskii, Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’07, pp. 1027–1035, SIAM, Philadelphia, 2007) is a simple non-uniform sampling technique for choosing points from a set of points. It works as follows: given a set of points \(P \subset\mathbb{R}^{d}\) , the first point is chosen uniformly at random from P. Subsequently, a point from P is chosen as the next sample with probability proportional to the square of the distance of this point to the nearest previously sampled point. D ²-sampling has been shown to have nice properties with respect to the k-means clustering problem. Arthur and Vassilvitskii (Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’07, pp. 1027–1035, SIAM, Philadelphia, 2007) show that k points chosen as centers from P using D ²-sampling give an O(logk) approximation in expectation. Ailon et al. (NIPS, pp. 10–18, 2009) and Aggarwal et al. (Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 15–28, Springer, Berlin, 2009) extended results of Arthur and Vassilvitskii (Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA’07, pp. 1027–1035, SIAM, Philadelphia, 2007) to show that O(k) points chosen as centers using D ²-sampling give an O(1) approximation to the k-means objective function with high probability. In this paper, we further demonstrate the power of D ²-sampling by giving a simple randomized (1+?)-approximation algorithm that uses the D ²-sampling in its core.     

Formule di quadratura «chiuse» di tipo gaussiano: Tabulzione dei nodi e dei coefficienti

The coefficientsA _hi and the nodesx _mi for «closed” Gaussian-type quadrature formulae $$\int\limits_{ - 1}^1 {f(x)dx = \sum\limits_{h = 0}^{2_8 } {\sum\limits_{i = 0}^{m + 1} {A_{hi} f^{(h)} (x_{mi} ) + R\left[ {f(x)} \right]} } } $$ withx _m0 =?1,x _{m, m+1} =1 andR[f(x)]=0 iff(x) is a polinomial of degree at most2m(s+1)+2(2s+1)?1, have been tabulated for the cases: $$\left\{ \begin{gathered} s = 1,2 \hfill \\ m = 2,3,4,5 \hfill \\ \end{gathered} \right.$$ .     

Fully Smoothed ℓ 1-TV Models: Bounds for the Minimizers and Parameter Choice

We consider a class of convex functionals that can be seen as $\mathcal{C}^{1}$ smooth approximations of the ? ₁-TV model. The minimizers of such functionals were shown to exhibit a qualitatively different behavior compared to the nonsmooth ? ₁-TV model (Nikolova et al. in Exact histogram specification for digital images using a variational approach, 2012). Here we focus on the way the parameters involved in these functionals determine the features of the minimizers  $\hat{u}$ . We give explicit relationships between the minimizers and these parameters. Given an input digital image f, we prove that the error $\|\hat{u}- f\| _{\infty}$ obeys $b-\varepsilon\leq\|\hat{u}-f\|_{\infty}\leq b$ where b is a constant independent of the input image. Further we can set the parameters so that ε>0 is arbitrarily close to zero. More precisely, we exhibit explicit formulae relating the model parameters, the input image f and the values b and ε. Conversely, we can fix the parameter values so that the error $\|\hat{u}- f\|_{\infty}$ meets some prescribed b,ε. All theoretical results are confirmed using numerical tests on natural digital images of different sizes with disparate content and quality.     

Pseudorandom generators for combinatorial checkerboards

We define a combinatorial checkerboard to be a function f : {1, . . . , m} ^d → {1,?1} of the form ${f(u_1,\ldots,u_d)=\prod_{i=1}^df_i(u_i)}$ for some functions f _i : {1, . . . , m} → {1,?1}. This is a variant of combinatorial rectangles, which can be defined in the same way but using {0, 1} instead of {1,?1}. We consider the problem of constructing explicit pseudorandom generators for combinatorial checkerboards. This is a generalization of small-bias generators, which correspond to the case m = 2. We construct a pseudorandom generator that ${\epsilon}$ -fools all combinatorial checkerboards with seed length ${O\bigl(\log m+\log d\cdot\log\log d+\log^{3/2} \frac{1}{\epsilon}\bigr)}$ . Previous work by Impagliazzo, Nisan, and Wigderson implies a pseudorandom generator with seed length ${O\bigl(\log m+\log^2d+\log d\cdot\log\frac{1}{\epsilon}\bigr)}$ . Our seed length is better except when ${\frac{1}{\epsilon}\geq d^{\omega(\log d)}}$ .     

Query-Efficient Locally Decodable Codes of Subexponential Length

A k-query locally decodable code (LDC) C : Σ ⁿ → Γ ^N encodes each message x into a codeword C(x) such that each symbol of x can be probabilistically recovered by querying only k coordinates of C(x), even after a constant fraction of the coordinates has been corrupted. Yekhanin (in J ACM 55:1–16, 2008) constructed a 3-query LDC of subexponential length, N = exp(exp(O(log n/log log n))), under the assumption that there are infinitely many Mersenne primes. Efremenko (in Proceedings of the 41st annual ACM symposium on theory of computing, ACM, New York, 2009) constructed a 3-query LDC of length ${N_{2}={\rm exp}({\rm exp} (O(\sqrt{\log n\log\log n})))}$ with no assumption, and a 2 ^r -query LDC of length ${N_{r}={\rm exp}({\rm exp}(O(\sqrt[r]{\log n(\log \log n)^{r-1}})))}$ , for every integer r ≥ 2. Itoh and Suzuki (in IEICE Trans Inform Syst E93-D 2:263–270, 2010) gave a composition method in Efremenko’s framework and constructed a 3 · 2 ^r-2-query LDC of length N _r , for every integer r ≥ 4, which improved the query complexity of Efremenko’s LDC of the same length by a factor of 3/4. The main ingredient of Efremenko’s construction is the Grolmusz construction for super-polynomial size set-systems with restricted intersections, over ${\mathbb{Z}_m}$ , where m possesses a certain “good” algebraic property (related to the “algebraic niceness” property of Yekhanin in J ACM 55:1–16, 2008). Efremenko constructed a 3-query LDC based on m = 511 and left as an open problem to find other numbers that offer the same property for LDC constructions. In this paper, we develop the algebraic theory behind the constructions of Yekhanin (in J ACM 55:1–16, 2008) and Efremenko (in Proceedings of the 41st annual ACM symposium on theory of computing, ACM, New York, 2009), in an attempt to understand the “algebraic niceness” phenomenon in ${\mathbb{Z}_m}$ . We show that every integer m =  pq = 2 ^t ?1, where p, q, and t are prime, possesses the same good algebraic property as m = 511 that allows savings in query complexity. We identify 50 numbers of this form by computer search, which together with 511, are then applied to gain improvements on query complexity via Itoh and Suzuki’s composition method. More precisely, we construct a ${3^{\lceil r/2\rceil}}$ -query LDC for every positive integer r < 104 and a ${\left\lfloor (3/4)^{51} \cdot 2^{r}\right\rfloor}$ -query LDC for every integer r ≥ 104, both of length N _r , improving the 2 ^r queries used by Efremenko (in Proceedings of the 41st annual ACM symposium on theory of computing, ACM, New York, 2009) and 3 · 2 ^r-2 queries used by Itoh and Suzuki (in IEICE Trans Inform Syst E93-D 2:263–270, 2010). We also obtain new efficient private information retrieval (PIR) schemes from the new query-efficient LDCs.     

The Equivalence of Sampling and Searching

In a sampling problem, we are given an input x∈{0,1} ⁿ , and asked to sample approximately from a probability distribution \(\mathcal{D}_{x}\) over \(\operatorname{poly} ( n ) \) -bit strings. In a search problem, we are given an input x∈{0,1} ⁿ , and asked to find a member of a nonempty set A _x with high probability. (An example is finding a Nash equilibrium.) In this paper, we use tools from Kolmogorov complexity to show that sampling and search problems are “essentially equivalent.” More precisely, for any sampling problem S, there exists a search problem R _S such that, if \(\mathcal{C}\) is any “reasonable” complexity class, then R _S is in the search version of \(\mathcal{C}\) if and only if S is in the sampling version. What makes this nontrivial is that the same R _S works for every  \(\mathcal{C}\) . As an application, we prove the surprising result that SampP=SampBQP if and only if FBPP=FBQP. In other words, classical computers can efficiently sample the output distribution of every quantum circuit, if and only if they can efficiently solve every search problem that quantum computers can solve.     

Geometric properties of linearizable control systems

In this paper the distributions associated with a non-linear system of the form $$\frac{{dx}}{{dt}} = f(x) + \sum\limits_{\alpha = 1}^m {u_\alpha (t)g_\alpha (x)} ,f(0) = 0andx \in U_0 \subset R^n$$ are studied in relation to nonlinear state feedback $$u(x,v) = \hat a(x) + \hat S(x)v$$ withâ, u, v ∈ R ^m and ? a nonsingularm×m matrix withâ, ? functions ofx. Bothf andg are vector fields onU ₀, generally assumed to be real analytic. Two nested families of distributions {G ^j } and {M ^j } associated with the system are examined with emphasis on generic points ofU ₀, where it is shown that the usual conditions for feedback linearizability contain some redundancy. A characterization of state linearizability in terms of invariant factors of the equivalent linear form are given, and a criterion in terms of the distributions for a type of partial linearization is found.     

Polynomial regression under arbitrary product distributions

In recent work, Kalai, Klivans, Mansour, and Servedio (2005) studied a variant of the “Low-Degree (Fourier) Algorithm” for learning under the uniform probability distribution on {0,1} ⁿ . They showed that the L ₁ polynomial regression algorithm yields agnostic (tolerant to arbitrary noise) learning algorithms with respect to the class of threshold functions—under certain restricted instance distributions, including uniform on {0,1} ⁿ and Gaussian on ? ⁿ . In this work we show how all learning results based on the Low-Degree Algorithm can be generalized to give almost identical agnostic guarantees under arbitrary product distributions on instance spaces X ₁×???×X _n . We also extend these results to learning under mixtures of product distributions. The main technical innovation is the use of (Hoeffding) orthogonal decomposition and the extension of the “noise sensitivity method” to arbitrary product spaces. In particular, we give a very simple proof that threshold functions over arbitrary product spaces have δ-noise sensitivity $O(\sqrt{\delta})$ , resolving an open problem suggested by Peres (2004).     

Minimum Manhattan Network Problem in Normed Planes with Polygonal Balls: A Factor 2.5 Approximation Algorithm

Let ${\mathcal{B}}$ be a centrally symmetric convex polygon of ?² and ‖p?q‖ be the distance between two points p,q∈?² in the normed plane whose unit ball is ${\mathcal{B}}$ . For a set T of n points (terminals) in ?², a ${\mathcal{B}}$ -network on T is a network N(T)=(V,E) with the property that its edges are parallel to the directions of ${\mathcal{B}}$ and for every pair of terminals t _i and t _j , the network N(T) contains a shortest ${\mathcal{B}}$ -path between them, i.e., a path of length ‖t _i ?t _j ‖. A minimum ${\mathcal{B}}$ -network on T is a ${\mathcal{B}}$ -network of minimum possible length. The problem of finding minimum ${\mathcal{B}}$ -networks has been introduced by Gudmundsson, Levcopoulos, and Narasimhan (APPROX’99) in the case when the unit ball ${\mathcal{B}}$ is a square (and hence the distance ‖p?q‖ is the l ₁ or the l _∞-distance between p and q) and it has been shown recently by Chin, Guo, and Sun (Symposium on Computational Geometry, pp. 393–402, 2009) to be strongly NP-complete. Several approximation algorithms (with factors 8, 4, 3, and 2) for the minimum Manhattan problem are known. In this paper, we propose a factor 2.5 approximation algorithm for the minimum ${\mathcal{B}}$ -network problem. The algorithm employs a simplified version of the strip-staircase decomposition proposed in our paper (Chepoi et al. in Theor. Comput. Sci. 390:56–69, 2008, and APPROX-RANDOM, pp. 40–51, 2005) and subsequently used in other factor 2 approximation algorithms for the minimum Manhattan problem.     

The method of interlineation of vector functions \vec{w} (x, y, z, t) on a system of vertical straight lines and its application in crosshole seismic tomography

The authors propose a method to construct interlineation operators for vector functions $ \vec{w} $ (x, y, z, t) on a system of arbitrarily located vertical straight lines. The method allows calculating the vector $ \vec{w} $ at each point (x, y, z) between straight lines Γ _k for any instant of time t ≥ 0. They are proposed to be used to construct a crosshole accelerometer to model Earth’s crust on the basis of seismic sounding data $ {{\vec{w}}_k}\left( {z,t} \right),\,k=\overline{1,M} $ , about the vector of acceleration $ \vec{w} $ (x, y, z, t) received by accelerometers at each chink Γ _k .     

Sulle formule di quadratura di Tschebyscheff

For the Tschebyscheff quadrature formula: $$\int\limits_{ - 1}^1 {\left( {1 - x^2 } \right)^{\lambda - 1/2} f(x) dx} = K_n \sum\limits_{k = 1}^n {f(x_{n,k} )} + R_n (f), \lambda > 0$$ it is shown that the degre,N, of exactness is bounded by: $$N \leqslant C(\lambda )n^{1/(2\lambda + 1)} $$ whereC(λ) is a convenient function of λ. For λ=1 the complete solution of Tschebyscheff's problem is given.     

Arithmetizing Classes Around \textsf{NC} 1 and \textsf{L}

The parallel complexity class $\textsf{NC}$ ¹ has many equivalent models such as polynomial size formulae and bounded width branching programs. Caussinus et al. (J. Comput. Syst. Sci. 57:200–212, 1992) considered arithmetizations of two of these classes, $\textsf{\#NC}$ ¹ and $\textsf{\#BWBP}$ . We further this study to include arithmetization of other classes. In particular, we show that counting paths in branching programs over visibly pushdown automata is in $\textsf{FLogDCFL}$ , while counting proof-trees in logarithmic width formulae has the same power as $\textsf{\#NC}$ ¹. We also consider polynomial-degree restrictions of $\textsf{SC}$ ⁱ , denoted $\textsf{sSC}$ ⁱ , and show that the Boolean class $\textsf{sSC}$ ¹ is sandwiched between $\textsf{NC}$ ¹ and $\textsf{L}$ , whereas $\textsf{sSC}$ ⁰ equals $\textsf{NC}$ ¹. On the other hand, the arithmetic class $\textsf{\#sSC}$ ⁰ contains $\textsf{\#BWBP}$ and is contained in $\textsf{FL}$ , and $\textsf{\#sSC}$ ¹ contains $\textsf{\#NC}$ ¹ and is in $\textsf{SC}$ ². We also investigate some closure properties of the newly defined arithmetic classes.