165 research outputs found
Towards Blackbox Identity Testing of Log-Variate Circuits
No full textDerandomization of blackbox identity testing reduces to extremely special circuit models. After a line of work, it is known that focusing on circuits with constant-depth and constantly many variables is enough (Agrawal,Ghosh,Saxena, STOC'18) to get to general hitting-sets and circuit lower bounds. This inspires us to study circuits with few variables, eg. logarithmic in the size s.
We give the first poly(s)-time blackbox identity test for n=O(log s) variate size-s circuits that have poly(s)-dimensional partial derivative space; eg. depth-3 diagonal circuits (or Sigma wedge Sigma^n). The former model is well-studied (Nisan,Wigderson, FOCS'95) but no poly(s2^n)-time identity test was known before us. We introduce the concept of cone-closed basis isolation and prove its usefulness in studying log-variate circuits. It subsumes the previous notions of rank-concentration studied extensively in the context of ROABP models
Improved Hitting Set for Orbit of ROABPs
No full textThe orbit of an n-variate polynomial f(x) over a field is the set {f(Ax+b) ∣ A ∈ GL(n, ) and b ∈ ⁿ}, and the orbit of a polynomial class is the union of orbits of all the polynomials in it. In this paper, we give improved constructions of hitting-sets for the orbit of read-once oblivious algebraic branching programs (ROABPs) and a related model. Over fields with characteristic zero or greater than d, we construct a hitting set of size (ndw)^{O(w²log n⋅ min{w², dlog w})} for the orbit of ROABPs in unknown variable order where d is the individual degree and w is the width of ROABPs. We also give a hitting set of size (ndw)^{O(min{w²,dlog w})} for the orbit of polynomials computed by w-width ROABPs in any variable order. Our hitting sets improve upon the results of Saha and Thankey [Chandan Saha and Bhargav Thankey, 2021] who gave an (ndw)^{O(dlog w)} size hitting set for the orbit of commutative ROABPs (a subclass of any-order ROABPs) and (nw)^{O(w⁶log n)} size hitting set for the orbit of multilinear ROABPs. Designing better hitting sets in large individual degree regime, for instance d > n, was asked as an open problem by [Chandan Saha and Bhargav Thankey, 2021] and this work solves it in small width setting.
We prove some new rank concentration results by establishing low-cone concentration for the polynomials over vector spaces, and they strengthen some previously known low-support based rank concentrations shown in [Michael A. Forbes et al., 2013]. These new low-cone concentration results are crucial in our hitting set construction, and may be of independent interest. To the best of our knowledge, this is the first time when low-cone rank concentration has been used for designing hitting sets
Matroid Intersection: A Pseudo-Deterministic Parallel Reduction from Search to Weighted-Decision
No full textWe study the matroid intersection problem from the parallel complexity perspective. Given two matroids over the same ground set, the problem asks to decide whether they have a common base and its search version asks to find a common base, if one exists. Another widely studied variant is the weighted decision version where with the two matroids, we are given small weights on the ground set elements and a target weight W, and the question is to decide whether there is a common base of weight at least W. From the perspective of parallel complexity, the relation between the search and the decision versions is not well understood. We make a significant progress on this question by giving a pseudo-deterministic parallel (NC) algorithm for the search version that uses an oracle access to the weighted decision.
The notion of pseudo-deterministic NC was recently introduced by Goldwasser and Grossman [Shafi Goldwasser and Ofer Grossman, 2017], which is a relaxation of NC. A pseudo-deterministic NC algorithm for a search problem is a randomized NC algorithm that, for a given input, outputs a fixed solution with high probability. In case the given matroids are linearly representable, our result implies a pseudo-deterministic NC algorithm (without the weighted decision oracle). This resolves an open question posed by Anari and Vazirani [Nima Anari and Vijay V. Vazirani, 2020]
Border Complexity of Symbolic Determinant Under Rank One Restriction
No full textVBP is the class of polynomial families that can be computed by the determinant of a symbolic matrix of the form A_0 + ∑_{i=1}^n A_i x_i where the size of each A_i is polynomial in the number of variables (equivalently, computable by polynomial-sized algebraic branching programs (ABP)). A major open problem in geometric complexity theory (GCT) is to determine whether VBP is closed under approximation i.e. whether VBP = VBP^ ̅. The power of approximation is well understood for some restricted models of computation, e.g. the class of depth-two circuits, read-once oblivious ABPs (ROABP), monotone ABPs, depth-three circuits of bounded top fan-in, and width-two ABPs. The former three classes are known to be closed under approximation [Markus Bläser et al., 2020], whereas the approximative closure of the last one captures the entire class of polynomial families computable by polynomial-sized formulas [Bringmann et al., 2017].
In this work, we consider the subclass of VBP computed by the determinant of a symbolic matrix of the form A_0 + ∑_{i=1}^n A_i x_i where for each 1 ≤ i ≤ n, A_i is of rank one. This class has been studied extensively [Edmonds, 1968; Jack Edmonds, 1979; Murota, 1993] and efficient identity testing algorithms are known for it [Lovász, 1989; Rohit Gurjar and Thomas Thierauf, 2020]. We show that this class is closed under approximation. In the language of algebraic geometry, we show that the set obtained by taking coordinatewise products of pairs of points from (the Plücker embedding of) a Grassmannian variety is closed
Laparoscopic cholecystectomy in double gallbladder with dual pathology
No full textDouble gallbladder is a rare embryological anomaly of clinical significance. Despite availability of modern imaging, only 50% of recently reported cases had preoperative diagnosis, which is desirable in every case to avoid serious operative complications. Double pathology in double gallbladder is extremely rare with only 3 reporting′s available till date to the best of author′s knowledge. With a preoperative diagnosis of double gallbladder, laparoscopic cholecystectomy can be safely and successfully performed with meticulous dissection, aided by operative cholangiogram. However in all such attempts a lower threshold should be kept for conversion to open surgery. Awareness about this anomaly amongst radiologists and surgeons is of crucial importance. Double gallbladder does not present with any specific symptom, neither it increases disease possibility in either lobe. Prophylactic cholecystectomy has no role in asymptomatic cases diagnosed accidentally. Author reports a case of a symptomatic young male with double gallbladder who presented with short history of dyspepsia, abdominal pain and fever. Definite preoperative diagnosis was reached with ultrasound scan and magnetic resonance cholangio pancreatography and subsequently dealt with laparoscopically. Calculous cholecystitis affected one lobe and acalculous empyema the other. While the 1st lobe drained though a cystic duct into common bile duct (CBD), the 2nd was without any communication with either CBD or its counterpart, thus remained as a blind vesicle
Towards Blackbox Identity Testing of Log-Variate Circuits
No full textDerandomization of blackbox identity testing reduces to extremely special circuit models. After a line of work, it is known that focusing on circuits with constant-depth and constantly many variables is enough (Agrawal,Ghosh,Saxena, STOC'18) to get to general hitting-sets and circuit lower bounds. This inspires us to study circuits with few variables, eg. logarithmic in the size s. We give the first poly(s)-time blackbox identity test for n=O(log s) variate size-s circuits that have poly(s)-dimensional partial derivative space; eg. depth-3 diagonal circuits (or Sigma wedge Sigma^n). The former model is well-studied (Nisan,Wigderson, FOCS'95) but no poly(s2^n)-time identity test was known before us. We introduce the concept of cone-closed basis isolation and prove its usefulness in studying log-variate circuits. It subsumes the previous notions of rank-concentration studied extensively in the context of ROABP models
Implementing Tabu Search to Exploit Sparsity in ATSP Instances
No full textReal life traveling salesman problem (TSP) instances are often large,sparse, and asymmetric. Conventional tabu search implementations for the TSP that have been reported in the literature, almost always deals with small, dense and symmetric instances. In this paper, we outline data structures and a tabu search implementation that takes advantage of such data structures, which can exploit sparsity of a TSP instances, and hence can solve relatively large TSP instances (with up to 3000 nodes) much faster than conventional implementations. We also provide computational experiences with this implementation.
Investigations on the Factors Responsible for the Cytochrome C-alpha Synuclein Binding-Aggregation Landscape
No full textMachine Learning Matrix Product State Ansatz for strongly correlated systems
No full textMachine learning (ML) has been used to optimize the matrix product state (MPS) ansatz for wavefunction of strongly correlated systems. The ML optimization of MPS has been tested for Heisenberg Hamiltonian on one-dimensional and ladder lattices which correspond to conjugated molecular systems. The input descriptors and output for the supervised ML are lattice configurations and configuration interaction coefficients, respectively. Efficient learning can be achieved from data over the full Hilbert space via exact diagonalization or full configuration interaction (FCI), as well
as over a much smaller sub-space via Monte Carlo Configuration Interaction (MCCI). We show that this circumvents the need to calculate energy and operator expectation values, and is therefore, a computationally efficient alternative to variational optimization
Fast Numerical Multivariate Multipoint Evaluation
No full textWe design nearly-linear time numerical algorithms for the problem of
multivariate multipoint evaluation over the fields of rational, real and
complex numbers. We consider both \emph{exact} and \emph{approximate} versions
of the algorithm. The input to the algorithms are (1) coefficients of an
-variate polynomial with degree in each variable, and (2) points
each of whose coordinate has value bounded by one and
bit-complexity .
* Approximate version: Given additionally an accuracy parameter , the
algorithm computes rational numbers such that
for all , and has a running time of
for all and all sufficiently large .
* Exact version (when over rationals): Given additionally a bound on the
bit-complexity of all evaluations, the algorithm computes the rational numbers
, in time for all
and all sufficiently large . .
Prior to this work, a nearly-linear time algorithm for multivariate
multipoint evaluation (exact or approximate) over any infinite field appears to
be known only for the case of univariate polynomials, and was discovered in a
recent work of Moroz (FOCS 2021). In this work, we extend this result from the
univariate to the multivariate setting. However, our algorithm is based on
ideas that seem to be conceptually different from those of Moroz (FOCS 2021)
and crucially relies on a recent algorithm of Bhargava, Ghosh, Guo, Kumar &
Umans (FOCS 2022) for multivariate multipoint evaluation over finite fields,
and known efficient algorithms for the problems of rational number
reconstruction and fast Chinese remaindering in computational number theory
- …
