BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Partha Mukhopadhyay

Partha Mukhopadhyay contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
hep-thComputational ComplexityData Structures and AlgorithmsDiscrete MathematicsFormal Languages and Automata Theoryquant-ph

Trust snapshot

Quick read

Trust 21 - EmergingVerification L1Unclaimed author
14works
0followers
6topics
4close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

14 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

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
preprint2013arXiv

Depth-4 Lower Bounds, Determinantal Complexity : A Unified Approach

Tavenas has recently proved that any n^{O(1)}-variate and degree n polynomial in VP can be computed by a depth-4 circuit of size 2^{O(\sqrt{n}\log n)}. So to prove VP not equal to VNP, it is sufficient to show that an explicit polynomial in VNP of degree n requires 2^{ω(\sqrt{n}\log n)} size depth-4 circuits. Soon after Tavenas's result, for two different explicit polynomials, depth-4 circuit size lower bounds of 2^{Ω(\sqrt{n}\log n)} have been proved Kayal et al. and Fournier et al. In particular, using combinatorial design Kayal et al.\ construct an explicit polynomial in VNP that requires depth-4 circuits of size 2^{Ω(\sqrt{n}\log n)} and Fournier et al.\ show that iterated matrix multiplication polynomial (which is in VP) also requires 2^{Ω(\sqrt{n}\log n)} size depth-4 circuits. In this paper, we identify a simple combinatorial property such that any polynomial f that satisfies the property would achieve similar circuit size lower bound for depth-4 circuits. In particular, it does not matter whether f is in VP or in VNP. As a result, we get a very simple unified lower bound analysis for the above mentioned polynomials. Another goal of this paper is to compare between our current knowledge of depth-4 circuit size lower bounds and determinantal complexity lower bounds. We prove the that the determinantal complexity of iterated matrix multiplication polynomial is Ω(dn) where d is the number of matrices and n is the dimension of the matrices. So for d=n, we get that the iterated matrix multiplication polynomial achieves the current best known lower bounds in both fronts: depth-4 circuit size and determinantal complexity. To the best of our knowledge, a Θ(n) bound for the determinantal complexity for the iterated matrix multiplication polynomial was known only for constant d>1 by Jansen.

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
preprint2012arXiv

On a semi-classical limit of loop space quantum mechanics

Following earlier work, we view two dimensional non-linear sigma model with target space $\cM$ as a single particle relativistic quantum mechanics in the corresponding free loop space $\cLM$. In a natural semi-classical limit ($\hbar=α&#39; \to 0$) of this model the wavefunction localizes on the submanifold of vanishing loops which is isomorphic to $\cM$. One would expect that the relevant semi-classical expansion should be related to the tubular expansion of the theory around the submanifold and an effective dynamics on the submanifold is obtainable using Born-Oppenheimer approximation. In this work we develop a framework to carry out such an analysis at the leading order in $α&#39;$-expansion. In particular, we show that the linearized tachyon effective equation is correctly reproduced up to divergent terms all proportional to the Ricci scalar of $\cM$. The steps leading to this result are as follows: first we define a finite dimensional analogue of the loop space quantum mechanics (LSQM) where we discuss its tubular expansion and how that is related to a semi-classical expansion of the Hamiltonian. Then we study an explicit construction of the relevant tubular neighborhood in $\cLM$ using exponential maps. Such a tubular geometry is obtained from a Riemannian structure on the tangent bundle of $\cM$ which views the zero-section as a submanifold admitting a tubular neighborhood. Using this result and exploiting an analogy with the toy model we arrive at the final result for LSQM.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

DeWitt-Virasoro construction

We study a particular approach for analyzing worldsheet conformal invariance for bosonic string propagating in a curved background using hamiltonian formalism. We work in the Schrodinger picture of a single particle description of the problem where the particle moves in an infinite-dimensional space. Background independence is maintained in this approach by adopting DeWitt&#39;s (Phys.Rev.85:653-661,1952) coordinate independent formulation of quantum mechanics. This enables us to construct certain background independent notion of Virasoro generators, called DeWitt-Virasoro (DWV) generators, and invariant matrix elements of an arbitrary operator constructed out of them in spin-zero representation. We show that the DWV algebra is given by the Witt algebra with additional anomalous terms that vanish for Ricci-flat backgrounds. The actual quantum Virasoro generators should be obtained by first introducing the vacuum state and then normal ordering the DWV generators with respect to that. We demonstrate the procedure in the simple cases of flat and pp-wave backgrounds. This is a shorter version of arXiv:0912.3987 [hep-th] with many technical derivations omitted.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

DeWitt-Virasoro construction in tensor representations

We generalize the DeWitt-Virasoro (DWV) construction of arXiv:0912.3987 [hep-th] to tensor representations of higher ranks. A rank-$n$ tensor state, which is by itself coordinate invariant, is expanded in terms of position eigenstates that transform as tensors of the same rank. The representation of the momentum operator in these basis states is then obtained by generalizing DeWitt&#39;s argument in Phys.Rev.85:653-661,1952. Such a representation is written in terms of certain bi-vector of parallel displacement and its covariant derivatives. With this machinery at hand we find tensor representations of the DWV generators defined in the previous work. The results differ from those in spin-zero representation by additional terms involving the spin connection. However, we show that the DWV algebra found earlier as a scalar expectation value remains the same, as required by consistency, as all the additional contributions conspire to cancel in various ways. In particular, vanishing of the anomaly term requires the same condition of Ricci-flatness for the background.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

String worldsheet theory in hamiltonian framework and background independence

We analyze exact conformal invariance of string worldsheet theory in non-trivial backgrounds using hamiltonian framework. In the first part of this talk we consider the example of type IIB superstrings in Ramond-Ramond pp-wave background. In particular, we discuss the quantum definition of energy-momentum (EM) tensor and two methods of computing Virasoro algebra. One of the methods uses dynamical supersymmetries and indirectly establishes (partially) conformal invariance when the background is on-shell. We discuss the problem of operator ordering involved in the other method which attempts to compute the algebra directly. This method is supposed to work for off-shell backgrounds and therefore is more useful. In order to understand this method better we attempt a background independent formulation of the problem which is discussed in the second half of the talk. For a bosonic string moving in an arbitrary metric-background such a framework is obtained by following DeWitt&#39;s work (Phys.Rev.85:653-661,1952) in the context of particle quantum mechanics. In particular, we construct certain background independent analogue of quantum Virasoro generators and show that in spin-zero representation they satisfy the Witt algebra with additional anomalous terms that vanish for Ricci-flat backgrounds. We also report on a new result which states that the same algebra holds true in arbitrary tensor representations as well.

0 citations0 reviewsNo code linkedOpen access
preprint2009arXiv

Superstrings in type IIB R-R plane-wave in semi-light-cone gauge and conformal invariance

We reconsider the analysis done by Kazama and Yokoi in arXiv:0801.1561 (hep-th). We find that although the right vacuum of the theory is the one associated to massless normal ordering (MNO), phase space normal ordering (PNO) plays crucial role in the analysis in the following way. While defining the quantum energy-momentum (EM) tensor one needs to take into account the field redefinition relating the space-time field and the corresponding world-sheet coupling. We argue that for a simple off-shell ansatz for the background this field redefinition can be taken to be identity if the interaction term is ordered according to PNO. This definition reproduces the correct physical spectrum when the background is on-shell. We further show that the right way to extract the effective equation of motion from the Virasoro anomaly is to first order the anomaly terms according to PNO at a finite regularization parameter $\eps$ and then take the $\eps \to 0$ limit. This prescription fixes an ambiguity in taking the limit for certain bosonic and fermionic contributions to the Virasoro anomaly and is the natural one to consider given the above definition of the EM tensor.

0 citations0 reviewsNo code linkedOpen access
preprint2006arXiv

DDF Construction and D-Brane Boundary States in Pure Spinor Formalism

Open string boundary conditions for non-BPS D-branes in type II string theories discussed in hep-th/0505157 give rise to two sectors with integer (R sector) and half-integer (NS sector) modes for the combined fermionic matter and bosonic ghost variables in pure spinor formalism. Exploiting the manifest supersymmetry of the formalism we explicitly construct the DDF (Del Giudice, Di Vecchia, Fubini) states in both the sectors which are in one-to-one correspondence with the states in light-cone Green-Schwarz formalism. We also give a proof of validity of this construction. A similar construction in the closed string sector enables us to define a physical Hilbert space in pure spinor formalism which is used to project the covariant boundary states of both the BPS and non-BPS instantonic D-branes. These projected boundary states take exactly the same form as those found in light-cone Green-Schwarz formalism and are suitable for computing the cylinder diagram with manifest open-closed duality.

0 citations0 reviewsNo code linkedOpen access
preprint2005arXiv

Quantum algorithm to distinguish Boolean functions of different weights

We exploit Grover operator of database search algorithm for weight decision algorithm. In this research, weight decision problem is to find an exact weight w from given two weights as w1 and w2 where w1+w2=1 and 0<w1<w2<1. Firstly, if a Boolean function is given and when weights are {1/4,3/4}, we can find w with only one application of Grover operator. Secondly, if we apply k many times of Grover operator, we can decide w from the set of weights {sin^2(\frac{k}{2k+1}\fracπ{2}) cos^2(\frac{k}{2k+1}\fracπ{2})}. Finally, by changing the last two Grover operators with two phase conditions, we can decide w from given any set of two weights. To decide w with a sure success, if the quantum algorithm requires O(k) Grover steps, then the best known classical algorithm requires Ω(k^s) steps where s>2. Hence the quantum algorithm achieves at least quadratic speedup.

0 citations0 reviewsNo code linkedOpen access
preprint2001arXiv

Oscillator Representation of the BCFT Construction of D-branes in Vacuum String Field Theory

Starting from the boundary CFT definition for the D-branes in vacuum string field theory (VSFT) given in hep-th/0105168, we derive the oscillator expression for the D24-brane solution in the VSFT on D25-brane. We show that the state takes the form of a squeezed state, similar to the one found directly in terms of the oscillators and reported in hep-th/0102112. Both the solutions are actually one parameter families of solutions. We also find numerical evidence that at least for moderately large values of the parameter $(b)$ in the oscillator construction the two families of solutions are same under a suitable redefinition of the parameter. Finally we generalize the method to computing the oscillator expression for a D-brane solution with constant gauge field strength turned on along the world volume.

0 citations0 reviewsNo code linkedOpen access