First-Order Logic vs. Fixed-Point Logic in Finite Set Theory. - Albert Atserias; Phokion G. Kolaitis (LICS, 1999)

The Descriptive Comlexity of the Fixed-Points of Bounded Formulas. - Albert Atserias (CSL, 2000)

Monotone Proofs of the Pigeon Hole Principle - Albert Atserias; Nicola Galesi; Ricard Gavaldà (Electron. Colloquium Comput. Complex., 2000)

Monotone simulations of nonmonotone propositional proofs - Albert Atserias; Nicola Galesi; Pavel Pudlák (Electron. Colloquium Comput. Complex., 2000)

Monotone Simulations of Nonmonotone Proofs. - Albert Atserias; Nicola Galesi; Pavel Pudlák (CCC, 2001)

Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution. - Albert Atserias; Maria Luisa Bonet; Juan Luis Esteban (ICALP, 2001)

Unsatisfiable Random Formulas Are Hard to Certify. - Albert Atserias (LICS, 2002)

On the Automatizability of Resolution and Related Propositional Proof Systems - Albert Atserias; Maria Luisa Bonet (Electron. Colloquium Comput. Complex., 2002)

Lower Bounds for the Weak Pigeonhole Principle and Random Formulas beyond Resolution. - Albert Atserias; Maria Luisa Bonet; Juan Luis Esteban (Inf. Comput., 2002)

Monotone simulations of non-monotone proofs. - Albert Atserias; Nicola Galesi; Pavel Pudlák (J. Comput. Syst. Sci., 2002)

On Chvatal Rank and Cutting Planes Proofs - Albert Atserias; Maria Luisa Bonet; Jordi Levy (Electron. Colloquium Comput. Complex., 2003)

Improved bounds on the Weak Pigeonhole Principle and infinitely many primes from weaker axioms. - Albert Atserias (Theor. Comput. Sci., 2003)

Constraint Propagation as a Proof System. - Albert Atserias; Phokion G. Kolaitis; Moshe Y. Vardi (CP, 2004)

Notions of Average-Case Complexity for Random 3-SAT. - Albert Atserias (CSL, 2004)

On sufficient conditions for unsatisfiability of random formulas. - Albert Atserias (J. ACM, 2004)

Definability on a Random 3-CNF Formula. - Albert Atserias (LICS, 2005)

Non-Uniform Hardness for NP via Black-Box Adversaries - Albert Atserias (Electron. Colloquium Comput. Complex., 2005)

Distinguishing SAT from Polynomial-Size Circuits, through Black-Box Queries. - Albert Atserias (CCC, 2006)

On preservation under homomorphisms and unions of conjunctive queries. - Albert Atserias; Anuj Dawar; Phokion G. Kolaitis (J. ACM, 2006)

On the Power of k -Consistency. - Albert Atserias; Andrei A. Bulatov; Víctor Dalmau (ICALP, 2007)

Conjunctive query evaluation by search-tree revisited. - Albert Atserias (Theor. Comput. Sci., 2007)

E. Grädel, P. Kolaitis, L. Libkin, M. Marx, I. Spencer, M. Vardi, Y. Venema and S. Weinstein , Finite Model Theory and Its Applications, Springer-Verlag (2007). - Albert Atserias (Comput. Sci. Rev., 2008)

On digraph coloring problems and treewidth duality. - Albert Atserias (Eur. J. Comb., 2008)

A combinatorial characterization of resolution width. - Albert Atserias; Víctor Dalmau (J. Comput. Syst. Sci., 2008)

Preservation under Extensions on Well-Behaved Finite Structures. - Albert Atserias; Anuj Dawar; Martin Grohe (SIAM J. Comput., 2008)

Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems. - Albert Atserias; Mark Weyer (CSL, 2009)

Four Subareas of the Theory of Constraints, and Their Links. - Albert Atserias (MFCS, 2009)

Affine systems of equations and counting infinitary logic. - Albert Atserias; Andrei A. Bulatov; Anuj Dawar (Theor. Comput. Sci., 2009)

Mean-payoff games and propositional proofs. - Albert Atserias; Elitza N. Maneva (Electron. Colloquium Comput. Complex., 2010)

A Why-on-Earth Tutorial on Finite Model Theory. - Albert Atserias (LICS, 2011)

Graph Isomorphism, Sherali-Adams Relaxations and Expressibility in Counting Logics. - Albert Atserias; Elitza N. Maneva (Electron. Colloquium Comput. Complex., 2011)

Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution. - Albert Atserias; Johannes Klaus Fichte; Marc Thurley (J. Artif. Intell. Res., 2011)

Foreword. - Albert Atserias; Mikolaj Bojanczyk; Balder ten Cate; Ronald Fagin; Floris Geerts; Kenneth A. Ross (Theory Comput. Syst., 2011)

Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers. - Albert Atserias; Anuj Dawar (Electron. Colloquium Comput. Complex., 2012)

The Proof-Search Problem between Bounded-Width Resolution and Bounded-Degree Semi-algebraic Proofs. - Albert Atserias (SAT, 2013)

The Ordering Principle in a Fragment of Approximate Counting. - Albert Atserias; Neil Thapen (Electron. Colloquium Comput. Complex., 2013)

Size Bounds and Query Plans for Relational Joins. - Albert Atserias; Martin Grohe; Dániel Marx (SIAM J. Comput., 2013)

Sherali-Adams Relaxations and Indistinguishability in Counting Logics. - Albert Atserias; Elitza N. Maneva (SIAM J. Comput., 2013)

Narrow Proofs May Be Maximally Long. - Albert Atserias; Massimo Lauria; Jakob Nordström (Electron. Colloquium Comput. Complex., 2014)

Bounded-width QBF is PSPACE-complete. - Albert Atserias; Sergi Oliva (J. Comput. Syst. Sci., 2014)

Entailment among Probabilistic Implications. - Albert Atserias; José L. Balcázar (LICS, 2015)

Partially definable forcing and bounded arithmetic. - Albert Atserias; Moritz Müller (Arch. Math. Log., 2015)

A Note on Semi-Algebraic Proofs and Gaussian Elimination over Prime Fields. - Albert Atserias (CoRR, 2015)

Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle. - Albert Atserias; Moritz Müller; Sergi Oliva (J. Symb. Log., 2015)

Non-Homogenizable Classes of Finite Structures. - Albert Atserias; Szymon Torunczyk (CSL, 2016)

On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface. - Albert Atserias; Stephan Kreutzer; Marc Noy (ICALP, 2018)

Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem. - Albert Atserias; Joanna Ochremiak (LICS, 2018)

Proof Complexity (Dagstuhl Seminar 18051). - Albert Atserias; Jakob Nordström; Pavel Pudlák; Rahul Santhanam (Dagstuhl Reports, 2018)

Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs. - Albert Atserias; Tuomas Hakoniemi (CCC, 2019)

Circular (Yet Sound) Proofs. - Albert Atserias; Massimo Lauria (SAT, 2019)

Generalized satisfiability problems via operator assignments. - Albert Atserias; Phokion G. Kolaitis; Simone Severini (J. Comput. Syst. Sci., 2019)

Quantum and non-signalling graph isomorphisms. - Albert Atserias; Laura Mancinska; David E. Roberson; Robert Sámal; Simone Severini; Antonios Varvitsiotis (J. Comb. Theory B, 2019)

Relative Entailment Among Probabilistic Implications. - Albert Atserias; José L. Balcázar; Marie Ely Piceno (Log. Methods Comput. Sci., 2019)

Definable inapproximability: new challenges for duplicator. - Albert Atserias; Anuj Dawar (J. Log. Comput., 2019)

Proof Complexity Meets Algebra. - Albert Atserias; Joanna Ochremiak (ACM Trans. Comput. Log., 2019)

Proofs of Soundness and Proof Search (Invited Talk). - Albert Atserias (FSTTCS, 2020)

Consistency, Acyclicity, and Positive Semirings. - Albert Atserias; Phokion G. Kolaitis (CoRR, 2020)

Automating Resolution is NP-Hard. - Albert Atserias; Moritz Müller (J. ACM, 2020)

On the Expressive Power of Homomorphism Counts. - Albert Atserias; Phokion G. Kolaitis; Wei-Lin Wu (LICS, 2021)

Clique Is Hard on Average for Regular Resolution. - Albert Atserias; Ilario Bonacina; Susanna F. de Rezende; Massimo Lauria; Jakob Nordström; Alexander A. Razborov (J. ACM, 2021)

On the Power of Symmetric Linear Programs. - Albert Atserias; Anuj Dawar; Joanna Ochremiak (J. ACM, 2021)

Towards a Theory of Algorithmic Proof Complexity (Invited Talk). - Albert Atserias (ICALP, 2022)

Promise Constraint Satisfaction and Width. - Albert Atserias; Víctor Dalmau (SODA, 2022)

Finite and Algorithmic Model Theory (Dagstuhl Seminar 22051). - Albert Atserias; Christoph Berkholz; Kousha Etessami; Joanna Ochremiak (Dagstuhl Reports, 2022)

Structure and Complexity of Bag Consistency. - Albert Atserias; Phokion G. Kolaitis (SIGMOD Rec., 2022)

On the Consistency of Circuit Lower Bounds for Non-deterministic Time. - Albert Atserias; Sam Buss; Moritz Müller (STOC, 2023)

Circular (Yet Sound) Proofs in Propositional Logic. - Albert Atserias; Massimo Lauria (ACM Trans. Comput. Log., 2023)

Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem. - Albert Atserias; Joanna Fijalkow (SIAM J. Comput., 2023)

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets. - Albert Atserias; Iddo Tzameret (Electron. Colloquium Comput. Complex., 2024)

Consistency of Relations over Monoids. - Albert Atserias; Phokion G. Kolaitis (Proc. ACM Manag. Data, 2024)

Local-vs-Global Consistency of Annotated Relations. - Albert Atserias (PODS Companion, 2025)

Proof Complexity and Its Relations to SAT Solving (Invited Talk). - Albert Atserias (STACS, 2025)

Simple general magnification of circuit lower bounds. - Albert Atserias; Moritz Müller (CoRR, 2025)

The Proof Analysis Problem. - Noel Arteche; Albert Atserias; Susanna F. de Rezende; Erfan Khaniki (CoRR, 2025)

Consistency Witnesses for Annotated Relations. - Albert Atserias; Phokion G. Kolaitis (SIGMOD Rec., 2025)