114 research outputs found
Deterministic Identity Testing Paradigms for Bounded Top-Fanin Depth-4 Circuits
Get PDFPolynomial Identity Testing (PIT) is a fundamental computational problem. The famous depth-4 reduction (Agrawal & Vinay, FOCS'08) has made PIT for depth-4 circuits, an enticing pursuit. The largely open special-cases of sum-product-of-sum-of-univariates (Σ^[k] Π Σ ∧) and sum-product-of-constant-degree-polynomials (Σ^[k] Π Σ Π^[δ]), for constants k, δ, have been a source of many great ideas in the last two decades. For eg. depth-3 ideas (Dvir & Shpilka, STOC'05; Kayal & Saxena, CCC'06; Saxena & Seshadhri, FOCS'10, STOC'11); depth-4 ideas (Beecken, Mittmann & Saxena, ICALP'11; Saha,Saxena & Saptharishi, Comput.Compl.'13; Forbes, FOCS'15; Kumar & Saraf, CCC'16); geometric Sylvester-Gallai ideas (Kayal & Saraf, FOCS'09; Shpilka, STOC'19; Peleg & Shpilka, CCC'20, STOC'21). We solve two of the basic underlying open problems in this work.
We give the first polynomial-time PIT for Σ^[k] Π Σ ∧. Further, we give the first quasipolynomial time blackbox PIT for both Σ^[k] Π Σ ∧ and Σ^[k] Π Σ Π^[δ]. No subexponential time algorithm was known prior to this work (even if k = δ = 3). A key technical ingredient in all the three algorithms is how the logarithmic derivative, and its power-series, modify the top Π-gate to ∧
Algebraic Independence over Positive Characteristic: New Criterion and Applications to Locally Low Algebraic Rank Circuits
Get PDFThe motivation for this work comes from two problems--test algebraic independence of arithmetic circuits over a field of small characteristic, and generalize the structural property of algebraic dependence used by (Kumar, Saraf CCC'16) to arbitrary fields.
It is known that in the case of zero, or large characteristic, using a classical criterion based on the Jacobian, we get a randomized poly-time algorithm to test algebraic independence. Over small characteristic, the Jacobian criterion fails and there is no subexponential time algorithm known. This problem could well be conjectured to be in RP, but the current best algorithm puts it in NP^#P (Mittmann, Saxena, Scheiblechner Trans.AMS'14). Currently, even the case of two bivariate circuits over F_2 is open. We come up with a natural generalization of Jacobian criterion, that works over all characteristic. The new criterion is efficient if the underlying inseparable degree is promised to be a constant. This is a modest step towards the open question of fast independence testing, over finite fields, posed in (Dvir, Gabizon, Wigderson FOCS'07).
In a set of linearly dependent polynomials, any polynomial can be written as a linear combination of the polynomials forming a basis. The analogous property for algebraic dependence is false, but a property approximately in that spirit is named as ``functional dependence'' in (Kumar, Saraf CCC'16) and proved for zero or large characteristic. We show that functional dependence holds for arbitrary fields, thereby answering the open questions in (Kumar, Saraf CCC'16). Following them we use the functional dependence lemma to prove the first exponential lower bound for locally low algebraic rank circuits for arbitrary fields (a model that strongly generalizes homogeneous depth-4 circuits). We also recover their quasipoly-time hitting-set for such models, for fields of characteristic smaller than the ones known before.
Our results show that approximate functional dependence is indeed a more fundamental concept than the Jacobian as it is field independent. We achieve the former by first picking a ``good'' transcendence basis, then translating the circuits by new variables, and finally approximating them by truncating higher degree monomials. We give a tight analysis of the ``degree'' of approximation needed in the criterion. To get the locally low algebraic rank circuit applications we follow the known shifted partial derivative based methods
Algebraic Independence over Positive Characteristic: {N}ew Criterion and Applications to Locally Low Algebraic Rank Circuits
No full textThe motivation for this work (Pandey et al. 2016) comes from two problems: testing algebraic independence of arithmetic circuits over a field of small characteristic and generalizing the structural property of algebraic dependence used by Kumar, Saraf, CCC’16 to arbitrary fields. It is known that in the case of zero, or large characteristic, using a classical criterion based on the Jacobian, we get a randomized poly-time algorithm to test algebraic independence. Over small characteristic, the Jacobian criterion fails and there is no subexponential time algorithm known. This problem could well be conjectured to be in RP, but the current best algorithm puts it in NP (Mittmann, Saxena, Scheiblechner, Trans.AMS’14). Currently, even the case of two bivariate circuits over is open. We come up with a natural generalization of Jacobian criterion that works over all characteristics. The new criterion is efficient if the underlying inseparable degree is promised to be a constant. This is a modest step toward the open question of fast independence testing, over finite fields, posed in (Dvir, Gabizon, Wigderson, FOCS’07). In a set of linearly dependent polynomials, any polynomial can be written as a linear combination of the polynomials forming a basis. The analogous property for algebraic dependence is false, but a property approximately in that spirit is named as “functional dependence” in Kumar, Saraf, CCC’16 and proved for zero or large characteristics. We show that functional dependence holds for arbitrary fields, thereby answering the open questions in Kumar, Saraf, CCC’16. Following them, we use the functional dependence lemma to prove the first exponential lower bound for locally low algebraic rank circuits for arbitrary fields (a model that strongly generalizes homogeneous depth-4 circuits). We also recover their quasipoly-time hitting-set for such models, for fields of characteristic smaller than the ones known before. Our results show that approximate functional dependence is indeed a more fundamental concept than the Jacobian as it is field independent. We achieve the former by first picking a “good” transcendence basis, then translating the circuits by new variables, and finally approximating them by truncating higher degree monomials. We give a tight analysis of the “degree” of approximation needed in the criterion. To get the locally low-algebraic-rank circuit applications, we follow the known shifted partial derivative-based methods
Algebraic Independence over Positive Characteristic: New Criterion and Applications to Locally Low Algebraic Rank Circuits
No full textThe motivation for this work comes from two problems--test algebraic independence of arithmetic circuits over a field of small characteristic, and generalize the structural property of algebraic dependence used by (Kumar, Saraf CCC'16) to arbitrary fields. It is known that in the case of zero, or large characteristic, using a classical criterion based on the Jacobian, we get a randomized poly-time algorithm to test algebraic independence. Over small characteristic, the Jacobian criterion fails and there is no subexponential time algorithm known. This problem could well be conjectured to be in RP, but the current best algorithm puts it in NP^#P (Mittmann, Saxena, Scheiblechner Trans.AMS'14). Currently, even the case of two bivariate circuits over F_2 is open. We come up with a natural generalization of Jacobian criterion, that works over all characteristic. The new criterion is efficient if the underlying inseparable degree is promised to be a constant. This is a modest step towards the open question of fast independence testing, over finite fields, posed in (Dvir, Gabizon, Wigderson FOCS'07). In a set of linearly dependent polynomials, any polynomial can be written as a linear combination of the polynomials forming a basis. The analogous property for algebraic dependence is false, but a property approximately in that spirit is named as ``functional dependence'' in (Kumar, Saraf CCC'16) and proved for zero or large characteristic. We show that functional dependence holds for arbitrary fields, thereby answering the open questions in (Kumar, Saraf CCC'16). Following them we use the functional dependence lemma to prove the first exponential lower bound for locally low algebraic rank circuits for arbitrary fields (a model that strongly generalizes homogeneous depth-4 circuits). We also recover their quasipoly-time hitting-set for such models, for fields of characteristic smaller than the ones known before. Our results show that approximate functional dependence is indeed a more fundamental concept than the Jacobian as it is field independent. We achieve the former by first picking a ``good'' transcendence basis, then translating the circuits by new variables, and finally approximating them by truncating higher degree monomials. We give a tight analysis of the ``degree'' of approximation needed in the criterion. To get the locally low algebraic rank circuit applications we follow the known shifted partial derivative based methods
Cost based reactive power participation for voltage control in multi units based isolated hybrid power system
No full textAbstractMulti units of wind and diesel based generators in isolated hybrid power system have technical and operational advantages over single units system. They require dynamic reactive power compensation for fast recovery of voltage under load and input changes. In developing countries like India, investors’ prime concern is to provide continuous electricity at low rate while quality degradation can be permitted within pre defined acceptable range. The use of static compensator along with dynamic compensator may give cost effective reactive power participation for system. This paper presented pricing of reactive power compensation under steady state and transient conditions of system with fixed capacitor and STATCOM. The main contributions of the paper are; (i) evaluating reactive power balance equation for generalized multi units of wind and diesel based isolated hybrid power system, (ii) reactive power compensation using fixed capacitor and STATCOM in presence of composite load model, (ii) fast recovery of voltage response using genetic algorithm based tuning of STATCOM controller, (iii) evaluation of reactive power compensation cost for steady and dynamic conditions due to probabilistic change in load and/or input demand and (iv) comparison of results with existing reference compensation method
An EOQ model of time quadratic and inventory dependent demand for deteriorated items with partially backlogged shortages under trade credit
No full textIndia's policy pathways
No full textEpisode two of Policy Pathways explores how Indian development policy can be adapted to mitigate the impacts of climate change and support marginalized communities.
Join host Chhavi Sachdev as she interviews the CGIAR's National Policies and Strategies (NPS) lead report author for India Archisman Mitra, Nitin Bassi Senior Program lead at the Council on Energy Environment and Water, and Parijat Ghosh, Research and Advocacy Team Coordinator at Professional Assistance for Development Action (PRADAN).
The episode also features remarks on the NPS report from Dr. Arabinda Kumar Padhee; Principal Secretary at the Department of Agriculture and Farmers' Empowerment, Government of Odisha
Reactive power control in decentralized hybrid power system with STATCOM using GA, ANN and ANFIS methods
No full text- …
