Search

For a polynomial $f$ from a class $\mathcal{C}$ of polynomials, we show that the problem to compute all the constant degree irreducible factors of $f$ reduces in polynomial time to polynomial identity tests (PIT) for class $\mathcal{C}$ and divisibility tests of $f$ by constant degree polynomials. We apply the result to several classes $\mathcal{C}$ and obtain the constant degree factors in \begin{enumerate} \item polynomial time, for $\mathcal{C}$ being polynomials that have only constant degree factors, \item quasipolynomial time, for $\mathcal{C}$ being sparse polynomials, \item subexponential time, for $\mathcal{C}$ being polynomials that have constant-depth circuits. \end{enumerate} Result 2 and 3 were already shown by Kumar, Ramanathan, and Saptharishi with a different proof and their time complexities necessarily depend on black-box PITs for a related bigger class $\mathcal{C}'$. Our complexities vary on whether the input is given as a blackbox or whitebox. We also show that the problem to compute the sparse factors of polynomial from a class $\mathcal{C}$ reduces in polynomial time to PIT for class $\mathcal{C}$, divisibility tests of $f$ by sparse polynomials, and irreducibility preserving bivariate projections for sparse polynomials. For $\mathcal{C}$ being sparse polynomials, it follows that it suffices to derandomize irreducibility preserving bivariate projections for sparse polynomials in order to compute all the sparse irreducible factors efficiently. When we consider factors of sparse polynomials that are sums of univariate polynomials, a subclass of sparse polynomials, we obtain a polynomial time algorithm. This was already shown by Volkovich with a different proof.

Despite recent advances in Reinforcement Learning (RL), many problems, especially real-world tasks, remain prohibitively expensive to learn. To address this issue, several lines of research have explored how tasks, or data samples themselves, can be sequenced into a curriculum to learn a problem that may otherwise be too difficult to learn from scratch. However, generating and optimizing a curriculum in a realistic scenario still requires extensive interactions with the environment. To address this challenge, we formulate the curriculum transfer problem, in which the schema of a curriculum optimized in a simpler, easy-to-solve environment (e.g., a grid world) is transferred to a complex, realistic scenario (e.g., a physics-based robotics simulation or the real world). We present "ACuTE", Automatic Curriculum Transfer from Simple to Complex Environments, a novel framework to solve this problem, and evaluate our proposed method by comparing it to other baseline approaches (e.g., domain adaptation) designed to speed up learning. We observe that our approach produces improved jumpstart and time-to-threshold performance even when adding task elements that further increase the difficulty of the realistic scenario. Finally, we demonstrate that our approach is independent of the learning algorithm used for curriculum generation, and is Sim2Real transferable to a real world scenario using a physical robot.

Regular irradiation of indoor environments with ultraviolet C (UVC) light has become a regular task for many indoor settings as a result of COVID-19, but current robotic systems attempting to automate it suffer from high costs and inefficient irradiation. In this paper, we propose a purpose-made inexpensive robotic platform with off-the-shelf components and standard navigation software that, with a novel algorithm for finding optimal irradiation locations, addresses both shortcomings to offer affordable and efficient solutions for UVC irradiation. We demonstrate in simulations the efficacy of the algorithm and show a prototypical run of the autonomous integrated robotic system in an indoor environment. In our sample instances, our proposed algorithm reduces the time needed by roughly 30\% while it increases the coverage by a factor of 35\% (when compared to the best possible placement of a static light)., Comment: Preliminary version of this paper will be published in the ICRA 2021 conference

We show that the quantum parity gate on $n > 3$ qubits cannot be cleanly simulated by a quantum circuit with two layers of arbitrary C-SIGN gates of any arity and arbitrary 1-qubit unitary gates, regardless of the number of allowed ancilla qubits. This is the best known and first nontrivial separation between the parity gate and circuits of this form. The same bounds also apply to the quantum fanout gate. Our results are incomparable with those of Fang et al. [3], which apply to any constant depth but require a sublinear number of ancilla qubits on the simulating circuit., Comment: 21 pages, 2 figures

We present a geometric approach towards derandomizing the Isolation Lemma by Mulmuley, Vazirani, and Vazirani. In particular, our approach produces a quasi-polynomial family of weights, where each weight is an integer and quasi-polynomially bounded, that can isolate a vertex in any 0/1 polytope for which each face lies in an affine space defined by a totally unimodular matrix. This includes the polytopes given by totally unimodular constraints and generalizes the recent derandomization of the Isolation Lemma for bipartite perfect matching and matroid intersection. We prove our result by associating a lattice to each face of the polytope and showing that if there is a totally unimodular kernel matrix for this lattice, then the number of vectors of length within 3/2 of the shortest vector in it is polynomially bounded. The proof of this latter geometric fact is combinatorial and follows from a polynomial bound on the number of circuits of size within 3/2 of the shortest circuit in a regular matroid. This is the technical core of the paper and relies on a variant of Seymour's decomposition theorem for regular matroids. It generalizes an influential result by Karger on the number of minimum cuts in a graph to regular matroids., Comment: Changes mainly in the introduction and abstract

We show that the bipartite perfect matching problem is in quasi-NC$^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$, and $O(log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth. We obtain our result by an almost complete derandomization of the famous Isolation Lemma when applied to yield an efficient randomized parallel algorithm for the bipartite perfect matching problem.

A read-once oblivious arithmetic branching program (ROABP) is an arithmetic branching program (ABP) where each variable occurs in at most one layer. We give the first polynomial time whitebox identity test for a polynomial computed by a sum of constantly many ROABPs. We also give a corresponding blackbox algorithm with quasi-polynomial time complexity $n^{O(\log n)}$. In both the cases, our time complexity is double exponential in the number of ROABPs. ROABPs are a generalization of set-multilinear depth-$3$ circuits. The prior results for the sum of constantly many set-multilinear depth-$3$ circuits were only slightly better than brute-force, i.e. exponential-time. Our techniques are a new interplay of three concepts for ROABP: low evaluation dimension, basis isolating weight assignment and low-support rank concentration. We relate basis isolation to rank concentration and extend it to a sum of two ROABPs using evaluation dimension (or partial derivatives)., Comment: 22 pages, Computational Complexity Conference, 2015

Graph Isomorphism is the prime example of a computational problem with a wide difference between the best known lower and upper bounds on its complexity. We bridge this gap for a natural and important special case, planar graph isomorphism, by presenting an upper bound that matches the known logspace hardness [Lindell'92]. In fact, we show the formally stronger result that planar graph canonization is in logspace. This improves the previously known upper bound of AC1 [MillerReif'91]. Our algorithm first constructs the biconnected component tree of a connected planar graph and then refines each biconnected component into a triconnected component tree. The next step is to logspace reduce the biconnected planar graph isomorphism and canonization problems to those for 3-connected planar graphs, which are known to be in logspace by [DattaLimayeNimbhorkar'08]. This is achieved by using the above decomposition, and by making significant modifications to Lindell's algorithm for tree canonization, along with changes in the space complexity analysis. The reduction from the connected case to the biconnected case requires further new ideas, including a non-trivial case analysis and a group theoretic lemma to bound the number of automorphisms of a colored 3-connected planar graph. This lemma is crucial for the reduction to work in logspace.

The isomorphism problem for planar graphs is known to be efficiently solvable. For planar 3-connected graphs, the isomorphism problem can be solved by efficient parallel algorithms, it is in the class $AC^1$. In this paper we improve the upper bound for planar 3-connected graphs to unambiguous logspace, in fact to $UL \cap coUL$. As a consequence of our method we get that the isomorphism problem for oriented graphs is in $NL$. We also show that the problems are hard for $L$.

We present quantum query complexity bounds for testing algebraic properties. For a set S and a binary operation on S, we consider the decision problem whether $S$ is a semigroup or has an identity element. If S is a monoid, we want to decide whether S is a group. We present quantum algorithms for these problems that improve the best known classical complexity bounds. In particular, we give the first application of the new quantum random walk technique by Magniez, Nayak, Roland, and Santha that improves the previous bounds by Ambainis and Szegedy. We also present several lower bounds for testing algebraic properties., Comment: 13 pages, 0 figures