9,058 research outputs found
Impact of strain on the design of low-power high-speed circuits
No full textIn this article, we explore the impact of strain on circuit performance when strained silicon (s-Si) devices are used for designing low-power high-speed circuits. Emphasis has been given on the evaluation of noise characteristics and low-power performance along with the delay characteristics under different channel straining conditions. An inverter circuit has been used for performance evaluation through simulation where the device simulator is calibrated with experimental device data. The result shows a great promise for s-Si technology in digital applications which require high throughput and low power
Recommended from our members
Fractional Pseudorandom Generators from Any Fourier Level
No full textWe prove new results on the polarizing random walk framework introduced in recent works of Chattopadhyay et al. [Chattopadhyay et al., 2019; Eshan Chattopadhyay et al., 2019] that exploit L₁ Fourier tail bounds for classes of Boolean functions to construct pseudorandom generators (PRGs). We show that given a bound on the k-th level of the Fourier spectrum, one can construct a PRG with a seed length whose quality scales with k. This interpolates previous works, which either require Fourier bounds on all levels [Chattopadhyay et al., 2019], or have polynomial dependence on the error parameter in the seed length [Eshan Chattopadhyay et al., 2019], and thus answers an open question in [Eshan Chattopadhyay et al., 2019]. As an example, we show that for polynomial error, Fourier bounds on the first O(log n) levels is sufficient to recover the seed length in [Chattopadhyay et al., 2019], which requires bounds on the entire tail.
We obtain our results by an alternate analysis of fractional PRGs using Taylor’s theorem and bounding the degree-k Lagrange remainder term using multilinearity and random restrictions. Interestingly, our analysis relies only on the level-k unsigned Fourier sum, which is potentially a much smaller quantity than the L₁ notion in previous works. By generalizing a connection established in [Chattopadhyay et al., 2020], we give a new reduction from constructing PRGs to proving correlation bounds. Finally, using these improvements we show how to obtain a PRG for ₂ polynomials with seed length close to the state-of-the-art construction due to Viola [Emanuele Viola, 2009]
Paracladopelma aratrum Chaudhuri et Chattopadhyay
No full text<i>Paracladopelma aratrum</i> Chaudhuri <i>et</i> Chattopadhyay <p>(Figs 1–2)</p> <p> <i>Paracladopelma aratra</i> Chaudhuri <i>et</i> Chattopadhyay, 1990: 160.</p> <p> <b>Material examined:</b> Holotype male (EB), <b>INDIA:</b> West Bengal, Bally, 27.vii.1986, S. Chattopadhyay. <b>Diagnostic characters.</b> The species differs from other <i>Paracladopelma</i> species by the absence of frontal tubercles and the plough-like superior volsella bearing 2 setae in outer margin and covered with microtrichia. <b>Male.</b> Description as in Chaudhuri and Chattopadhyay (1990: 160, fig. 26–28) with the following corrections: eyes with long parallel-sided dorsomedial extension; superior volsella plough-shaped, outer margin with 2 setae, covered with microtrichia; inferior volsella with small rounded lobe, covered with microtrichia. The hypopygium of the holotype is re-drawn in Figures 1–2.</p> <p> <b>Distribution.</b> The species is recorded from India.</p>Published as part of <i>Yan, Chuncai, Jin, Zhaohui & Wang, Xinhua, 2008, Paracladopelma Harnisch from the Sino-Indian Region (Diptera: Chironomidae), pp. 1-29 in Zootaxa 1934</i> on page 5, DOI: <a href="http://zenodo.org/record/184929">10.5281/zenodo.184929</a>
Lifting to Parity Decision Trees Via Stifling
No full textWe show that the deterministic decision tree complexity of a (partial)
function or relation lifts to the deterministic parity decision tree (PDT)
size complexity of the composed function/relation as long as the
gadget satisfies a property that we call stifling. We observe that several
simple gadgets of constant size, like Indexing on 3 input bits, Inner Product
on 4 input bits, Majority on 3 input bits and random functions, satisfy this
property. It can be shown that existing randomized communication lifting
theorems ([G\"{o}\"{o}s, Pitassi, Watson. SICOMP'20], [Chattopadhyay et al.
SICOMP'21]) imply PDT-size lifting. However there are two shortcomings of this
approach: first they lift randomized decision tree complexity of , which
could be exponentially smaller than its deterministic counterpart when either
is a partial function or even a total search problem. Second, the size of
the gadgets in such lifting theorems are as large as logarithmic in the size of
the input to . Reducing the gadget size to a constant is an important open
problem at the frontier of current research.
Our result shows that even a random constant-size gadget does enable lifting
to PDT size. Further, it also yields the first systematic way of turning lower
bounds on the width of tree-like resolution proofs of the unsatisfiability of
constant-width CNF formulas to lower bounds on the size of tree-like proofs in
the resolution with parity system, i.e., (), of the
unsatisfiability of closely related constant-width CNF formulas
Recommended from our members
Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates
No full textA recent work of Chattopadhyay et al. (CCC 2018) introduced a new framework for the design of pseudorandom generators for Boolean functions. It works under the assumption that the Fourier tails of the Boolean functions are uniformly bounded for all levels by an exponential function. In this work, we design an alternative pseudorandom generator that only requires bounds on the second level of the Fourier tails. It is based on a derandomization of the work of Raz and Tal (ECCC 2018) who used the above framework to obtain an oracle separation between BQP and PH.
As an application, we give a concrete conjecture for bounds on the second level of the Fourier tails for low degree polynomials over the finite field F_2. If true, it would imply an efficient pseudorandom generator for AC^0[oplus], a well-known open problem in complexity theory. As a stepping stone towards resolving this conjecture, we prove such bounds for the first level of the Fourier tails
Respiratory health status and its predictors: a cross-sectional study among coal-based sponge iron plant workers in Barjora, India.
No full textOBJECTIVES: During the past decade, coal-based sponge iron plants, a highly polluted industry, have grown rapidly in Barjora, India. The toxic effects of particulate matters and gaseous pollutants include various respiratory diseases. Understanding workers' perception of respiratory health is essential in people-centred healthcare. The aim of the study was to assess their respiratory health status and to determine its predictors. DESIGN: Cross-sectional study. SETTING: Coal-based sponge iron plants in Barjora, India. PARTICIPANTS: 258 coal-based sponge iron plant workers. PRIMARY OUTCOME MEASURE: Respiratory health status was measured using the St. George's respiratory questionnaire (SGRQ) total score. 100 and 0 represent the worst and best possible respiratory health status, respectively. STATISTICAL ANALYSES: The two-part model (frequency (any worse respiratory health status) and severity (amount of worse respiratory health status)) was developed for the score, as the data were positively skewed with many zeros. RESULTS: The mean (SD) SGRQ total score was 7.7 (14.5), the median (IQR) was 0.9 (9.0), and the observed range was 0-86.6. The best possible SGRQ total score was reported by 46.9% of workers. Independent predictors of worse respiratory health status were cleaner domestic cooking fuel (coefficient -0.76, 95% CI -1.46 to -0.06, p=0.034) and personal history of any respiratory disease (1.76, 1.04 to 2.47, p<0.001) in case of frequency; and family history of any respiratory disease (0.43, 0.02 to 0.83, p=0.039) and personal history (1.19, 0.83 to 1.54, p<0.001) in case of severity. CONCLUSIONS: Less than half of the coal-based sponge iron plant workers in Barjora have the best possible respiratory health status. The predictors of worse respiratory health status were identified. The study findings could be taken into consideration in future interventional studies aimed at improving the respiratory health status of these workers
Monotone Complexity of Spanning Tree Polynomial Re-Visited
No full textWe prove two results that shed new light on the monotone complexity of the spanning tree polynomial, a classic polynomial in algebraic complexity and beyond.
First, we show that the spanning tree polynomials having n variables and defined over constant-degree expander graphs, have monotone arithmetic complexity 2^{Ω(n)}. This yields the first strongly exponential lower bound on monotone arithmetic circuit complexity for a polynomial in VP. Before this result, strongly exponential size monotone lower bounds were known only for explicit polynomials in VNP [S. B. Gashkov and I. S. Sergeev, 2012; Ran Raz and Amir Yehudayoff, 2011; Srikanth Srinivasan, 2020; Bruno Pasqualotto Cavalar et al., 2020; Pavel Hrubeš and Amir Yehudayoff, 2021].
Recently, Hrubeš [Pavel Hrubeš, 2020] initiated a program to prove lower bounds against general arithmetic circuits by proving ε-sensitive lower bounds for monotone arithmetic circuits for a specific range of values for ε ∈ (0,1). The first ε-sensitive lower bound was just proved for a family of polynomials inside VNP by Chattopadhyay, Datta and Mukhopadhyay [Arkadev Chattopadhyay et al., 2021]. We consider the spanning tree polynomial ST_n defined over the complete graph of n vertices and show that the polynomials F_{n-1,n} - ε⋅ ST_{n} and F_{n-1,n} + ε⋅ ST_{n}, defined over (n-1)n variables, have monotone circuit complexity 2^{Ω(n)} if ε ≥ 2^{- Ω(n)} and F_{n-1,n} := ∏_{i = 2}ⁿ (x_{i,1} + ⋯ + x_{i,n}) is the complete set-multilinear polynomial. This provides the first ε-sensitive exponential lower bound for a family of polynomials inside VP. En-route, we consider a problem in 2-party, best partition communication complexity of deciding whether two sets of oriented edges distributed among Alice and Bob form a spanning tree or not. We prove that there exists a fixed distribution, under which the problem has low discrepancy with respect to every nearly-balanced partition. This result could be of interest beyond algebraic complexity.
Our two results, thus, are incomparable generalizations of the well known result by Jerrum and Snir [Mark Jerrum and Marc Snir, 1982] which showed that the spanning tree polynomial, defined over complete graphs with n vertices (so the number of variables is (n-1)n), has monotone complexity 2^{Ω(n)}. In particular, the first result is an optimal lower bound and the second result can be thought of as a robust version of the earlier monotone lower bound for the spanning tree polynomial
- …
