Rajsekar Manokaran

According to our database, Rajsekar Manokaran authored at least 14 papers between 2008 and 2018.

Collaborative distances:

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

2018

Towards a characterization of constant-factor approximable finite-valued CSPs.

Víctor Dalmau, Andrei A. Krokhin, Rajsekar Manokaran

J. Comput. Syst. Sci., 2018

2017

On the Hardness of Approximating Balanced Homogenous 3-Lin.

Johan Håstad, Rajsekar Manokaran

Theory Comput., 2017

Improved NP-Inapproximability for 2-Variable Linear Equations.

Johan Håstad, Sangxia Huang, Rajsekar Manokaran, Ryan O'Donnell, John Wright

Theory Comput., 2017

2015

On the NP-Hardness of Approximating Ordering-Constraint Satisfaction Problems.

Per Austrin, Rajsekar Manokaran, Cenny Wenner

Theory Comput., 2015

Towards a Characterization of Constant-Factor Approximable Min CSPs.

Víctor Dalmau, Andrei A. Krokhin, Rajsekar Manokaran

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

Maximum Quadratic Assignment Problem: Reduction from Maximum Label Cover and LP-based Approximation Algorithm.

Konstantin Makarychev, Rajsekar Manokaran, Maxim Sviridenko

ACM Trans. Algorithms, 2014

2012

Testing Permanent Oracles - Revisited.

Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva

Electron. Colloquium Comput. Complex., 2012

On Quadratic Programming with a Ratio Objective.

Aditya Bhaskara, Moses Charikar, Rajsekar Manokaran, Aravindan Vijayaraghavan

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Beating the Random Ordering is Hard: Every ordering CSP is approximation resistant.

Venkatesan Guruswami, Johan Håstad, Rajsekar Manokaran, Prasad Raghavendra, Moses Charikar

Electron. Colloquium Comput. Complex., 2011

On LP-Based Approximability for Strict CSPs.

Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2009

On the Optimality of a Class of LP-based Algorithms.

Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi

Electron. Colloquium Comput. Complex., 2009

Every Permutation CSP of arity 3 is Approximation Resistant.

Moses Charikar, Venkatesan Guruswami, Rajsekar Manokaran

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling.

Rajsekar Manokaran, Joseph Naor, Prasad Raghavendra, Roy Schwartz

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Beating the Random Ordering is Hard: Inapproximability of Maximum Acyclic Subgraph.

Venkatesan Guruswami, Rajsekar Manokaran, Prasad Raghavendra

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008