Result 1 to 20 of 111 total
Grothendieck-type inequalities in combinatorial optimization. (English)
Commun. Pure Appl. Math. 65, No. 7, 992-1035 (2012).
1
Hardness of approximating the closest vector problem with pre-processing. (English)
Comput. Complexity 20, No. 4, 741-753 (2011).
2
Inapproximability of NP-complete problems, discrete Fourier analysis, and geometry. (English)
Bhatia, Rajendra (ed.) et al., Proceedings of the international congress of mathematicians (ICM 2010), Hyderabad, India, August 19‒27, 2010. Vol. IV: Invited lectures. Hackensack, NJ: World Scientific; New Delhi: Hindustan Book Agency (ISBN 978-981-4324-34-2/hbk; 978-81-85931-08-3/hbk; 978-981-4324-31-1/set; 978-981-4324-35-9/ebook). 2676-2697 (2011).
3
A simple deterministic reduction for the gap minimum distance of code problem. (English)
Aceto, Luca (ed.) et al., Automata, languages and programming. 38th international colloquium, ICALP 2011, Zurich, Switzerland, July 4‒8, 2011. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-22005-0/pbk). Lecture Notes in Computer Science 6755, 474-485 (2011).
4
Combinatorial theorems about embedding trees on the real line. (English)
J. Graph Theory 67, No. 2, 153-168 (2011).
5
Inapproximability of vertex cover and independent set in bounded degree graphs. (English)
Theory Comput. 7, Paper No. 3, 27-43, electronic only (2011).
6
On the hardness of learning intersections of two halfspaces. (English)
J. Comput. Syst. Sci. 77, No. 1, 129-141 (2011).
7
Combinatorial theorems about embedding trees on the real line (English)
Journal of Graph Theory 67, No. 2, 153-168 (2011).
8
A simple deterministic reduction for the gap minimum distance of code problem (English)
ICALP (1), 474-485 (2011).
9
NP-hardness of approximately solving linear equations over reals (English)
STOC, 413-420 (2011).
10
AODV-DS with dominant pruning in mobile ad hoc networks. (English)
Meghanathan, Natarajan (ed.) et al., Recent trends in networks and communications. International conferences, NeCoM 2010, WiMoN 2010, WeST 2010, Chennai, India, July 23‒25, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-14492-9/pbk; 978-3-642-14493-6/ebook). Communications in Computer and Information Science 90, 162-170 (2010).
11
Hardness of reconstructing multivariate polynomials over finite fields. (English)
SIAM J. Comput. 39, No. 6, 2598-2621 (2010).
12
Approximate Lasserre integrality gap for unique games. (English)
Serna, Maria (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 13th international workshop, APPROX 2010, and 14th international workshop, RANDOM 2010, Barcelona, Spain, September 1‒3, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15368-6/pbk). Lecture Notes in Computer Science 6302, 298-311 (2010).
13
SDP gaps for 2-to-1 and other label-cover variants. (English)
Abramsky, Samson (ed.) et al., Automata, languages and programming. 37th international colloquium, ICALP 2010, Bordeaux, France, July 6‒10, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-14164-5/pbk). Lecture Notes in Computer Science 6198, 617-628 (2010).
14
Inapproximability of hypergraph vertex cover and applications to scheduling problems. (English)
Abramsky, Samson (ed.) et al., Automata, languages and programming. 37th international colloquium, ICALP 2010, Bordeaux, France, July 6‒10, 2010. Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-14164-5/pbk). Lecture Notes in Computer Science 6198, 250-261 (2010).
15
io-port 05754737 Harsha, Prahladh;
Charikar, Moses;
Andrews, Matthew;
Arora, Sanjeev;
Khot, Subhash;
Moshkovitz, Dana;
Zhang, Lisa;
Aazami, Ashkan;
Desai, Dev;
Gorodezky, Igor;
Jagannathan, Geetha;
Kulikov, Alexander S.;
Mir, Darakhshan J.;
Newman, Alantha;
Nikolov, Aleksandar;
Pritchard, David;
Spencer, Gwen
Limits of approximation algorithms: pcps and unique games (DIMACS tutorial lecture notes). (English)
Comput. Res. Repos. 2010, Article No. 1002.3864 (2010).
16
Inapproximability results for computational problems on lattices. (English)
Nguyen, Phong Q. (ed.) et al., The LLL algorithm. Survey and applications. Dordrecht: Springer (ISBN 978-3-642-02294-4/hbk; 978-3-642-02295-1/ebook). Information Security and Cryptography, 453-473 (2010).
17
Sharp kernel clustering algorithms and their associated Grothendieck inequalities (English)
SODA, 664-683 (2010).
18
SDP gaps for 2-to-1 and other label-cover variants (English)
ICALP (1), 617-628 (2010).
19
Inapproximability of hypergraph vertex cover and applications to scheduling problems (English)
ICALP (1), 250-261 (2010).
20
Result 1 to 20 of 111 total
Start
Contact
Print
General Help
