• GCDX of p-1,q-1 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 Local-global Principle for Diophantine Equations 

      Lipton, Richard J.; Vishnoi, Nisheeth Kumar (Georgia Institute of Technology, 2003)
      We observe the following global-local 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 NP-completeness of feedback vertex set for tournaments. We then give a simple 3-approximation algorithm for feedback ...