Richard J. Lipton
Research Subjects
Research Interests
Richard J. Lipton has a total of 20 co-authors. Here are the top co-authors by number of shared publications:
- Parikshit Gopalan
Georgia Tech
2 shared publications - Aranyak Mehta
IBM Almaden Research Center
1 shared publication - Aranyak Mehta
Google Research, Mountain View, CA, USA
1 shared publication - Atish Das Sarma
Google Research Google Inc Mountain View USA
1 shared publication Atri Rudra
Department of CSE University at Buffalo
1 shared publication- Danupon Nanongkai
College of Computing Georgia Institute of Technology 30332 Atlanta GA USA
1 shared publication
Latest Publications
- Open Access
Graph Pricing Problem on Bounded Treewidth, Bounded Genus and k-partite graphs
Consider the following problem. A seller has infinite copies of $n$ products represented by nodes in a graph. There are $m$ consumers, each has a budget and wants to buy two products. Consumers are represented by weighted edges. Given the prices of products, each consumer will buy both products she wants, at the given price, if she can afford to. Our objective is to help the seller price the products to maximize her profit. This problem is called {\em graph vertex pricing} ({\sf GVP}) problem and has resisted several recent attempts despite its current simple solution. This motivates the study of this problem on special classes of graphs. In this paper, we study this problem on a large class of graphs such as graphs with bounded treewidth, bounded genus and $k$-partite graphs. We show that there exists an {\sf FPTAS} for {\sf GVP} on graphs with bounded treewidth. This result is also extended to an {\sf FPTAS} for the more general {\em single-minded pricing} problem. On bounded genus graphs we present a {\sf PTAS} and show that {\sf GVP} is {\sf NP}-hard even on planar graphs. We study the Sherali-Adams hierarchy applied to a natural Integer Program formulation that $(1+\epsilon)$-approximates the optimal solution of {\sf GVP}. Sherali-Adams hierarchy has gained much interest recently as a possible approach to develop new approximation algorithms. We show that, when the input graph has bounded treewidth or bounded genus, applying a constant number of rounds of Sherali-Adams hierarchy makes the integrality gap of this natural {\sf LP} arbitrarily small, thus giving a $(1+\epsilon)$-approximate solution to the original {\sf GVP} instance. On $k$-partite graphs, we present a constant-factor approximation algorithm. We further improve the approximation factors for paths, cycles and graphs with degree at most three.Open AccessGraph Pricing Problem on Bounded Treewidth, Bounded Genus and k-partite graphs
Consider the following problem. A seller has infinite copies of $n$ products represented by nodes in a graph. There are $m$ consumers, each has a budget and wants to buy two products. Consumers are represented by weighted edges. Given the prices of products, each consumer will buy both products she wants, at the given price, if she can afford to. Our objective is to help the seller price the products to maximize her profit. This problem is called {\em graph vertex pricing} ({\sf GVP}) problem and has resisted several recent attempts despite its current simple solution. This motivates the study of this problem on special classes of graphs. In this paper, we study this problem on a large class of graphs such as graphs with bounded treewidth, bounded genus and $k$-partite graphs. We show that there exists an {\sf FPTAS} for {\sf GVP} on graphs with bounded treewidth. This result is also extended to an {\sf FPTAS} for the more general {\em single-minded pricing} problem. On bounded genus graphs we present a {\sf PTAS} and show that {\sf GVP} is {\sf NP}-hard even on planar graphs. We study the Sherali-Adams hierarchy applied to a natural Integer Program formulation that $(1+\epsilon)$-approximates the optimal solution of {\sf GVP}. Sherali-Adams hierarchy has gained much interest recently as a possible approach to develop new approximation algorithms. We show that, when the input graph has bounded treewidth or bounded genus, applying a constant number of rounds of Sherali-Adams hierarchy makes the integrality gap of this natural {\sf LP} arbitrarily small, thus giving a $(1+\epsilon)$-approximate solution to the original {\sf GVP} instance. On $k$-partite graphs, we present a constant-factor approximation algorithm. We further improve the approximation factors for paths, cycles and graphs with degree at most three. - 4 May 2013
- Published by Springer Nature in computational complexity
- Vol. 22 (2) , 311-343
Amplifying circuit lower bounds against polynomial time, with applications
- 4 May 2013
- Published by Springer Nature in computational complexity
- Vol. 22 (2) , 311-343
Amplifying circuit lower bounds against polynomial time, with applications
- Open Access
Simulating Special but Natural Quantum Circuits
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. Grover's algorithm does not fall into this class). Our main result is that any algorithm in this class that measures at most O(log n) qubits can be simulated by classical randomized polynomial time algorithms. This does not dequantize Shor's algorithm (as the latter measures n qubits) but our work also highlights a new potentially hard function for cryptographic applications. Our main technical contribution is (to the best of our knowledge) a new exact characterization of certain sums of Fourier-type coefficients (with exponentially many summands).
Open AccessSimulating Special but Natural Quantum Circuits
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. Grover's algorithm does not fall into this class). Our main result is that any algorithm in this class that measures at most O(log n) qubits can be simulated by classical randomized polynomial time algorithms. This does not dequantize Shor's algorithm (as the latter measures n qubits) but our work also highlights a new potentially hard function for cryptographic applications. Our main technical contribution is (to the best of our knowledge) a new exact characterization of certain sums of Fourier-type coefficients (with exponentially many summands).
- 3 November 2010
- Published by Elsevier in Theoretical Computer Science
- Vol. 412 (23) , 2544-2555
Best-order streaming model
- 3 November 2010
- Published by Elsevier in Theoretical Computer Science
- Vol. 412 (23) , 2544-2555
Best-order streaming model
- 25 September 2010
- Published by Springer Nature
- p. E1-E2
Erratum
- 20 August 2010
- Published by Springer Nature
- p. 37-38
A Nightmare About SAT
- 20 August 2010
- Published by Springer Nature
- p. 33-36
Why Believe P Not Equal To NP?
- 20 August 2010
- Published by Springer Nature
- p. 29-31
How To Solve P=NP?
- 20 August 2010
- Published by Springer Nature
- p. 27-28
NP Too Big or P Too Small?
- 20 August 2010
- Published by Springer Nature
- p. 23-26
What Happens When P=NP Is Resolved?