45 citations · 65 across the 7 of their papers we have counts for
7 papers
On the Skolem Problem and Prime Powers
George Kenison, Richard Lipton, Joël Ouaknine +1
The Skolem Problem asks, given a linear recurrence sequence , whether there exists such that . In this paper we consider the following specialisation…
Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-partite graphs
Parinya Chalermsook, Shiva Kintali, Richard Lipton +1
Consider the following problem. A seller has infinite copies of products represented by nodes in a graph. There are consumers, each has a budget and wants to buy two produc…
Simulating Special but Natural Quantum Circuits
Richard J. Lipton, Kenneth W. Regan, Atri Rudra
We identify a sub-class of BQP that captures certain structural commonalities among many quantum algorithms including Shor's algorithms. This class does not contain all of BQP (e.g…
On Tractable Exponential Sums
Jin-Yi Cai, Xi Chen, Richard Lipton +1
We consider the problem of evaluating certain exponential sums. These sums take the form , where each x_i is summed over…
Polynomials that Sign Represent Parity and Descartes' Rule of Signs
Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan +1
A real polynomial sign represents if for every , the sign of equals . Such s…
Some Remarks on the Jacobian Conjecture and Connections with Hilbert's Irreducibility Theorem
Richard J. Lipton, Evangelos Markakis
We make two observations regarding the invertibility of Keller maps. i.e., polynomial maps for which the determinant of their Jacobian matrix is identically equal to 1. In our firs…