Browsing College of Computing Technical Reports by Author "Vishnoi, Nisheeth Kumar"
Now showing items 15 of 5

GCDX of p1,q1 for Random p,q
Vishnoi, Nisheeth Kumar (Georgia Institute of Technology, 2003)In this note we study the following problem: How big can the greatest common divisor of p−1 and q−1 be, where p, q are randomly chosen primes in the set {1, . . . ,N}? Apart from being of independent interest, this ... 
A Generalization of the Characteristic Polynomial of a Graph
Lipton, Richard J.; Vishnoi, Nisheeth Kumar; Zalcstein, Yechezkel (Zeke) (Georgia Institute of Technology, 2003)Given a graph G with its adjacency matrix A, consider the matrix A(x, y) in which the 1s are replaced by the indeter0minate x and 0s (other than the diagonals) are replaced by y. The ℒpolynomial of G is defined ... 
The Geometry of Matrix Rigidity
Landsberg, J. M.; Taylor, Jacob; Vishnoi, Nisheeth Kumar (Georgia Institute of Technology, 2003)Consider the following problem: Given an n×n matrix A and an input x, compute Ax. This problem has a simple algorithm which runs in time O(n²). The question thus is: Is this is the best possible ? Valiant showed ([12]) ... 
A Localglobal Principle for Diophantine Equations
Lipton, Richard J.; Vishnoi, Nisheeth Kumar (Georgia Institute of Technology, 2003)We observe the following globallocal principle for Diophantine equations: If an equation f(x₁,...,x[subscript t]) ϵ ℤ[x₁,...,x[subscript t] = p can be solved efficiently for a dense set of primes p, then one can ... 
On feedback vertex sets in tournaments
Vishnoi, Nisheeth Kumar (Georgia Institute of Technology, 2003)In this report we consider the feedback vertex and arc set problems for tournaments. We first show NPcompleteness of feedback vertex set for tournaments. We then give a simple 3approximation algorithm for feedback ...