Contents

• Most recent preprints
• Publications in refereed conferences and journals
• Invited and other papers
• Theses
• Program committees

Most recent preprints

• A. Atserias, M. Müller, and S. Oliva
  Proof Complexity of Relativized Statements,
  Manuscript, 2012.
  pdf

• A. Atserias and E. Maneva
  Sherali-Adams Relaxations and Indistinguishability in Counting Logics,
  in Proceedings of 3rd ACM-SIGACT Innovations in Theoretical Computer Science (ITCS), 2012.
  pdf

• A. Atserias and M. Müller
  Partially definable forcing and bounded arithmetic,
  Manuscript, 2011.
  pdf

Publications in competitive conferences and refereed journals

• A. Atserias, J. K. Fichte, and M. Thurley
  Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution,
  Journal of Artificial Intelligence Research, Vol. 40, pp. 353-373, 2011.
  A preliminary version appeared in the Proceedings of 12th International Conference on Theory and Applications of Satisfiability Testing (SAT), volume 5584 of Lecture Notes in Computer Science, Springer-Verlag, pp. 114--127, 2009.
  pdf

• A. Atserias and E. Maneva
  Mean-payoff games and propositional proofs,
  Information and Computation, Vol. 209, Issue 4, pp. 664-691, 2011.
  A preliminary version appeared in the Proceedings of 34th International Colloquium on Automata, Languages and Programming (ICALP), volume 6198 of Lecture Notes in Computer Science, Springer-Verlag, pp. 102-113, 2010.
  pdf

• A. Atserias and M. Weyer
  Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems,
  in Proceedings of 18th Annual Conference of the European Association for Computer Science Logic (CSL), volume 5771 of Lecture Notes in Computer Science, Springer-Verlag, pp. 102-116, 2009.
  pdf

• A. Atserias, M. Grohe, and D. Marx.
  Size bounds and query plans for relational joins,
  submitted for journal publication, 2011.
  A preliminary version appeared in the Proceedings of 49th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 739-748, 2008.
  pdf.

• A. Atserias, A. Bulatov, A. Dawar.
  Affine Systems of Equations and Counting Infinitary Logic,
  Theoretical Computer Science 410(18), pp. 1666-1683, 2009.
  A preliminary version appeared in the Proceedings of 34th International Colloquium on Automata, Languages and Programming (ICALP), volume 4596 of Lecture Notes in Computer Science, Springer-Verlag, pp. 558-570, 2007.
  pdf.

• A. Atserias, A. Bulatov, V. Dalmau.
  On the Power of k-Consistency,
  in Proceedings of 34th International Colloquium on Automata, Languages and Programming (ICALP), volume 4596 of Lecture Notes in Computer Science, Springer-Verlag, pp. 279-290, 2007.
  pdf.

• A. Atserias.
  Distinguishing SAT from Polynomial-Size Circuits, through Black-Box Queries,
  in Procceedings of 21st Annual IEEE Conference on Computational Complexity (CCC), pp. 88-95, 2006.
  pdf.

• A. Atserias, A. Dawar, and M. Grohe.
  Preservation under Extensions on Well-Behaved Finite Structures,
  SIAM Journal on Computing 38, pages 18-34, 2008.
  A preliminary version appeared in the Proceedings of 32nd International Colloquium on Automata, Languages and Programming (ICALP), volume 3580 of Lecture Notes in Computer Science, Springer-Verlag, pages 1437-1449, 2005.
  pdf.

• A. Atserias.
  On Digraph Coloring Problems and Treewidth Duality,
  European Journal of Combinatorics 29(4), pages 796-820, 2008.
  A preliminary version appeared in the Proceedings of 20th IEEE Symposium on Logic in Computer Science (LICS), pages 106-115, 2005.
  pdf.

• A. Atserias.
  Definability on a Random 3-CNF Formula,
  in Proceedings of 20th IEEE Symposium on Logic in Computer Science (LICS), pages 458-466, 2005.
  pdf.

• A. Atserias.
  Conjunctive Query Evaluation by Search-Tree Revisited,
  Theoretical Computer Science, 371, pages 155-168, 2007.
  A preliminary version appeared in the Proceedings of 10th International Conference on Database Theory (ICDT), volume 3363 of Lecture Notes in Computer Science, pages 53-67, Springer-Verlag, 2005.
  pdf

• A. Atserias, Ph. G. Kolaitis, and M. Y. Vardi.
  Constraint Propagation as a Proof System,
  in Proceedings of 10th International Conference on Principles and Practice of Constraint Programming (CP), volume 3258 of Lecture Notes in Computer Science, pages 77-91, Springer-Verlag, 2004.
  pdf

• A. Atserias, A. Dawar, and Ph. G. Kolaitis.
  On Preservation under Homomorphisms and Unions of Conjunctive Queries,
  Journal of the ACM, 53(2), pages 208-237, 2006.
  A preliminary version appeared in the Proceedings of 23rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS), pages 319-329, 2004.
  pdf.

• A. Atserias and V. Dalmau.
  A Combinatorial Characterization of Resolution Width,
  Journal of Computer and System Sciences, 74(3), pages 323-334, 2008.
  A preliminary version appeared in the Proceedings of 18th IEEE Conference on Computational Complexity (CCC), pages 239-247, 2003.
  pdf.

• A. Atserias and M. L. Bonet.
  On the Automatizability of Resolution and Related Propositional Proof Systems,
  Information and Computation, 189(2), pages 182-201, 2004.
  A preliminary version appeared in the Proceedings of 11th Annual Conference of the EACSL (CSL), volume 2471 of Lecture Notes in Computer Science, Springer-Verlag, pages 569-583, 2002.
  pdf.

• A. Atserias.
  On Sufficient Conditions for Unsatisfiability of Random Formulas,
  Journal of the ACM, 51(2), pages 281-311, 2004.
  A preliminary version appeared in the Proceedings of 17th IEEE Symposium on Logic in Computer Science (LICS), pages 325-334, 2002, under the title "Unsatisfiable Random Formulas are Hard to Certify".
  pdf.

• A. Atserias.
  Improved Bounds on the Weak Pigeonhole Principle and Infinitely Many Primes from Weaker Axioms,
  Theoretical Computer Science 295(1-3), pages 27-39, 2003.
  A preliminary version appeared in the Proceedings of 26th International Symposium on Mathematical Foundations of Computer Science (MFCS), volume 2136 of Lecture Notes in Computer Science, pages 148-158, Springer-Verlag, 2001.
  pdf.

• A. Atserias, M. L. Bonet, and J. L. Esteban.
  Lower Bounds for the Weak Pigeonhole Principle and Random Formulas Beyond Resolution,
  Information and Computation 176(2), pages 136-152, 2002.
  A preliminary version appeared in the Proceedings of 28th International Colloquium on Automata Languages and Programming (ICALP), volume 2076 of Lecture Notes in Computer Science, pages 1005-1016, Springer-Verlag, 2001.
  pdf.

• A. Atserias, N. Galesi, and P. Pudlák.
  Monotone Simulations of Nonmonotone Proofs,
  Journal of Computer and System Sciences 65, pages 626-638, 2002.
  A preliminary version appeared in the Proceedings of 16th IEEE Conference on Computational Complexity (CCC), 2001.
  pdf.

• A. Atserias.
  The Descriptive Complexity of the Fixed-Points of Bounded Formulas,
  in Proceedings of 9th Annual Conference of the EACSL (CSL), volume 1862 of Lecture Notes in Computer Science, pages 172-186, Springer-Verlag, 2000.
  pdf.

• A. Atserias, N. Galesi, and R. Gavaldà.
  Monotone Proofs of the Pigeon Hole Principle,
  Mathematical Logic Quarterly 47(4), pages 461-474, 2001.
  A preliminary version appeared in the Proceedings of 27th International Colloquium on Automata, Languages and Programming (ICALP), volume 1853 of Lecture Notes in Computer Science, pages 151-162, Springer-Verlag, 2000.
  pdf.

• A. Atserias and Ph. G. Kolaitis.
  First-order logic vs. fixed-point logic on finite set theory.,
  in Proceedings of 14th IEEE Symposium on Logic in Computer Science (LICS), 1999.
  pdf.

• A. Atserias and J. Balcázar.
  Refining Logical Characterizations of Advice Complexity Classes,
  in Proceedings of First Panhellenic Symposium on Logic (PLS), pages 157-168, 1997.
  pdf.

Invited, reviews, technical reports, and other papers

• A. Atserias
  Book review: Stephen Cook and Phuong Nguyen. Logical foundations of proof complexity. Perspectives in Logic. Cambridge University Press, New York, 2010, 15+479 pp.,
  The Bulletin of Symbolic Logic 17(3), pp. 462-464. 2011.
  pdf

• A. Atserias and E. Maneva
  Mean-Payoff Games and the Max-Atom Problem,
  technical report, 2009.
  pdf

• A. Atserias.
  Book review: E. Graedel, P. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Vardi, Y. Venema and S. Weinstein. Finite Model Theory and Its Applications. Springer-Verlag, 2007.
  Computer Science Review 2(1), pages 55-59, 2008.
  pdf.

• A. Atserias.
  P vs. NP (i el 10è problema de Hilbert) (in Catalan),
  Invited talk at IV Cicle de Conferències Ferran Sunyer i Balaguer (here), 2005.
  pdf.

• A. Atserias.
  Notions of Average-Case Complexity for Random 3-SAT,
  in 13th Annual Conference of the EACSL (CSL), volume 3210 of Lecture Notes in Computer Science, pages 1-5, Springer-Verlag, 2004.
  Invited talk.
  pdf.

• A. Atserias.
  Complexitat de Kolmogorov i Qüestions de Fonament (in Catalan),
  Butlletí de la Societat Catalana de Matemàtiques 18(1), pàgines 7-17, 2003.
  Invited talk at Sisena Trobada Matemàtica de la Societat Catalana de Matemàtiques, 2003.
  pdf

• A. Atserias.
  Message complexity lower bounds for decentralized anonymous wave algorithms,
  Report LSI-96-5-T, 1996.

Theses

• A. Atserias. Fixed-Point Logics, Descriptive Complexity, and Random Satisfiability, Ph.D. Thesis, Computer Science Department, University of California at Santa Cruz, December 2002. Directed by Ph. G. Kolaitis.
  pdf.

• A. Atserias. The Complexity of Resource-Bounded Propositional Proofs, Ph.D. Thesis, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, February 2002. Co-directed by J. L. Balcázar and M. L. Bonet.
  pdf.

• A. Atserias. Computational aspects of first-order logic on finite structures, M.Sc. Thesis, Computer Science Department, University of California at Santa Cruz, May 1999. Directed by Ph. G. Kolaitis.
  pdf.

Program committees

• 39th International Colloquium on Automata, Languages and Programming (ICALP 2012).
• 26th IEEE Conference on Computational Complexity (CCC 2011).
• Computability in Europe 2011: Models of Computation in Context (CiE 2011).
• ASL European Summer Meeting, Logic Colloquium 2010. (ASL).
• 25th Annual IEEE Symposium on Logic in Computer Science (LICS 2010).
• 11th International Workshop on Logic and Computational Complexity (formerly Implicit Computational Complexity) (LCC 2009).
• 36th International Colloquium on Automata, Languages and Programming (ICALP 2009).
• 12th International Conference on Database Theory (ICDT 2009).
• 23rd IEEE Conference on Computational Complexity (CCC 2008).
• 22nd Annual IEEE Symposium on Logic in Computer Science (LICS 2007).
• 11th International Conference on Database Theory (ICDT 2007).
• 7th International Workshop on Logic and Computational Complexity (formerly Implicit Computational Complexity) (LCC 2005).
• 14th Annual Conference (19th International Workshop) of the European Association for Computer Science Logic (CSL 2005).
• Computability in Europe 2005: New Computational Paradigms (CiE 2005).
• 31st International Colloquium on Automata, Languages and Programming (ICALP 2004).
• 19th Annual IEEE Symposium on Logic in Computer Science (LICS 2004).
• Kalmár Workshop on Logic and Computer Science (2003).

Back to my home page.