Zobrazeno 1 - 10
of 65
pro vyhledávání: '"Gurjar, Rohit"'
Two matrices are said to be principal minor equivalent if they have equal corresponding principal minors of all orders. We give a characterization of principal minor equivalence and a deterministic polynomial time algorithm to check if two given matr
Externí odkaz:
http://arxiv.org/abs/2410.01961
In this work, we study the parallel complexity of the Euclidean minimum-weight perfect matching (EWPM) problem. Here our graph is the complete bipartite graph $G$ on two sets of points $A$ and $B$ in $\mathbb{R}^2$ and the weight of each edge is the
Externí odkaz:
http://arxiv.org/abs/2405.18833
The matching and linear matroid intersection problems are solvable in quasi-NC, meaning that there exist deterministic algorithms that run in polylogarithmic time and use quasi-polynomially many parallel processors. However, such a parallel algorithm
Externí odkaz:
http://arxiv.org/abs/2402.18276
We study the problem of fairly assigning a set of discrete tasks (or chores) among a set of agents with additive valuations. Each chore is associated with a start and finish time, and each agent can perform at most one chore at any given time. The go
Externí odkaz:
http://arxiv.org/abs/2402.04353
VBP is the class of polynomial families that can be computed by the determinant of a symbolic matrix of the form $A_0 + \sum_{i=1}^n A_ix_i$ where the size of each $A_i$ is polynomial in the number of variables (equivalently, computable by polynomial
Externí odkaz:
http://arxiv.org/abs/2305.09973
Autor:
Gurjar, Rohit, Vishnoi, Nisheeth K.
We show that for any regular matroid on $m$ elements and any $\alpha \geq 1$, the number of $\alpha$-minimum circuits, or circuits whose size is at most an $\alpha$-multiple of the minimum size of a circuit in the matroid is bounded by $m^{O(\alpha^2
Externí odkaz:
http://arxiv.org/abs/1807.05164
Autor:
Gurjar, Rohit, Volk, Ben Lee
We construct a pseudorandom generator which fools read-$k$ oblivious branching programs and, more generally, any linear length oblivious branching program, assuming that the sequence according to which the bits are read is known in advance. For polyn
Externí odkaz:
http://arxiv.org/abs/1708.02054
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,
Externí odkaz:
http://arxiv.org/abs/1708.02222
Autor:
Gurjar, Rohit, Vishnoi, Nisheeth K.
We present a simple proof of the fact that the base (and independence) polytope of a rank $n$ regular matroid over $m$ elements has an extension complexity $O(mn)$.
Comment: This paper has been withdrawn as there is an error in the proof of the
Comment: This paper has been withdrawn as there is an error in the proof of the
Externí odkaz:
http://arxiv.org/abs/1701.00538
Publikováno v:
Theory of Computing 13(2):1-21, 2017
We give improved hitting sets for two special cases of Read-once Oblivious Arithmetic Branching Programs (ROABP). First is the case of an ROABP with known order of the variables. The best previously known hitting set for this case had size $(nw)^{O(\
Externí odkaz:
http://arxiv.org/abs/1601.08031