NICOLA GALESI

Professore associato

email: nicola.galesi@uniroma1.it





Produzione scientifica

11573/1308191 - 2019 - Resolution and the binary encoding of combinatorial principles
Galesi N. - 04b Atto di convegno in volume
congresso: Conference on Computational Complexity (New Brunswick (USA))
libro: 34th Computational Complexity Conference, CCC 2019, July 18-20, 2019, New Brunswick, NJ, USA. LIPIcs 137 - (978-3-95977-116-0)

11573/1311217 - 2019 - Bounded-depth frege complexity of tseitin formulas for all graphs
Galesi N. - 04b Atto di convegno in volume
congresso: 44th International Symposium on Mathematical Foundations of Computer Science, MFCS 2019 (Norimberga, Germany)
libro: Leibniz International Proceedings in Informatics, LIPIcs - (978-3-95977-117-7)

11573/1350776 - 2019 - Vertex-connectivity for node failure identification in boolean network tomography
Galesi N.; Ranjbar F. - 04b Atto di convegno in volume
congresso: 15th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2019 (Munich, Germany)
libro: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) - (978-3-030-34404-7; 978-3-030-34405-4)

11573/1264314 - 2018 - Cops-Robber games and the resolution of Tseitin Formulas
Galesi, Nicola - 04b Atto di convegno in volume
congresso: 21st International Conference on Theory and Applications of Satisfiability Testing, SAT 2018 (gbr)
libro: 21st International Conference on Theory and Applications of Satisfiability Testing, SAT 2018 Held as Part of the Federated Logic Conference, FloC 2018; Oxford; United Kingdom; 9 July 2018 through 12 July 2018; Code 215249 - (9783319941431)

11573/1264316 - 2018 - Tight bounds for maximal identifiability of failure nodes in boolean network tomography
Galesi, Nicola; Ranjbar, Fariba - 04b Atto di convegno in volume
congresso: 38th IEEE International Conference on Distributed Computing Systems, ICDCS 2018 (Vienna University of Technology (TU Wien), aut)
libro: Proceedings - International Conference on Distributed Computing Systems - (9781538668719)

11573/978134 - 2017 - Space proof complexity for random 3-CNFs
Galesi, Nicola; Wollan, Paul Joseph - 01a Articolo in rivista
rivista: INFORMATION AND COMPUTATION (Orlando, Fla. : Academic Press [New York] : Elsevier Science (USA)) pp. 165-176 - issn: 1090-2651 - wos: WOS:000407658600008 (1) - scopus: 2-s2.0-85021162863 (2)

11573/902276 - 2016 - A framework for space complexity in algebraic proof systems
Bonacina, Ilario; Galesi, Nicola - 01a Articolo in rivista
rivista: JOURNAL OF THE ASSOCIATION FOR COMPUTING MACHINERY (ACM / Association for Computing Machinery:1515 Broadway, 17th Floor:New York, NY 10036:(212)869-7440, EMAIL: acmhelp@hq.acm.org, INTERNET: http://www.acm.org, Fax: (212)944-1318) pp. 1-20 - issn: 0004-5411 - wos: WOS:000357529300006 (3) - scopus: 2-s2.0-84936945139 (9)

11573/902288 - 2016 - On the proof complexity of Paris-harrington and off-diagonal ramsey tautologies
Carlucci, Lorenzo; Galesi, Nicola; Lauria, Massimo - 01a Articolo in rivista
rivista: ACM TRANSACTIONS ON COMPUTATIONAL LOGIC (New York, NY : Association for Computing Machinery, c2000-) pp. 1-25 - issn: 1529-3785 - wos: WOS:000390984400004 (0) - scopus: 2-s2.0-84987984208 (0)

11573/902430 - 2016 - Total space in resolution
Bonacina, Ilario; Galesi, Nicola - 01a Articolo in rivista
rivista: SIAM JOURNAL ON COMPUTING (Society for Industrial and Applied Mathematics:3600 University City Science Center:Philadelphia, PA 19104:(800)447-7426, (215)382-9800, EMAIL: service@siam.org, INTERNET: http://www.siam.org, Fax: (215)386-7999) pp. 1894-1909 - issn: 0097-5397 - wos: WOS:000387321500007 (2) - scopus: 2-s2.0-85010644516 (4)

11573/908272 - 2015 - The space complexity of cutting planes refutations
Galesi, Nicola - 04b Atto di convegno in volume
congresso: 30th Conference on Computational Complexity, CCC 2015 (Portrland)
libro: Leibniz International Proceedings in Informatics, LIPIcs - (9783939897811; 9783939897811)

11573/643028 - 2014 - Proofs of Space: When Space Is of the Essence
Ateniese, Giuseppe; Galesi, Nicola - 04b Atto di convegno in volume
libro: Security and Cryptography for Networks - 9th International Conference, SCN 2014, Amalfi, Italy, September 3-5, 2014. Proceedings - ()

11573/853471 - 2014 - Total space in resolution
Bonacina, Ilario; Galesi, Nicola - 04b Atto di convegno in volume
congresso: 55th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2014 (Radisson Blu Warwick Hotel, usa)
libro: Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS - (9781479965175; 9781479965175)

11573/902316 - 2014 - Proofs of space: when space is of the essence - Security and Cryptography for Networks - 9th International Conference, SCN 2014, Proceedings
Ateniese, Giuseppe; Bonacina, Ilario; Faonio, Antonio; Galesi, Nicola - 02a Capitolo o Articolo
libro: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) - (9783319108780; 9783319108780)

11573/496975 - 2013 - Pseudo-Partitions, Transeversality and Locality: A combinatorial characterization for Space measure in Algebraic Systems
Galesi, Nicola - 04b Atto di convegno in volume
congresso: Innovations in Theoretical Computer Science (Berkeley)
libro: Proc. Innovations in Theoretical Computer Science - ()

11573/496979 - 2013 - Parameterized Complexity of DPLL Search Procedures
Galesi, Nicola; Lauria, Massimo - 01a Articolo in rivista
rivista: ACM TRANSACTIONS ON COMPUTATIONAL LOGIC (New York, NY : Association for Computing Machinery, c2000-) pp. 1-21 - issn: 1529-3785 - wos: WOS:000323892900004 (13) - scopus: 2-s2.0-84879381038 (17)

11573/718353 - 2013 - A characterization of tree-like Resolution size
Beyersdorff, Olaf; Galesi, Nicola; Lauria, Massimo - 01a Articolo in rivista
rivista: INFORMATION PROCESSING LETTERS (-Amsterdam : Elsevier Science -Amsterdam : North-Holland) pp. 666-671 - issn: 0020-0190 - wos: WOS:000322610700005 (9) - scopus: 2-s2.0-84879377601 (16)

11573/490888 - 2012 - Parameterized bounded-depth Frege is not optimal
Galesi, Nicola; Lauria, Massimo - 01a Articolo in rivista
rivista: ACM TRANSACTIONS ON COMPUTATION THEORY (New York, N.Y. : Association for Computing Machinery) pp. 1-16 - issn: 1942-3454 - wos: (0) - scopus: 2-s2.0-84868675131 (11)

11573/379820 - 2011 - Paris-Harrington tautologies
Carlucci, Lorenzo; Galesi, Nicola; Lauria, Massimo - 04b Atto di convegno in volume
congresso: 26th Annual IEEE Conference on Computational Complexity (CCC) (San Jose, CA)
libro: Proceedings of the 26th Annual IEEE Conference on Computational Complexity - (9780769544113)

11573/391744 - 2011 - Parameterized bounded-depth Frege is not optimal
Galesi, Nicola; Lauria, Massimo - 04b Atto di convegno in volume
congresso: 38th International Colloquium on Automata, Languages and Programming, ICALP 2011 (Zurich)
libro: Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I 2011 - (9783642220050; 9783642220067)

11573/392502 - 2011 - Parameterized complexity of DPLL search procedures
Galesi, Nicola; Lauria, Massimo - 04b Atto di convegno in volume
congresso: 14th International Conference on Theory and Applications of Satisfiability Testing, SAT 2011 (Ann Arbor, MI)
libro: Theory and Applications of Satisfiability Testing - SAT 2011 14th International Conference, SAT 2011, Ann Arbor, MI, USA, June 19-22, 2011. Proceedings - (9783642215803; 9783642215810)

11573/133664 - 2010 - Optimality of size-degree tradeoffs for polynomial calculus
Galesi, Nicola; Lauria, Massimo - 01a Articolo in rivista
rivista: ACM TRANSACTIONS ON COMPUTATIONAL LOGIC (New York, NY : Association for Computing Machinery, c2000-) pp. 1-22 - issn: 1529-3785 - wos: WOS:000284931300004 (16) - scopus: 2-s2.0-78649352528 (16)

11573/133793 - 2010 - A lower bound for the pigeonhole principle in tree-like Resolution by asymmetric Prover-Delayer games
Galesi, Nicola; Lauria, Massimo - 01a Articolo in rivista
rivista: INFORMATION PROCESSING LETTERS (-Amsterdam : Elsevier Science -Amsterdam : North-Holland) pp. 1074-1077 - issn: 0020-0190 - wos: WOS:000284388500009 (9) - scopus: 2-s2.0-77957276708 (12)

11573/208782 - 2010 - On the Automatizability of Polynomial Calculus
Galesi, Nicola; Lauria, Massimo - 01a Articolo in rivista
rivista: THEORY OF COMPUTING SYSTEMS (Springer-Verlag New York Incorporated:175 Fifth Avenue:New York, NY 10010:(212)460-1500, EMAIL: orders@springer-ny.com, INTERNET: http://www.springer-ny.com, Fax: (212)533-3503) pp. 491-506 - issn: 1432-4350 - wos: WOS:000278029300008 (6) - scopus: 2-s2.0-77952958208 (11)

11573/133120 - 2006 - Rank Bounds and Integrality Gaps for Cutting Planes Procedures
Galesi, Nicola - 01a Articolo in rivista
rivista: THEORY OF COMPUTING ([Chicago, Ill. : Department of Computer Science, University of Chicago], 2005-) pp. 65-90 - issn: 1557-2862 - wos: (0) - scopus: (0)

11573/163165 - 2005 - Resolution and Pebbling Games
Galesi, Nicola - 04b Atto di convegno in volume
libro: Theory and Applications of Satisfiability Testing, 8th International Conference, SAT 2005 - (9783540262763)

11573/133655 - 2004 - On the complexity of resolution with bounded conjunctions
Galesi, Nicola - 01a Articolo in rivista
rivista: THEORETICAL COMPUTER SCIENCE (Elsevier BV:PO Box 211, 1000 AE Amsterdam Netherlands:011 31 20 4853757, 011 31 20 4853642, 011 31 20 4853641, EMAIL: nlinfo-f@elsevier.nl, INTERNET: http://www.elsevier.nl, Fax: 011 31 20 4853598) pp. 347-370 - issn: 0304-3975 - wos: WOS:000223383700009 (19) - scopus: 2-s2.0-3242685008 (24)

11573/162896 - 2004 - Polynomial Time SAT Decision, Hypergraph Transversals and the Hermitian Rank
Galesi, Nicola - 04b Atto di convegno in volume
libro: Theory and Applications of Satisfiability Testing, 7th International Conference, SAT 2004 - (9783540278290)

11573/205902 - 2004 - The Complexity of Treelike Systems over lamdda-Local Formulae
Galesi, Nicola - 04b Atto di convegno in volume
libro: 19th Annual IEEE Conference on Computational Complexity (CCC 2004) - ()

11573/133656 - 2003 - Space complexity of random formulae in resolution
Galesi, Nicola - 01a Articolo in rivista
rivista: RANDOM STRUCTURES & ALGORITHMS (John Wiley & Sons Incorporated:Customer Service, 111 River Street:Hoboken, NJ 07030:(800)225-5945, (201)748-6000, EMAIL: societyinfo@wiley.com, INTERNET: http://www.wiley.com, Fax: (212)748-6551) pp. 92-109 - issn: 1042-9832 - wos: WOS:000184211400005 (32) - scopus: 2-s2.0-0042806264 (42)

11573/133658 - 2003 - Degree complexity for a modified pigeonhole principle
Galesi, Nicola - 01a Articolo in rivista
rivista: ARCHIVE FOR MATHEMATICAL LOGIC (Springer Verlag Germany:Tiergartenstrasse 17, D 69121 Heidelberg Germany:011 49 6221 3450, EMAIL: g.braun@springer.de, INTERNET: http://www.springer.de, Fax: 011 49 6221 345229) pp. 403-414 - issn: 0933-5846 - wos: WOS:000183780000001 (1) - scopus: 2-s2.0-0037998778 (2)

11573/208299 - 2003 - Rank Bounds and Integrality Gaps for Cutting Planes Procedures
Galesi, Nicola - 04b Atto di convegno in volume
libro: 44th Symposium on Foundations of Computer Science (FOCS 2003) - ()

11573/133657 - 2002 - Monotone Simulations of Nonmonotone Proofs
Galesi, Nicola - 01a Articolo in rivista
rivista: JOURNAL OF COMPUTER AND SYSTEM SCIENCES (Academic Press Incorporated:6277 Sea Harbor Drive:Orlando, FL 32887:(800)543-9534, (407)345-4100, EMAIL: ap@acad.com, INTERNET: http://www.idealibrary.com, Fax: (407)352-3445) pp. 626-638 - issn: 0022-0000 - wos: WOS:180154300003 (0) - scopus: 2-s2.0-23844483527 (15)

11573/162894 - 2002 - On the complexity of resolution with bounded conjunctions.
Galesi, Nicola - 04b Atto di convegno in volume
libro: Automata, Languages and Programming, 29th International Colloquium, ICALP 2002, - (9783540438649)

11573/133659 - 2001 - Optimality of size-width tradeoffs for resolution
Galesi, Nicola - 01a Articolo in rivista
rivista: COMPUTATIONAL COMPLEXITY (Birkhaeuser Verlag AG:Viaduktstrasse 42-44, CH 4051 Basel Switzerland:011 41 61 2050707, EMAIL: subscriptions@birkhauser.ch, INTERNET: http://www.birkhauser.ch, Fax: 011 41 61 2050792) pp. 261-276 - issn: 1016-3328 - wos: WOS:000182873900001 (34) - scopus: 2-s2.0-0038036843 (49)

11573/133660 - 2001 - Monotone Proofs of the Pigeon Hole Principle
Galesi, Nicola - 01a Articolo in rivista
rivista: MATHEMATICAL LOGIC QUARTERLY (- WILEY-V C H VERLAG GMBH, PO BOX 10 11 61, WEINHEIM, GERMANY, D-69451 -Johann Ambrosius Barth:Prager Strasse 16 B, D-04103 Leipzig Germany:011 49 341 9781570, Fax: 011 49 341 9781575) pp. 461-474 - issn: 0942-5616 - wos: WOS:000172160800005 (2) - scopus: 2-s2.0-0035541203 (4)

11573/133661 - 2001 - A predicative and decidable characterization of the polynomial classes of languages
Galesi, Nicola - 01a Articolo in rivista
rivista: THEORETICAL COMPUTER SCIENCE (Elsevier BV:PO Box 211, 1000 AE Amsterdam Netherlands:011 31 20 4853757, 011 31 20 4853642, 011 31 20 4853641, EMAIL: nlinfo-f@elsevier.nl, INTERNET: http://www.elsevier.nl, Fax: 011 31 20 4853598) pp. 83-99 - issn: 0304-3975 - wos: WOS:000165324800007 (2) - scopus: 2-s2.0-0347983272 (2)

11573/208300 - 2001 - Monotone Simulations of Nonmonotone Proofs.
Galesi, Nicola - 04b Atto di convegno in volume
libro: 16th Annual IEEE Conference on Computational Complexity - ()

11573/208761 - 2001 - Space Complexity of Random Formulae in Resolution
Galesi, Nicola - 04b Atto di convegno in volume
libro: 16th Annual IEEE Conference on Computational Complexity - ()

11573/133662 - 2000 - On the Relative Complexity of Resolution Refinements and Cutting Planes Proof Systemsv
Galesi, Nicola - 01a Articolo in rivista
rivista: SIAM JOURNAL ON COMPUTING (Society for Industrial and Applied Mathematics:3600 University City Science Center:Philadelphia, PA 19104:(800)447-7426, (215)382-9800, EMAIL: service@siam.org, INTERNET: http://www.siam.org, Fax: (215)386-7999) pp. 1462-1484 - issn: 0097-5397 - wos: WOS:000167679200005 (42) - scopus: (0)

11573/162897 - 2000 - Monotone Proofs of the Pigeon Hole Principle
Galesi, Nicola - 04b Atto di convegno in volume
congresso: ICALP (Lecture Notes in Computer Science. Geneva, Switzerland, July 9-15.)
libro: Automata, Languages and Programming, 27th International Colloquium, ICALP 2000 - (9783540677154)

11573/208762 - 1999 - A Study of Proof Search Algorithms for Resolution and Polynomial Calculus
Galesi, Nicola - 04b Atto di convegno in volume
libro: 40th Annual Symposium on Foundations of Computer Science, FOCS '99 - ()

11573/205918 - 1998 - Exponential Separations between Restricted Resolution and Cutting Planes Proof Systems
Galesi, Nicola - 04b Atto di convegno in volume
libro: 39th Annual Symposium on Foundations of Computer Science, FOCS '98, - ()

11573/133663 - 1997 - A Syntactic Characterization of Bounded-Rank Decision Trees in Terms of Decision Lists.
Galesi, Nicola - 01a Articolo in rivista
rivista: RAIRO. INFORMATIQUE THEORIQUE ET APPLICATIONS (Attuale : EDP Sciences 17, avenue du Hoggar - Parc d'Activités de Courtaboeuf - BP 112 - F-91944 Les Ulis Cedex A - France precedenti: -Paris: Elsevier 1997-1998 -Dunod Gauthier Villars:15 rue Gossin, 92543 Montrouge France:011 33 1 40926527, 011 33 1 46565266, Fax: 011 33 1 40926597) pp. 149-158 - issn: 0988-3754 - wos: (0) - scopus: (0)

© Università degli Studi di Roma "La Sapienza" - Piazzale Aldo Moro 5, 00185 Roma