Autour de nouvelles notions pour l'analyse des algorithmes d'approximation: De la structure de NPO à la structure des instances = About new notions for the approximation algorithm analysis: from thoe NPO structure to the instance structureDEMANGE, Marc; PASCHOS, Vangelis.RAIRO. Recherche opérationnelle. 2002, Vol 36, Num 4, pp 311-350, issn 0399-0559, 40 p.Article

Autour de nouvelles notions pour l'analyse des algorithmes d'approximation: Formalisme unifié et classes d'approximation = About new notions for approximation algorithm analysis: unified formalism and approximation classesDEMANGE, Marc; PASCHOS, E. T.RAIRO. Recherche opérationnelle. 2002, Vol 36, Num 3, pp 237-277, issn 0399-0559, 41 p.Article

ON PROXIMITY-OBLIVIOUS TESTINGGOLDREICH, Oded; RON, Dana.SIAM journal on computing (Print). 2011, Vol 40, Num 2, pp 534-566, issn 0097-5397, 33 p.Article

A polynomial bound on the number of comaximal localizations needed in order to make free a projective moduleDIAZ-TOCA, Gema M; LOMBARDI, Henri.Linear algebra and its applications. 2011, Vol 435, Num 2, pp 354-360, issn 0024-3795, 7 p.Article

A COUNTEREXAMPLE TO STRONG PARALLEL REPETITION : Foundation of Computer ScienceRAZ, Ran.SIAM journal on computing (Print). 2011, Vol 40, Num 3, pp 771-777, issn 0097-5397, 7 p.Article

A NEAR-OPTIMAL SEPARATION OF REGULAR AND GENERAL RESOLUTIONURQUHART, Alasdair.SIAM journal on computing (Print). 2011, Vol 40, Num 1, pp 107-121, issn 0097-5397, 15 p.Article

Comment: Improvement of Weyl's Inequality. By M. G. Marmorino et alMARMORINO, M. G.Journal of mathematical chemistry. 2007, Vol 41, Num 3, pp 327-327, issn 0259-9791, 1 p.Article

A complete classification of the complexity of propositional abductionCREIGNOU, Nadia; ZANUTTINI, Bruno.SIAM journal on computing (Print). 2007, Vol 36, Num 1, pp 207-229, issn 0097-5397, 23 p.Article

Complexity results for prefix grammarsLOHREY, Markus; PETERSEN, Holger.Informatique théorique et applications (Imprimé). 2005, Vol 39, Num 2, pp 391-401, issn 0988-3754, 11 p.Article

MATRIX p-NORMS ARE NP-HARD TO APPROXIMATE IFHENDRICKX, Julien M; OLSHEVSKY, Alex.SIAM journal on matrix analysis and applications. 2010, Vol 31, Num 5, pp 2802-2812, issn 0895-4798, 11 p.Article

The complexity of finite model reasoning in description logicsLUTZ, Carsten; SATTLER, Ulrike; TENDERA, Lidia et al.Information and computation (Print). 2005, Vol 199, Num 1-2, pp 132-171, issn 0890-5401, 40 p.Conference Paper

String distances and intrusion detection : Bridging the gap between formal languages and computer securityBRUSCHI, Danilo; PIGHIZZINI, Giovanni.Informatique théorique et applications (Imprimé). 2006, Vol 40, Num 2, pp 303-313, issn 0988-3754, 11 p.Article

There are no sparse NP_W-HARD setsCUCKER, Felipe; GRIGORIEV, Dima.SIAM journal on computing (Print). 2001, Vol 31, Num 1, pp 193-198, issn 0097-5397Article

A LOWER BOUND FOR THE SIZE OF SYNTACTICALLY MULTILINEAR ARITHMETIC CIRCUITSRAZ, Ran; SHPILKA, Amir; YEHUDAYOFF, Amir et al.SIAM journal on computing (Print). 2009, Vol 38, Num 4, pp 1624-1647, issn 0097-5397, 24 p.Article

The rectilinear steiner arborescence problem is NP-completeWEIPING SHI; CHEN SU.SIAM journal on computing (Print). 2006, Vol 35, Num 3, pp 729-740, issn 0097-5397, 12 p.Article

A new multilayered pcp and the hardness of hypergraph vertex coverDINUR, Irit; GURUSWAMI, Venkatesan; KHOT, Subhash et al.SIAM journal on computing (Print). 2005, Vol 34, Num 5, pp 1129-1146, issn 0097-5397, 18 p.Article

Perfectness is an elusive graph propertyHOUGARDY, Stefan; WAGLER, Annegret.SIAM journal on computing (Print). 2005, Vol 34, Num 1, pp 109-117, issn 0097-5397, 9 p.Article

Distance desert automata and the star height problemKIRSTEN, Daniel.Informatique théorique et applications (Imprimé). 2005, Vol 39, Num 3, pp 455-509, issn 0988-3754, 55 p.Conference Paper

ALGORITHMIC ASPECTS OF PROPERTY TESTING IN THE DENSE GRAPHS MODELGOLDREICH, Oded; RON, Dana.SIAM journal on computing (Print). 2011, Vol 40, Num 2, pp 376-445, issn 0097-5397, 70 p.Article

ON THE PARAMETERIZED COMPLEXITY OF APPROXIMATE COUNTINGANDRES MONTOYA, J.Informatique théorique et applications (Imprimé). 2011, Vol 45, Num 2, pp 197-223, issn 0988-3754, 27 p.Article

AN ISOMORPHISM BETWEEN SUBEXPONENTIAL AND PARAMETERIZED COMPLEXITY THEORYYIJIA CHEN; GROHE, Martin.SIAM journal on computing (Print). 2008, Vol 37, Num 4, pp 1228-1258, issn 0097-5397, 31 p.Article

Assignment testers : Towards A combinatorial proof of the PCP theoremDINUR, Irit; REINGOLD, Omer.SIAM journal on computing (Print). 2007, Vol 36, Num 4, pp 975-1024, issn 0097-5397, 50 p.Article

COMPUTATIONAL COMPLEXITY OF HOLANT PROBLEMSCAI, Jin-Yi; PINYAN LU; MINGJI XIA et al.SIAM journal on computing (Print). 2011, Vol 40, Num 4, pp 1101-1132, issn 0097-5397, 32 p.Article

SEMANTICS AND COMPUTABILITY OF THE EVOLUTION OF HYBRID SYSTEMSCOLLINS, Pieter.SIAM journal on control and optimization. 2011, Vol 49, Num 2, pp 890-925, issn 0363-0129, 36 p.Article

CLIQUE-WIDTH IS NP-COMPLETEFELLOWS, Michael R; ROSAMOND, Frances A; ROTICS, Udi et al.SIAM journal on discrete mathematics (Print). 2010, Vol 23, Num 2, pp 909-939, issn 0895-4801, 31 p.Article