No Input, No Output   J. Strummer

Home Research Teaching Pubblications Activities Students index.htmlResearch.htmlTeaching.htmlActivities.htmlStudents.htmlshapeimage_2_link_0shapeimage_2_link_1shapeimage_2_link_2shapeimage_2_link_3shapeimage_2_link_4shapeimage_2_link_5
 

More Recent & Manuscripts

Journals

Conference Proceedings

O. Beyersdorff, N. Galesi, M. Lauria. A lower bound for Pigeonhole Principle in Treelike Resolution by Asymmetric Prover Delayer Game. Information Processing Letters. 110. pp. 1044-1047 (2010). N.Galesi, M. Lauria. On the automatizabilty of Polynomial Calculus. Theory of Computing Systems 47(2). pp 491-506. 2010. N. Galesi, M. Lauria. Optimality of size-degree tradeoffs for Polynomial Calculus. ACM Transactions on Computational Logic. Theory of Computing Systems 47(2). pp 491-506. 2010. J. Buresh-Oppenheim, N. Galesi, A. Magen, S. Hoory, T. Pitassi. Rank Bounds and Integrality Gaps for Cutting Planes Procedures. Theory of Computing 2(1) pp. 65--90, 2006. N. Galesi, O. Kullmann. Polynomial SAT decision, hypergraph transversals and Hermitian rank. SAT 05 Selected Papers, LNCS 3542, pp. 89--104. J.L. Esteban, N. Galesi, J. Messner. On the Complexity of Resolution with Bounded Conjunctions. Theoretical Computer Science. 321(2-3)pp. 347-370 2004. E. Ben-Sasson, N. Galesi. Space Complexity of Random Formulae in Resolution. Random Structures and Algorithms, Vol 23(1). 2003 pp.92-109. A. Atserias, N Galesi, P.Pudlák. Monotone Simulations of Nonmonotone Proofs. Journal of Computer and System Sciences, Vol 65. 2002. pp. 626-638. M.L. Bonet, N. Galesi. Degree Complexity for a Modified PigeonHole Principle. Archive for Mathematical Logic, vol 42 (5). 2003 pp.403-414. M.L. Bonet, N. Galesi. Optimality of Size-Width Tradeoffs for Resolution. Computational Complexity, Vol 10(4) 2001. pp. 261-276. A. Atserias, N Galesi, R. Gavaldá. Monotone Proofs of the Pigeonhole Principle. Mathematical Logic Quarterly, Vol. 47(4). 2001, pp. 461-474. M.L. Bonet, J.L. Esteban, N Galesi, J. Johannsen. On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systems. Siam Journal on Computing, Vol. 30(5). 2000, pp. 1462-1484. M.L. Bonet, N. Galesi. Linear Lower Bounds and Simulations in Frege Systems with Substitutions. Selected Papers of 11-th CSL, Lecture Notes in Computer Science, Vol 1414. 1998, pp. 115-128. N. Galesi. A Syntactic Characterization of Bounded-Rank Decision Trees in terms of Decision Lists. RAIRO-Theoretical Informatics and Applications, Vol 31(2). 1997, pp. 149-158. S. Caporaso, M. Zito, N. Galesi. A Predicative and Decidable Characterization of the Polynomial Classes of Languages. Theoretical Computer Science, Vol 251(1-2). 2001, pp. 83-99. http://www.dsi.uniroma1.it/%7Egalesi/tree-like-php.pdfhttp://www.dsi.uniroma1.it/%7Egalesi/tree-like-php.pdfhttp://www.dsi.uniroma1.it/%7Egalesi/autom.pdfhttp://www.dsi.uniroma1.it/%7Egalesi/gop.pdfhttp://www.dsi.uniroma1.it/%7Egalesi/cp.pdfhttp://www.dsi.uniroma1.it/%7Egalesi/cp.pdfhttp://www.dsi.uniroma1.it/%7Egalesi/galkul.pshttp://www.dsi.uniroma1.it/%7Egalesi/papers/tcs2.pshttp://www.dsi.uniroma1.it/%7Egalesi/randomspace.pshttp://www.dsi.uniroma1.it/%7Egalesi/monsim.pshttp://www.dsi.uniroma1.it/%7Egalesi/archive.pshttp://www.dsi.uniroma1.it/%7Egalesi/width.pshttp://www.dsi.uniroma1.it/~galesi/mlq.pdfhttp://www.dsi.uniroma1.it/~galesi/SIAM.pdfhttp://www.dsi.uniroma1.it/~galesi/SIAM.pdfhttp://www.dsi.uniroma1.it/%7Egalesi/csl.pshttp://www.dsi.uniroma1.it/%7Egalesi/rairo.pshttp://www.dsi.uniroma1.it/~galesi/papers/02062305330013394.pdfhttp://www.dsi.uniroma1.it/~galesi/papers/02062305330013394.pdfshapeimage_3_link_0shapeimage_3_link_1shapeimage_3_link_2shapeimage_3_link_3shapeimage_3_link_4shapeimage_3_link_5shapeimage_3_link_6shapeimage_3_link_7shapeimage_3_link_8shapeimage_3_link_9shapeimage_3_link_10shapeimage_3_link_11shapeimage_3_link_12shapeimage_3_link_13shapeimage_3_link_14shapeimage_3_link_15shapeimage_3_link_16shapeimage_3_link_17shapeimage_3_link_18
O. Beyersdorff, N. Galesi, M. Lauria, A Razborov. Parameterized Bounded-Depth Frege is Not Optimal (2010) L. Carlucci, N.Galesi, M. Lauria Paris-Harrington Tautologies. (2010) O. Beyersdorff, N. Galesi, M. Lauria. Hardness of Parameterized Resolution ECCC 2010 O. Beyersdorf, N Galesi, M. Lauria. The strength of Parameterized tree-like Resolution. (2010) N. Galesi, M. Lauria. Extending Polynomial Calculus with k-DNF Resolution. ECCC 2007http://www.dsi.uniroma1.it/~galesi/parres.pdfhttp://www.dsi.uniroma1.it/~galesi/PH.pdfhttp://www.dsi.uniroma1.it/%7Egalesi/dagphp-full-version.pdfhttp://livepage.apple.com/http://www.dsi.uniroma1.it/~galesi/TR.pdfshapeimage_4_link_0shapeimage_4_link_1shapeimage_4_link_2shapeimage_4_link_3shapeimage_4_link_4
N. Galesi, N. Thapen. Resolution and Pebbling Games. SAT 05, LNCS 3569, pp. 76--90 N. Galesi, N. Thapen. The Complexity of Treelike Systems over l-Local Formulae 19th IEEE Conference on Computational Complexity (CCC), Amherst (MA), 2004. J. Buresh-Oppenheim, N. Galesi, A. Magen, S. Hoory, T. Pitassi. Rank Bounds and Integrality Gaps for Cutting Planes Procedures. 44th IEEE Symposium on Foundations of Computer Science (FOCS) Boston (MA), Usa. October 11-14, 2003. J.L. Esteban, N. Galesi, J. Messner. On the Complexity of Resolution with Bounded Conjunctions. 29th International Colloquium on Automata, Languages and Programming (ICALP), Malaga, Spain. July 8-13, 2002. Lectures Notes in Computer Science 2380, pp. 220-231. E. Ben-Sasson, N. Galesi. Space Complexity of Random Formulae in Resolution. 16th IEEE Conference on Computational Complexity (CCC), Chicago, Illinois. June 18-21, 2001. pp. 42-51. A. Atserias, N. Galesi, P.Pudlák. Monotone Simulations of Nonmontone Proofs. 16th IEEE Conference on Computational Complexity (CCC), Chicago, Illinois, June 18-21, 2001. pp. 36-41. A. Atserias, N. Galesi, R. Gavaldå. Monotone Proofs of the Pigeonhole Principle. 27th International Colloquium on Automata, Languages and Programming (ICALP), Geneva, Switzerland. July 9-15, 2000. pp. 36-41. M.L. Bonet, N. Galesi. A Study of Proof Search Algorithms for Resolution and Polynomial Calculus. 40th IEEE Symposium on Foundations of Computer Science (FOCS), New York City, New York. October 17-19, 1999. pp. 422-431. M.L. Bonet, J.L Esteban, N. Galesi, J. Johannsen. Exponential Seprations between Restricted Resolution and Cutting Planes Proof Systems. 39th IEEE Symposium on Foundations of Computer Science (FOCS), Palo Alto, California. November 8-11, 1998. pp. 638-647. M.L. Bonet, N. Galesi. A Linear Lower Bounds and Simulations in Frege Systems with Substitutions. 11th Annual Conference of EACSL, Computer Science Logic (CSL), Aarhus, Denmark. August 23-29, 1997. pp. . S. Caporaso. M. Covino, N. Galesi, M. Zito. A Syntactic Characterization in LISP of the Polynomial Complexity Classes and Hierarchy. 3rd Italian Conference on Algorithms and Complexity (CIAC), Rome, Italy. March 12-14, 1997. Lecture Notes in Computer Science 1203. pp. 61-73.
 

Thesis

N. Galesi, On the COmplexity of Propositional proof Systems. Universitat Politécnica de Catalunya. 2000