Sanjeev Arora
- 1.M. Ajta/. Generating hard instances of lattice problems. Proceedings of the Twenty Eighth Annual Symposium on the Theory of Computing, ACM, 1996. Google Scholar
Digital Library
- 2.M. Ajtai and C. Dwork. A public-key cryptosystem with worst-case/average-case equivalence. Proceedings of the Twenty Eighth Annual Symposium on the Theory of Computing, ACM, 1997 Google ScholarDigital Library
- 3.S. Arora. ProbabiUstic Checking of Proofs and Hardness of Approzimation Problems. Phi) thesis, U.C. Berkeley, 1994. Available from http://w~-v. ~s. princeton, edu/~axora . Google ScholarDigital Library
- 4.S. Arora. Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. Proceedings of 87th IEEE Syrup. on Foundations of Computer Science, pp 2-12, 1996. Google ScholarDigital Library
- 5.S. Arora. Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. Proceedings of 38th IEEE Syrup. on Foundations of Computer Science, 1997. Google ScholarDigital Library
- 6.S. Arora, L. Babai, J. Stern, and Z. Sweedyk. The hardness of approximate optima in lattices, codes, and systems of linear equations. Journal of Corn. purer and System Sciences, 54(2):317-331, 1997. Google ScholarDigital Library
- 7.S. Arora, A. Frieze, and H. Kaplan. New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems, Proceedings of the Thirty Seventh Annual Symposium on the Foundations of Computer Science, IEEE, 1996, pages 21-30. Google ScholarDigital Library
- 8.S, Arora, D. Karger, and M. Karpinski. Polynomial Time Approximation Schemes for Dense Instances of N'~-Hard Problems. Proceedings of the Twenty Seventh Annual Symposium on the Theory of Computing, ACM, 1995. Google ScholarDigital Library
- 9.S, Arora and C. Lund. Hardness of approximations, In {75}. Google ScholarDigital Library
- 10.S, Arora, C. Lund, R. Motwani, M. Sudan, and M, Szegedy. Proof verification and intractability of approximation problems. In Proc. 33rd IEEE Syrup. on Foundations of Computer Science, pages 13-22, 1992.Google Scholar
- 11.S, Arora, R. Motwani, S. Safra, M. Sudan, and M. Szegedy, PCP and approximation problems. Unpublished note, 1992.Google Scholar
- 12.S. Arora and S. Safra. Probabilistic checking of proofs: a new characterization of NP. To appear Journal of the ACM. Preliminary version in Procoedings of the Thirty Third Annual Symposium on the Foundations of Computer Science, IEEE, 1992. Google ScholarDigital Library
- 13.S. Arora and M. Sudan. improved low degree testing and its applications. Proceedings of the Twenty Eighth Annual Symposium on the Theory of Computing, ACM, 1997 Google ScholarDigital Library
- 14.G. Auslello, A. D'Atri, and M. Protest. On the ~tructure of combinatorial problems and structure preserving reductions, in Proc. dth Intl. Coll. on Automata, Languages and Programming, 1977. Google ScholarDigital Library
- 15.G, Ausiello, A. D'Atri, and M. Protest. Structure preserving reductions among convex optimization problems. Journal of Computer and System $cienact, 21:136-153, 1980.Google Scholar
- 16.G. Ausiello, A. Marchetti-Spaccamela, and M. Protasi. Toward a unified approach for the classification of NP-complete optimization problems. Theoretical Computer Science, 12:83-96, 1980.Google ScholarCross Ref
- 17.L. Babai. TYading group theory for randomness. in Proc. 17th ACM $ymp. on Theory of Computing, pages 421-429, 1985. Google ScholarDigital Library
- 18.L. Babai. Transparent proofs and limits to approximations, in Proceedings of the First European Conoress of Mathematicians. Birkhauser, 1994,Google Scholar
- 19.L, Babai, L. Fortnow, and C. Lund. Nondeterministic exponential time has two-prover interactive protocols. Computational Complexity, 1:3-40, 1991.Google ScholarCross Ref
- 20.L. Babai, L. Fortnow, L. Levin, and M. Szegedy. Checking computations in polylogarithmic time. In Pros. ~3rd A CM Symp. on Theory of Computing, pages 21-31, 1991. Google Scholar
- 21.L. Babel and S. Moran. Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences, 36:254-276, 1988. Google ScholarDigital Library
- 22.B. S. Baker. Approximation algorithms for NP- complete problems on planar graphs. JACM 41(1):153--180, 1994. Prelim. version in Proceedings of the Twenty Third Annual Symposium on the Foundations of Computer Sc./ence, 1EEE, 1982. Google ScholarDigital Library
- 23.D. Beaver and 3. Feigenbaum. Hiding instances in multioracle queries. Proceedings of the Seventh Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science Vol. 415, Springer Verlag, 1990. Google ScholarDigital Library
- 24.M. Benare. Interactive Proofs and approximation: Reductions from two provers in one round. In Proceedings of the ~nd Israel Symposium on Theory and Computing Systems. IEEE Computer Press, 1993. Preliminary version: IBM Research Report RC 17969 (May 1992).Google Scholar
- 25.M. BeIlare, D. Coppersmith, J. H~ad, M. Kivd and M. Sudan. Linearity testing in characteristic two. IEEE Transactions on Information Theory 42(6):1781-1795, November 1996. Google ScholarCross Ref
- 26.M. BeUare, O. Goldreich, and M. Sudan. Free bits and non-approximability- towards tight resuits. In Proc. 36th IEEE Syrup. on Foundations of Computer Science, 1995. Full version available from ECCC. Google ScholarDigital Library
- 27.M. Bellare, S. Goldwasser, C. Lund, and A. Russell. Efficient multi-prover interactive proofs with applications to approximation problems. In Proc. ~5th A CM Symp. on Theory of Computing, pages 113-131, 1993. Google ScholarDigital Library
- 28.M. BeHare and P. Rogaway. The complexity of approximating a nonlinear program. Journal of Mathematical Programming B, 69(3):429-441, 1995. Also in Complexity of Numerical Optimizaffon, Ed. P. M. Pardalos, World Scientific, 1993. Google ScholarDigital Library
- 29.M. Bellare and M. Sudan. Improved nonapproximability results. In Proc. ~6th A CM Syrup. on Theory of Computing, pages 184-193, 1994. Google ScholarDigital Library
- 30.M. Ben-or, S. Goldwasser, J. Kilian, and A. Wigderson. Multi prover interactive proofs: How to remove intractability assumptions. In Proc. ~Oth A CM Syrup. on Theory of Computing, pages 113-121, 1988. Google ScholarDigital Library
- 31.P. Barman and G. Schnitger. On the complexity of approximating the independent set problem. In. formation and Computation, 96(1):77-94, 1992. Google ScholarDigital Library
- 32.M. Bern and P. Plassmann. The Steiner problem vAth edge lengths i and 2. Information Processing Letters, 32:171-176, 1989. Google ScholarDigital Library
- 33.A. Blum, G. Konjevod, It. Ravi, and S. Vempala. Semi-definite relaxations for minimum bandwidth and other problems These proceedings. Google ScholarDigital Library
- 34.M. Blum and S. Kannan. Designing programs that check their work. In Proc. 21st A CM Syrup. on Theory of Computing, pages 86-97, 1989. Google ScholarDigital Library
- 35.M. Blum, M. Luby, and IL Rubinfeld. Self- Testing/Correcting with Applications to Numerical Problems. JCSS 47(3):549-595, 1993. Prelim. Version in Proceedings of the Twenty Second Annum Symposium on the Theory' of Computing, ACM, 1990. Google ScholarDigital Library
- 36.R. B. Boppana and M. M. HaUd6rsson. Approxtreating m~um independent sets by excluding subgraphs. BIT, 32(2):180-196, June 1992. Google ScholarDigital Library
- 37.N. Christofides. Worst-case analysis of a new heuristic for the traveling salesman problem. In J.F. T~aub, editor, Symposium on new directions and recent results in algorithms and complexity, page 441. Academic Press, NY, 1976.Google Scholar
- 38.A. Condom The complexity of the max-word problem and the power of one-way interactive proof systems. Computational Complexity, 3:292- 3O5, 1993. Google ScholarDigital Library
- 39.A. Condon, J. Feigenbaum, C. Lurid and P. Shor. Probabilistically Checkable Debate Systems and Approximation Algorithms for PSPACE-ttard Functions. Proceedings of the Twenty Fifth Annual S:~nposium on the Theory of Computing, ACM, 1993. Google ScholarDigital Library
- 40.A. Condon, J. Feigenbanm, C. Lund and P. Shot. Random debaters and the hardness of approximating stochastic functions. SIAM Journal on Computing, 26(2):369-400, April 1997. Google ScholarDigital Library
- 41.S. Cook. The complexqty of theorem-proving procedures, in Prec. 3rd A CM Syrup. on Theory of Computing, pages 151-155, 1971. Google ScholarDigital Library
- 42.N. Creignou. A dichotomy theorem for maximum generalized satisfiability problems. JCSS 51(3):511-522, 1995. Google ScholarDigital Library
- 43.P. Crescenzi and V. Kann. A compendium of NP optimization problems. Available from ftp://www.nada.kth.se/Theory/Viggo. Kann/compendium.ps.ZGoogle Scholar
- 44.P. Crescenzi, V. Kann, R. Silvestri, and L. Trevisan. Structure in aprox'imation classes. Prec. 1st Combinatorics and Computing conference, pages 539-548. LNCS 959, Springer Verlag, 1995. Google ScholarDigital Library
- 45.P. Crescenzi and A. Panconesi. CompletenEss in approximation classes. Information and Computation, 93:241-262, 1991. Google ScholarDigital Library
- 46.R. Fagin. Generalized first-order spectra and polynomial-time recognizable sets. In R. Karp, editor, Complexity of Computer Computations, pages 43-73. AMS, 1974.Google Scholar
- 47.U. Feige. A threshold of In n for approximating set cover. Proceedings of the Twenty Eighth Annum S:~nposium on the Theory of Computing, ACM, 1996, pages 314-318. Google ScholarDigital Library
- 48.U. Feige. Appro:dmating the bandwidth via volume respecting embeddings. These proceedings. Google ScholarDigital Library
- 49.U. Feige, S. Gold~sser, L. Lov~sz, S. Safra, and M. Szeged:~; Interactive proofs and the hardness of approximating cliques Journal of the A CM, 43(2):268-292, 1996. Preliminary version: Approximatin9 clique is almost NP-complete, Proceedings of the Thirty Second Annum Symposium on the Foundations of Computer Seience, IEEE, 1991. Google ScholarDigital Library
- 50.U. Feige and J. Kilian. Two prover protocolslow error at affordable rates. In Prec. 26th ACM Symp. on Theory of Computing, pages 172-183, 1994. Google ScholarDigital Library
- 51.U. Feige and J. Kilian. Zero Knowledge and the Chromatic Number (Preliminary Version). Proceedings of the Eleventh Annum Conference on Comple:dty Theory, IEEE, 1996. Google ScholarDigital Library
- 52.U. Feige and L. Lov,4sz. Two-prover one-round proof systems: Their power and their problems. In Prec. ~dth A CM Syrup. on Theory of Computing, pages 733-741, 1992. Google Scholar
- 53.W. Fernandez de la Vega and G. S. Lueker. Bin packing can be solved within l+e in linear time. Combinatorica:l(4), 349-355, 1981.Google Scholar
- 54.L. Fortnow, J. Rompel, and M. Sipser. On the power of multi-prover interactive protocols. In Proceedings of the 3rd Conference on Struatur~ in Complexity Theory, pages 156-161, 1988.Google Scholar
- 55.A. Frieze and R. Kannan. The Regularity Lemma and Approximation Schemes for Dense Problems. Proceedings of the Thirty Seventh Annum Symposium on the Foundations of Computer Science, IEEE, 1996, pages 12-20. Google ScholarDigital Library
- 56.M. Fiirer. Improved hardness results for appro.,dmating the chromatic number. In Prec. 36th IEEE Syrup. on Foundations of Computer Science, 1995. Google ScholarDigital Library
- 57.M. R. Garey, R. L. Graham, and J. D. Ullman. Worst case analysis of memory allocation algorithms. In Proceedings of the Fourth Annum Symposium on the Theory of Computing, ACM, 1972, pages 143-150. Google ScholarDigital Library
- 58.M. R. Garey and D. S. Johnson. The complexity of near-optimal graph coloring. Journal of tha ACM, 23:43-49, 1976. Google ScholarDigital Library
- 59.M. Garey and D. Johnson. "Strong" NP- completeness results: motivation, examples and implications. Journal of the A CM, 25:499-508, 1978. Google ScholarDigital Library
- 60.M. R. Garey and D. S. Johnson. Gomputer3 and Intractability: a guid~ to the theory of NP- completeness. W. H. Freeman, 1979. Google ScholarDigital Library
- 61.N. Garg, V.V. Vazirani, and M. Yannakakis. Approximate max-flow min-(multi)-cut theorems and their applications. In Prec. ~5th A CM Syrup. on Theory of Computing, pages 698 -707, 1993. Google Scholar
- 62.M. Goemans and D. Williamson. A 0.878 approximation algorithm for MAX-2SAT and MAX- CUT. In Prec. 26th A CM Syrup. on Theor~d of Computing, pages 422-431, 1994. Google ScholarDigital Library
- 63.M. Goemans and D. Williamson. The primal-dual method for approximation algorithms and its applications to network design problems. In {75}. Google ScholarDigital Library
- 64.O. Goldreich. Probabilistic proof systems. Technical Report RS-94-28, Basic Research in Computer Science, Center of the Danish National Research Foundation, September 1994. Proceedings of the International Congress of Mathematicians, Blrkhauser Verlag 1994. Google ScholarDigital Library
- 65.O. Goldreich. A Taxonomy of Proof Systems. In Complezity Theo~ Retrospective Ii, L.A. Hemaspaandra and A. Selman (eds.), Springer-Verlag, New York, 1997. Google ScholarDigital Library
- 66.O. Goldreich, S. Goldwasser and D. Ron. Property Testing and its Connection to Learning and Approximation. Proceedings of the Thirty Seventh Annual Symposium on the Foundations of Computer Science, IEEE, 1996, pages 339-348. Google ScholarDigital Library
- 67.S. Goldwasser, $. Micali, and C. Rackoff. The knowledge complexity of interactive proofs. SIAM J, on Computing, 18:186-208, 1989. Google ScholarDigital Library
- 68.O. Ooldreich, S. Micali, and A. Wigderson. How to play any mental game or a completeness theerent for protocols with honest majority. In Prec. lOth A CM Syrup. on Theory of Computing, pages 218-229, 1987. Google Scholar
- 69.R. L. Graham. Bounds for certain multiprocessing anomalies. Ball System Technical Journal, 45:1563-1581, 1966.Google ScholarCross Ref
- 70.M. GrS~schel~ L. Lovlsz, and A. Schrijver. Geometric Algorithms and Combinatorial Optimization. Springer Verlag, Berlin. 1988.Google Scholar
- 71.L. Hall. Approximation algorithms for scheduling. Google ScholarDigital Library
- 72.M. Halldorsson. A still better performance guarantee for approximate graph coloring. Information Procaasing Letters, 45:19-23, 1993. Google ScholarDigital Library
- 73.J, Hfistad, Clique is Hard to Approximate within nl'~. Proceedings of the Thirty Seventh Annual Symposium on the Foundations of Computer Science, IEEE, 1996, pages 627-636. Google ScholarDigital Library
- 74.J. H~tad. Some optimal inapproximability results. Proceedings of the Twenty Eighth Annual Symposium on the Theory of Computing, ACM, 1997, pages 1-10. Google ScholarDigital Library
- 75.D. Hochbaum, ed. Approximation Algorithms for NP-hard problems. PWS Publishing, Boston, 1996. Google ScholarDigital Library
- 76.D, Hochbaum and D. Shmoys. Using dual approximation algorithms for scheduling problems: practical and theoretical results. Journal of the AGM 34(1):144-162, 1987. Google ScholarDigital Library
- 77.D, Hochbaum and D. Shmoys. A best-possible heuristic for the k-center problem. Math. of Op, Res. 10(2):180-184, 1985.Google Scholar
- 78.O. H. ibarra and C. E. Kim. Fast approximation algorithms for the knapsack and sum of subsets problems. JACM, 22(4):463-468, 1975. Google ScholarDigital Library
- 79.D, S. 3ohnson. Approximation algorithms for combinatorial problems. Journal of Computer and $yatem Sciences, 9:256-278, 1974.Google Scholar
- 80.D, S. Johnson. The NP-completeness column: an ongoing guide. Journal of Algorithms, 13:502-524, 1992. Google ScholarDigital Library
- 81.V. Kann. On the approzimability of NP. complete optimization problems. PhD thesis, Royal Institute of Technology, Stockholm, Sweden, 1992.Google Scholar
- 82.D. Karger, th Motwrani, and M. Sudan. Approximate graph coloring by semidefmite programruing. Proceedings of the Thirty Fifth Annum Symposium on the Foundations of Computer Science, IEEE, 1994, pages 2-13.Google Scholar
- 83.H. Karloff and U. Zwick. A 7/8-Approximation Algorithm for MAX 3SAT? Proceedings of the Thirty Eigth Annual Symposium on the Foundations of Computer Science, IEEE, 1997. Google ScholarDigital Library
- 84.N. Karmarkar and R.M. Karp. An efficient approximation scheme for the one-dimensional binpacking problem. In Prec. 23'a IEEE Symposium on Foundations of Computer Science, pp 312-320, 1982.Google Scholar
- 85.R. M. Karp. Reducibility among combinatorial problems. In Miller and Thatcher, editors, Com. plezity of Computer Computations, pages 85-103. Plenum Press, 1972.Google Scholar
- 86.tL M. Karp. Probabilistic analysis of partitioning algorithms for the TSP in the plane. Math. Oper. Res. 2 (1977), 209-224.Google ScholarDigital Library
- 87.D. Karger, R. Motwani, and G.D.S. Ramkumar. On approximating the longest path in a graph. In Proceedings of Workshop on Algorithms and Data Structures, pages 421-430. LNCS (Springer- Verlag), v. 709, 1993. Google ScholarDigital Library
- 88.S. Khanna, N. Lintel, and S. Safra. On the hardness of approximating the chromatic number. In Proceedings of the ~nd Israel Symposium on The. cry and Computing Systems, ISTC$, pages 250-- 260. IEEE Computer Society Press, 1993.Google ScholarCross Ref
- 89.S. Khanna, R. Motvmni, M. Sudan, and U. Vazirant. On syntactic versus computational vievrs of approximability. Proceech'ngs of the Thirty Fifth Annual Symposium on the Foundations of Computer Science, 1EEE, 1994, pages 819-836.Google Scholar
- 90.S. Khanna, M. Sudan, L. Trevisan. Constraint satisfaction: the approximability of minimization problems. Proceedings of the Twelfth Annum Conference on Complexity Theory, IEEE, 1997, pages 282-296. Google ScholarDigital Library
- 91.S. Khanna, M. Sudan, and D. WiUiamson. A complete classification of the approximability of maximization problems derived from Boolean constraint satisfaction. Proceedings of the Twenty Eighth Annual Symposium on the Theory of Computing, ACM, 1997, pages 11-20. Google ScholarDigital Library
- 92.M. Kiwi, C. Lund, A. Russell, D. Spielman, and th Sundaram Alternation in interaction. Proceedings of the Ninth Annual Conference on Structure in Complexi~ Theory, IEEE, 1994, pages 294- 303.Google ScholarCross Ref
- 93.P. G. Kolaitis and M. N. Thakur. Approxdmation properties of NP minimization classes. In Prec. of the 6th Conference on Structure in Comple. zity Theo~, pages 353--366, 1991.Google Scholar
- 94.G. Kolata. New shortcut found for long math proofs. New York Times, April 7, 1992.Google Scholar
- 95.tL Ladner. On the Structure of Polynomial Time ReductibiliW. JACM, 22(1):155-171, 1975. Google ScholarDigital Library
- 96.D. Lapidot and A. Shamir. Fully parallelized multi prover protocols for NEXPTIME. In Proc. $2nd IEEE Syrup. on Foundations of Computer Science, pages 13-18, 1991. Google ScholarDigital Library
- 97.E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, D. B. Shmoys. The traveling salesman problem. John ~Vileb; 1985Google Scholar
- 98.T. Leighton and $. Rao. An approximate maxflow rain-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. In Proc. 29th IEEE Syrup. on Foundations of Computer Science, pages 422-431, 1988.Google Scholar
- 99.L. Lex4n. Universal'ny~e perebornyYe zadachi (universal search problems: in Russian). Problemy Peredachi Informatsii, 9(3):265-266, 1973.Google Scholar
- 100.L. Levin. Average case complete problems. SIAM Jour. of Computing, 1986, Vol. 15, pp. 285-286. Extended abstract appeared in Proc. 16th A CM Syrup. on Theory of Computing, 1984. Google ScholarDigital Library
- 101.R. Lipton. New directions in testing. In Distributed Computing and Cryptography, J. Feigenbaum and M. Merritt, editors. Dimacs SeriEs in Discrete Mathematics and Theoretical Computer Science, 2. AMS 1991.Google Scholar
- 102.1%. Lipton and R. Tarjan. Applications of a planar separator theorem. SIAM J. Computing, 9(3):615-627, 1980.Google ScholarCross Ref
- 103.N. Linial, E. London, and Y. Rabinovich. The Geometry of Graphs and Some of its Algorithmic Applications. Combinatorica, 1995.Google ScholarCross Ref
- 104.L. Lov~z. On the ratio of optimal integral and fractional covers. Discrete Mathematics, 13:383- 390, 1975.Google ScholarDigital Library
- 105.C. Lund. The Power of Interaction. MIT Press, Cambridge, Mass., 1992. Google ScholarDigital Library
- 106.C. Lund, L. Fortnow, H. Karloff, and N. Nisan. Algebraic methods for interactive proof systems. J. of the A CM, 39(4):859-868, October 1992. Google ScholarDigital Library
- 107.C. Lund and M. Yannakakis. The appro.xim~~ion of maximum subgraph problems. In Proee~ings of International Colloquium on Automata, Lan- 9uages and Programming, ICALP, pages 40-51, 1993. Google ScholarDigital Library
- 108.C. Lund and M. Yann~. On the hardness of approximating minimization problems. Journal of the ACM, 41(5):960-981, 1994. Google ScholarDigital Library
- 109.j. Mitchell. Guillotine subdivisions approximate polygonal subdivisions: Part II- A simple PTAS for geometric k-MST, TSP, and related problems. Preliminary manuscript, April 30, 1996. To appear in SIAM J. Computing. Google ScholarDigital Library
- 110.A. Panconesi and D. Ranjan. Quantifiers and approximation. In Proc. of the ~~nd A CM Syrup. on the Theory of Computing, pages 446-456, 1990. Google ScholarDigital Library
- 111.C. Papadimi/riou and M. Yannatm_kis. Optimization, approximation and complexity classes. Journal of Computer and System Sciences, 43:425- 440, 1991. Prelim. version in Proc. A CM STOC 1988. Google ScholarDigital Library
- 112.C. Papadimitriou and M. Yannakakis. The traveling salesman problem with distances one and two. Mathematics of Operations Research, 18(1):1-11, 1993. Google ScholarDigital Library
- 113.R. Raz. A parallel repetition theorem. Proceedings of the Twenty Seventh Annum Symposium on the Theory of Computing, ACM, 1995. Google ScholarDigital Library
- 114.R. Raz and S. Safra. A sub-constant errorprobability low-degree test, and a sub-constant error-probability PCP characterization of NP. Proceedings of the Twenty Eighth Annum Symposium on the Theory of Computing, ACM, 1997. Google ScholarDigital Library
- 115.R. Rubinfeld. A Mathematical Theory of Self. Checking, Self. Testing and Self-Correcting Pro. grams. Ph.D. thesis, U.C. Berkeley, 1990. Google ScholarDigital Library
- 116.R. Rubinfeld and M. Sudan. Testing polynomial functions efficiently and over rational domains. In Proc. 3rd Annual A CM-SIAM Syrup. on Discrete Algorithms, pages 23-32, 1992. Google ScholarDigital Library
- 117.S. Sahni. Approximate algorithms for the 0/1 knapsack problem. Journal of the A CM, 22(1):115-124, 1975. Google ScholarDigital Library
- 118.S. Sahni and T. Gonzalez. P-complete approximation problems. Journal of the A CM, 23:555-565, 1976. Google ScholarDigital Library
- 119.T. J. Schaefer. The Complexity of Satisfiability Problems. In Proc. lOth ACM STOG, pp 216- 226, 1978. Google ScholarDigital Library
- 120.A. Shamir. IP -- PSPACE. J. of the A CM, 39(4):869-877, October 1992. Google ScholarDigital Library
- 121.D. Shmoys. Cut problems and their application to divide-and-conquer. In {75}. Google ScholarDigital Library
- 122.H. U. Simon. On approximate solutions for combinatorial optimization problems. SIAM J. Al~e. braic Discrete Methods, 3:294-310, 1990.Google Scholar
- 123.M. Sudan. Efficient checking of polynomials and proofs and the hardness of approximation problems. PhD thesis, U.C. Berkeley, 1992. Google ScholarDigital Library
- 124.A. Wigderson. Improving the Performance Guarantee for Approximate Graph Coloring. JACM 30(4):729-735, 1983. Google ScholarDigital Library
- 125.M. Yannakakis. The effect of a connectivity requirement on the complexity of of maximum subgraph problems. Journal of the A CM, 26:618-630, 1979. Google ScholarDigital Library
- 126.M. Yannakakis. Edge deletion problems. SIAM Journal of Computing, 10:77-89, 1981.Google ScholarCross Ref
- 127.M. Yannakakis. On the approximation of ma.ximum satisfiability. In Proceedings of 8rd Annual A CM-SIAM Symposium on Discrete Algorithms, pages 1-9, 1992. Google ScholarDigital Library
- 128.D. Zuckerman. NP-complete problems have a version that's hard to approximate. In 8th Structure in Complexity Theory Conf., pages 305-312, 1993.Google ScholarCross Ref
Index Terms
- The approximability of NP-hard problems
Recommendations
Problems and Techniques
The Problems and Techniques section in this issue contains three papers on very different topics: achieving reliability through optimization, improving the solution of systems of linear equations by preconditioning, and determining asymptotic ...
Weakly Hard Problems
A weak completeness phenomenon is investigated in the complexity class ${\rm E}= {\rm DTIME}(2^{\rm linear})$. According to standard terminology, a language $H$ is $\leq^{\rm P}_{m}$- hard for E if the set ${\rm P}_{m}(H)$, consisting of all languages ...
Comments