BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

V. Arvind

V. Arvind appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational ComplexityDiscrete MathematicsData Structures and AlgorithmsFormal Languages and Automata Theorymath.COmath.GRquant-ph

Catalog footprint

What is connected

15works
7topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

15 published item(s)

preprint2022arXiv

Black-box Identity Testing of Noncommutative Rational Formulas of Inversion Height Two in Deterministic Quasipolynomial-time

Hrubeš and Wigderson (2015) initiated the complexity-theoretic study of noncommutative formulas with inverse gates. They introduced the Rational Identity Testing (RIT) problem which is to decide whether a noncommutative rational formula computes zero in the free skew field. In the white-box setting, deterministic polynomial-time algorithms are known for this problem following the works of Garg, Gurvits, Oliveira, and Wigderson (2016) and Ivanyos, Qiao, and Subrahmanyam (2018). A central open problem in this area is to design efficient deterministic black-box identity testing algorithm for rational formulas. In this paper, we solve this problem for the first nested inverse case. More precisely, we obtain a deterministic quasipolynomial-time black-box RIT algorithm for noncommutative rational formulas of inversion height two via a hitting set construction. Several new technical ideas are involved in the hitting set construction, including key concepts from matrix coefficient realization theory (Volčič, 2018) and properties of cyclic division algebra (Lam, 2001). En route to the proof, an important step is to embed the hitting set of Forbes and Shpilka for noncommutative formulas (2013) inside a cyclic division algebra of small index.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Matrix Polynomial Factorization via Higman Linearization

In continuation to our recent work on noncommutative polynomial factorization, we consider the factorization problem for matrices of polynomials and show the following results. (1) Given as input a full rank $d\times d$ matrix $M$ whose entries $M_{ij}$ are polynomials in the free noncommutative ring $\mathbb{F}_q\langle x_1,x_2,\ldots,x_n \rangle$, where each $M_{ij}$ is given by a noncommutative arithmetic formula of size at most $s$, we give a randomized algorithm that runs in time polynomial in $d,s, n$ and $\log_2q$ that computes a factorization of $M$ as a matrix product $M=M_1M_2\cdots M_r$, where each $d\times d$ matrix factor $M_i$ is irreducible (in a well-defined sense) and the entries of each $M_i$ are polynomials in $\mathbb{F}_q \langle x_1,x_2,\ldots,x_n \rangle$ that are output as algebraic branching programs. We also obtain a deterministic algorithm for the problem that runs in $poly(d,n,s,q)$. (2)A special case is the efficient factorization of matrices whose entries are univariate polynomials in $\mathbb{F}[x]$. When $\mathbb{F}$ is a finite field the above result applies. When $\mathbb{F}$ is the field of rationals we obtain a deterministic polynomial-time algorithm for the problem.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On Identity Testing and Noncommutative Rank Computation over the Free Skew Field

The identity testing of rational formulas (RIT) in the free skew field efficiently reduces to computing the rank of a matrix whose entries are linear polynomials in noncommuting variables\cite{HW15}. This rank computation problem has deterministic polynomial-time white-box algorithms \cite{GGOW16, IQS18} and a randomized polynomial-time algorithm in the black-box setting \cite{DM17}. In this paper, we propose a new approach for efficient derandomization of \emph{black-box} RIT. Additionally, we obtain results for matrix rank computation over the free skew field, and construct efficient linear pencil representations for a new class of rational expressions. More precisely, we show the following results: 1. Under the hardness assumption that the ABP (algebraic branching program) complexity of every polynomial identity for the $k\times k$ matrix algebra is $2^{Ω(k)}$ \cite{BW05}, we obtain a subexponential-time black-box algorithm for RIT in almost general setting. This can be seen as the first "hardness implies derandomization" type theorem for rational formulas. 2. We show that the noncommutative rank of any matrix over the free skew field whose entries have small linear pencil representations can be computed in deterministic polynomial time. Prior to this, an efficient rank computation was only known for matrices with noncommutative formulas as entries\cite{GGOW20}. As special cases of our algorithm, we obtain the first deterministic polynomial-time algorithms for rank computation of matrices whose entries are noncommutative ABPs or rational formulas. 3. Motivated by the definition given by Bergman\cite{Ber76}, we define a new class that contains noncommutative ABPs and rational formulas. We obtain a polynomial-size linear pencil representation for this class. As a by-product, we obtain a white-box deterministic polynomial-time identity testing algorithm for the class.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Equivalence Testing of Weighted Automata over Partially Commutative Monoids

We study \emph{multiplicity equivalence} testing of automata over partially commutative monoids (pc monoids) and show efficient algorithms in special cases, exploiting the structure of the underlying non-commutation graph of the monoid. Specifically, if the clique cover number of the non-commutation graph (the minimum number of cliques covering the graph) of the pc monoid is a constant, we obtain a deterministic quasi-polynomial time algorithm. As a consequence, we also obtain the first deterministic quasi-polynomial time algorithms for multiplicity equivalence testing of $k$-tape automata and for equivalence testing of deterministic $k$-tape automata for constant $k$. Prior to this, a randomized polynomial-time algorithm for the above problems was shown by Worrell [ICALP 2013]. We also consider pc monoids for which the non-commutation graphs have cover consisting of at most $k$ cliques and star graphs for any constant $k$. We obtain randomized polynomial-time algorithm for multiplicity equivalence testing of automata over such monoids.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Fast Exact Algorithms Using Hadamard Product of Polynomials

Let $C$ be an arithmetic circuit of $poly(n)$ size given as input that computes a polynomial $f\in\mathbb{F}[X]$, where $X=\{x_1,x_2,\ldots,x_n\}$ and $\mathbb{F}$ is any field where the field arithmetic can be performed efficiently. We obtain new algorithms for the following two problems first studied by Koutis and Williams \cite{Kou08, Wi09, KW16}. k-MLC: Compute the sum of the coefficients of all degree-$k$ multilinear monomials in the polynomial $f$. k-MMD: Test if there is a nonzero degree-$k$ multilinear monomial in the polynomial $f$. Our algorithms are based on the fact that the Hadamard product $f\circ S_{n,k}$, is the degree-$k$ multilinear part of $f$, where $S_{n,k}$ is the $k^{th}$ elementary symmetric polynomial. 1. For k-MLC problem, we give a deterministic algorithm of run time $O^*(n^{k/2+c\log k})$ (where $c$ is a constant), answering an open question of Koutis and Williams \cite[ICALP'09]{KW16}. As corollaries, we show $O^*(\binom{n}{\downarrow k/2})$-time exact counting algorithms for several combinatorial problems: k-Tree, t-Dominating Set, m-Dimensional k-Matching. 2. For k-MMD problem, we give a randomized algorithm of run time $4.32^k\cdot poly(n,k)$. Our algorithm uses only $poly(n,k)$ space. This matches the run time of a recent algorithm \cite{BDH18} for $k-MMD$ which requires exponential (in $k$) space. Other results include fast deterministic algorithms for k-MLC and k-MMD problems for depth three circuits.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the Weisfeiler-Leman Dimension of Fractional Packing

The $k$-dimensional Weisfeiler-Leman procedure ($k$-WL), which colors $k$-tuples of vertices in rounds based on the neighborhood structure in the graph, has proven to be immensely fruitful in the algorithmic study of Graph Isomorphism. More generally, it is of fundamental importance in understanding and exploiting symmetries in graphs in various settings. Two graphs are $k$-WL-equivalent if the $k$-dimensional Weisfeiler-Leman procedure produces the same final coloring on both graphs. 1-WL-equivalence is known as fractional isomorphism of graphs, and the $k$-WL-equivalence relation becomes finer as $k$ increases. We investigate to what extent standard graph parameters are preserved by $k$-WL-equivalence, focusing on fractional graph packing numbers. The integral packing numbers are typically NP-hard to compute, and we discuss applicability of $k$-WL-invariance for estimating the integrality gap of the LP relaxation provided by their fractional counterparts.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Randomized Polynomial Time Identity Testing for Noncommutative Circuits

In this paper we show that the black-box polynomial identity testing for noncommutative polynomials $f\in\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$ of degree $D$ and sparsity $t$, can be done in randomized $\poly(n,\log t,\log D)$ time. As a consequence, if the black-box contains a circuit $C$ of size $s$ computing $f\in\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$ which has at most $t$ non-zero monomials, then the identity testing can be done by a randomized algorithm with running time polynomial in $s$ and $n$ and $\log t$. This makes significant progress on a question that has been open for over ten years. The earlier result by Bogdanov and Wee [BW05], using the classical Amitsur-Levitski theorem, gives a randomized polynomial-time algorithm only for circuits of polynomially bounded syntactic degree. In our result, we place no restriction on the degree of the circuit. Our algorithm is based on automata-theoretic ideas introduced in [AMS08,AM08]. In those papers, the main idea was to construct deterministic finite automata that isolate a single monomial from the set of nonzero monomials of a polynomial $f$ in $\mathbb{F}\langle z_1,z_2,\cdots,z_n \rangle$. In the present paper, since we need to deal with exponential degree monomials, we carry out a different kind of monomial isolation using nondeterministic automata.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs

In this paper we study the complexity of the following problems: Given a colored graph X=(V,E,c), compute a minimum cardinality set S of vertices such that no nontrivial automorphism of X fixes all vertices in S. A closely related problem is computing a minimum base S for a permutation group G on [n] given by generators, i.e., a minimum cardinality subset S of [n] such that no nontrivial permutation in G fixes all elements of S. Our focus is mainly on the parameterized complexity of these problems. We show that when k=|S| is treated as parameter, then both problems are MINI[1]-hard. For the dual problems, where k=n-|S| is the parameter, we give FPT algorithms. A notion closely related to fixing is called individualization. Individualization combined with the Weisfeiler-Leman procedure is a fundamental technique in algorithms for Graph Isomorphism. Motivated by the power of individualization, in the present paper we explore the complexity of individualization: what is the minimum number of vertices we need to individualize in a given graph such that color refinement "succeeds" on it. Here "succeeds" could have different interpretations, and we consider the following: It could mean the individualized graph becomes: (a) discrete, (b) amenable, (c) compact, or (d) refinable. In particular, we study the parameterized versions of these problems where the parameter is the number of vertices individualized. We show a dichotomy: For graphs with color classes of size at most 3 these problems can be solved in polynomial time (even in logspace), while starting from color class size 4 they become W[P]-hard.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Graph Isomorphism, Color Refinement, and Compactness

Color refinement is a classical technique used to show that two given graphs G and H are non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a graph G amenable to color refinement if it succeeds in distinguishing G from any non-isomorphic graph H. Tinhofer (1991) explored a linear programming approach to Graph Isomorphism and defined compact graphs: A graph is compact if its fractional automorphisms polytope is integral. Tinhofer noted that isomorphism testing for compact graphs can be done quite efficiently by linear programming. However, the problem of characterizing and recognizing compact graphs in polynomial time remains an open question. Our results are summarized below: - We show that amenable graphs are recognizable in time O((n + m)logn), where n and m denote the number of vertices and the number of edges in the input graph. - We show that all amenable graphs are compact. - We study related combinatorial and algebraic graph properties introduced by Tinhofer and Godsil. The corresponding classes of graphs form a hierarchy and we prove that recognizing each of these graph classes is P-hard. In particular, this gives a first complexity lower bound for recognizing compact graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Noncommutative Valiant's Classes: Structure and Complete Problems

In this paper we explore the noncommutative analogues, $\mathrm{VP}_{nc}$ and $\mathrm{VNP}_{nc}$, of Valiant's algebraic complexity classes and show some striking connections to classical formal language theory. Our main results are the following: (1) We show that Dyck polynomials (defined from the Dyck languages of formal language theory) are complete for the class $\mathrm{VP}_{nc}$ under $\le_{abp}$ reductions. Likewise, it turns out that $\mathrm{PAL}$ (Palindrome polynomials defined from palindromes) are complete for the class $\mathrm{VSKEW}_{nc}$ (defined by polynomial-size skew circuits) under $\le_{abp}$ reductions. The proof of these results is by suitably adapting the classical Chomsky-Schützenberger theorem showing that Dyck languages are the hardest CFLs. (2) Next, we consider the class $\mathrm{VNP}_{nc}$. It is known~\cite{HWY10a} that, assuming the sum-of-squares conjecture, the noncommutative polynomial $\sum_{w\in\{x_0,x_1\}^n}ww$ requires exponential size circuits. We unconditionally show that $\sum_{w\in\{x_0,x_1\}^n}ww$ is not $\mathrm{VNP}_{nc}$-complete under the projection reducibility. As a consequence, assuming the sum-of-squares conjecture, we exhibit a strictly infinite hierarchy of p-families under projections inside $\mathrm{VNP}_{nc}$ (analogous to Ladner's theorem~\cite{Ladner75}). In the final section we discuss some new $\mathrm{VNP}_{nc}$-complete problems under $\le_{abp}$-reductions. (3) Inside $\mathrm{VP}_{nc}$ too we show there is a strict hierarchy of p-families (based on the nesting depth of Dyck polynomials) under the $\le_{abp}$ reducibility.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Complexity of Noncommutative Polynomial Factorization

In this paper we study the complexity of factorization of polynomials in the free noncommutative ring $\mathbb{F}\langle x_1,x_2,\dots,x_n\rangle$ of polynomials over the field $\mathbb{F}$ and noncommuting variables $x_1,x_2,\ldots,x_n$. Our main results are the following. Although $\mathbb{F}\langle x_1,x_2,\dots,x_n \rangle$ is not a unique factorization ring, we note that variable-disjoint factorization in $\mathbb{F}\langle x_1,x_2,\dots,x_n \rangle$ has the uniqueness property. Furthermore, we prove that computing the variable-disjoint factorization is polynomial-time equivalent to Polynomial Identity Testing (both when the input polynomial is given by an arithmetic circuit or an algebraic branching program). We also show that variable-disjoint factorization in the black-box setting can be efficiently computed (where the factors computed will be also given by black-boxes, analogous to the work [KT91] in the commutative setting). As a consequence of the previous result we show that homogeneous noncommutative polynomials and multilinear noncommutative polynomials have unique factorizations in the usual sense, which can be efficiently computed. Finally, we discuss a polynomial decomposition problem in $\mathbb{F}\langle x_1,x_2,\dots,x_n\rangle$ which is a natural generalization of homogeneous polynomial factorization and prove some complexity bounds for it.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Some Lower Bound Results for Set-Multilinear Arithmetic Computations

In this paper, we study the structure of set-multilinear arithmetic circuits and set-multilinear branching programs with the aim of showing lower bound results. We define some natural restrictions of these models for which we are able to show lower bound results. Some of our results extend existing lower bounds, while others are new and raise open questions. More specifically, our main results are the following: (1) We observe that set-multilinear arithmetic circuits can be transformed into shallow set-multilinear circuits efficiently, similar to depth reduction results of [VSBR83,RY08] for more general commutative circuits. As a consequence, we note that polynomial size set-multilinear circuits have quasi-polynomial size set-multilinear branching programs. We show that \emph{narrow} set-multilinear ABPs (with a restricted number of set types) computing the Permanent polynomial $\mathrm{PER}_n$ require $2^{n^{Ω(1)}}$ size. A similar result for general set-multilinear ABPs appears difficult as it would imply that the Permanent requires superpolynomial size set-multilinear circuits. It would also imply that the noncommutative Permanent requires superpolynomial size noncommutative arithmetic circuits. (2) Indeed, we also show that set-multilinear branching programs are exponentially more powerful than \emph{interval} multilinear circuits (where the index sets for each gate is restricted to be an interval w.r.t.\ some ordering), assuming the sum-of-squares conjecture. This further underlines the power of set-multilinear branching programs. (3) Finally, we consider set-multilinear circuits with restrictions on the number of proof trees of monomials computed by it, and prove exponential lower bounds results. This raises some new lower bound questions.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Near-Optimal Expanding Generating Sets for Solvable Permutation Groups

Let $G =<S>$ be a solvable permutation group of the symmetric group $S_n$ given as input by the generating set $S$. We give a deterministic polynomial-time algorithm that computes an \emph{expanding generating set} of size $\tilde{O}(n^2)$ for $G$. More precisely, the algorithm computes a subset $T\subset G$ of size $\tilde{O}(n^2)(1/λ)^{O(1)}$ such that the undirected Cayley graph $Cay(G,T)$ is a $λ$-spectral expander (the $\tilde{O}$ notation suppresses $\log ^{O(1)}n$ factors). As a byproduct of our proof, we get a new explicit construction of $\varepsilon$-bias spaces of size $\tilde{O}(n\poly(\log d))(\frac{1}{\varepsilon})^{O(1)}$ for the groups $\Z_d^n$. The earlier known size bound was $O((d+n/\varepsilon^2))^{11/2}$ given by \cite{AMN98}.

0 citations0 reviewsNo code linkedOpen access
preprint2002arXiv

The Quantum Query Complexity of 0-1 Knapsack and Associated Claw Problems

We first give an $Ø(2^{n/3})$ quantum algorithm for the 0-1 Knapsack problem with $n$ variables. More generally, for 0-1 Integer Linear Programs with $n$ variables and $d$ inequalities we give an $Ø(2^{n/3}n^d)$ quantum algorithm. For $d =o(n/\log n)$ this running time is bounded by $Ø(2^{n(1/3+ε)})$ for every $ε>0$ and in particular it is better than the $Ø(2^{n/2})$ upper bound for general quantum search. To investigate whether better algorithms for these NP-hard problems are possible, we formulate a \emph{symmetric} claw problem corresponding to 0-1 Knapsack and study its quantum query complexity. For the symmetric claw problem we establish a lower bound of $Ø(2^{n/4})$ for its quantum query complexity. We have an $Ø(2^{n/3})$ upper bound given by essentially the same quantum algorithm that works for Knapsack. Additionally, we consider CNF satisfiability of CNF formulas $F$ with no restrictions on clause size, but with the number of clauses in $F$ bounded by $cn$ for a constant $c$, where $n$ is the number of variables. We give a $2^{(1-α)n/2}$ quantum algorithm for satisfiability in this case, where $α$ is a constant depending on $c$.

0 citations0 reviewsNo code linkedOpen access