Ajay Nerurkar

According to our database, Ajay Nerurkar authored at least 7 papers between 1997 and 2000.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2000

A note on the non-NP-hardness of approximate lattice problems under general Cook reductions.

Jin-yi Cai, Ajay Nerurkar

Inf. Process. Lett., 2000

1999

Approximating the SVP to within a Factor (1+1/dim^xi) Is NP-Hard under Randomized Reductions.

Jin-yi Cai, Ajay Nerurkar

J. Comput. Syst. Sci., 1999

Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time.

Jin-yi Cai, Ajay Nerurkar, D. Sivakumar

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

On Routing in Circulant Graphs.

Jin-yi Cai, George Havas, Bernard Mans, Ajay Nerurkar, Jean-Pierre Seifert, Igor E. Shparlinski

Proceedings of the Computing and Combinatorics, 5th Annual International Conference, 1999

1998

Approximating the SVP to within a Factor is NP-Hard under Randomized Reductions.

Jin-yi Cai, Ajay Nerurkar

Proceedings of the 13th Annual IEEE Conference on Computational Complexity, 1998

1997

Approximating the SVP to within a factor (1 + 1/dim^epsilon) is NP-hard under randomized reductions

Jin-yi Cai, Ajay Nerurkar

Electron. Colloquium Comput. Complex., 1997

An Improved Worst-Case to Average-Case Connection for Lattice Problems.

Jin-yi Cai, Ajay Nerurkar

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997