
A. Atserias Towards a Theory of Algorithmic Proof Complexity (Invited Talk). in the Proceedings of 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022), LIPIcs volume 229, 1:11:2, June 29, 2022. 
A. Atserias and V. Dalmau Promise Constraint Satisfaction and Width. in the Proceedings of the 2022 ACMSIAM Symposium on Discrete Algorithms (SODA 2022). Also arXiv:2107.05886 [cs.CC], July 13, 2021. 
A. Atserias, Ph. G. Kolaitis, and WeiLin Wu The Expressive Power of Homomorphism Counts. In the Proceedings of the 26th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2021). Also arxiv:2101.12733 [math.CO], January 29, 2021. 
A. Atserias Proof Search and the Structure of Solution Spaces. In IMTech Newsletter 01, JanuaryJune, 2021. 
A. Atserias and Ph. G. Kolaitis. Structure and Complexity of Bag Consistency. In the Proceedings of the 40th ACM SIGMODSIGACTSIGAI Symposium on Principles of Database Systems (PODS 2021). Also arxiv:2012.12126 [cs.DB], December 22, 2020. 
A. Atserias and Ph. G. Kolaitis. Consistency, Acyclicity, and Positive Semirings. Technical report arxiv:2009.09488 [cs.DB], September 20, 2020. 
A. Atserias and M. Müller. Automating Resolution is NPHard. Journal of the ACM, 67(5), Article No. 31, September 2020. A preliminary version appeared in the Proceedings of 60th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2019), 
A. Atserias, A. Dawar, and J. Ochremiak. On the Power of Symmetric Linear Programs. Submitted, December 2019. A preliminary version appeared in the Proceedings of 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2019), IEEE, pp. 113, Vancouver, Canada, July 2019. 
A. Atserias and T. Hakoniemi. SizeDegree TradeOffs for SumsofSquares and Positivstellensatz Proofs. In the Proceedings of Computational Complexity Conference (CCC 2019), LIPIcs series, vol. 137, pp. 24:124:20, New Brunswick, NJ, USA, July 2019. Longer version at arXiv:1811.01351 [cs.CC], November 2018. 
A. Atserias and A. Dawar. Definable Inapproximability: New Challenges for Duplicator. Journal of Logic and Computation, 29(8), pp. 11851210, December 2019. A preliminary version appeared in the Proceedings of 27th EACSL Annual Conference on Computer Science Logic (CSL 2018), LIPIcs series, vol. 119, pp. 7:1–7:21, September 2018. 
A. Atserias, S. Kreutzer, and M. Noy. On ZeroOne and Convergence Laws for Graphs Embeddable on a Fixed Surface. In the Proceedings of 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), LIPIcs series, vol. 107, pp. 116:1116:14, July 2018. 
A. Atserias and M. Lauria. Circular (Yet Sound) Proofs. Submitted, September 2019. A preliminary version appeared in the Proceedings of 22nd International Conference on Theory and Applications of Satisfiability Testing (SAT 2019), Lecture Notes in Computer Science 11628, Springer, pp. 118, July 2019 
A. Atserias, I. Bonacina, S. F. de Rezende, M. Lauria, J. Nordström, and A. Razborov. Clique Is Hard on Average for Regular Resolution. In the Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), pp. 866877, June 2018. 
A. Atserias and J. Ochremiak. Definable Ellipsoid Method, SumsofSquares Proofs, and the Isomorphism Problem. In the Proceedings of 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2018), pp. 6675, July 2018. Longer version at arxiv.org/abs/1802.02388, February 2018. 
A. Atserias and J. Ochremiak. Proof Complexity Meets Algebra. ACM Transaction on Computational Logic, Vol. 201, Article n. 1, January 2019. A preliminary version appeared in the Proceedings of 44th Annual Colloquium on Automata, Languages and Programming (ICALP 2017), LIPIcs series, pp. 110:1110:14, July 2017. 
A. Atserias, Ph. G. Kolaitis, and S. Severini. Generalized Satisfiability Problems via Operator Assignments. Journal of Computer and Systems Sciences, 105:171198, 2019. A preliminary version appeared in the Proceedings of 21st International Symposium on Fundamentals of Computation Theory (FCT 2017), Lecture Notes in Computer Science 10472, Springer, pp. 5668, September 2017. 
A. Atserias, L. Mančinska, D. E. Roberson, R. Šámal, S. Severini, and A. Varvitsiotis. Quantum and nonsignalling graph isomorphisms. Journal of Combinatorial Theory, Series B, 136:289328, 2019. 
A. Atserias and S. Toruńczyk. NonHomogenizable Classes of Finite Structures. Submitted, June 2019. A preliminary version appeared in the Proceedings of 25th EACSL Annual Conference on Computer Science Logic (CSL 2016), LIPIcs series, pp. 16:116:16, February 2016. 
A. Atserias. A Note on SemiAlgebraic Proofs and Gaussian Elimination over Prime Fields. Technical report, arxiv.org/abs/1502.03974, February 2015. 
A. Atserias, J. L. Balcázar, and Marie Ely Piceno. Relative Entailment Among Probabilistic Implications. Logical Methods in Computer Science, Volume 15, Issue 1, February 2019. A preliminary version appeared in the Proceedings of 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2015), IEEE Press, pages 621632, 2015. 
A. Atserias, M. Lauria, and J. Nordström. Narrow Proofs May Be Maximally Long, ACM Transactions on Computational Logic 17(3), pages 19:119:30, 2016. A preliminary version appeared in the Proceedings of 29th Annual IEEE Conference on Computational Complexity (CCC 2014), IEEE Press, pages 286297, 2014. 
A. Atserias and N. Thapen. The Ordering Principle in a Fragment of Approximate Counting. ACM Transactions on Computational Logic 15(4), pages 29:129:11, 2014. 
A. Atserias. The ProofSearch Problem between BoundedWidth Resolution and BoundedDegree SemiAlgebraic Proofs. In the Proceedings of 16th International Conference on Theory and Applications of Satisfiability Testing (SAT 2013), Lecture Notes in Computer Science vol. 7962, SpringerVerlag, pages 117, 2013. 
A. Atserias, M. Müller, and S. Oliva. Lower Bounds for DNFRefutations of a Relativized Weak Pigeonhole Principle. The Journal of Symbolic Logic, 80(2), pages 450476, 2015. A preliminary version appeared in the Proceedings of 28th Annual IEEE Conference on Computational Complexity (CCC 2013), IEEE Press, pages 109120, 2013. 
A. Atserias and S. Oliva. BoundedWidth QBF is PSPACEcomplete. Journal of Computer and System Sciences 80(7), pages 14151429, 2014. A preliminary version appeared in the Proceedings of 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013), LIPIcs series vol. 20, pp. 4454, 2013. 
A. Atserias and M. Müller Partially definable forcing and bounded arithmetic. Archive for Mathematical Logic 54(12), pages 133, 2015. 
A. Atserias and A. Dawar. Degree Lower Bounds of TowerType for Approximating Formulas with Parity Quantifiers. ACM Transactions on Computational Logic 15(1), pages 6:16:24, 2014. A preliminary version appeared in the Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP 2012), Part II, volume 7392 of Lecture Notes in Computer Science, SpringerVerlag, pages 6778, 2012. 
A. Atserias and E. Maneva. SheraliAdams Relaxations and Indistinguishability in Counting Logics, SIAM Journal on Computing, 42(1), pages 112137, 2013. A preliminary version appeared in the Proceedings of 3rd ACMSIGACT Innovations in Theoretical Computer Science (ITCS 2012), ACM, pages 367379, 2012. 
A. Atserias, J. K. Fichte, and M. Thurley. ClauseLearning Algorithms with Many Restarts and BoundedWidth Resolution, Journal of Artificial Intelligence Research, 40, pages 353373, 2011. A preliminary version appeared in the Proceedings of 12th International Conference on Theory and Applications of Satisfiability Testing (SAT 2009), volume 5584 of Lecture Notes in Computer Science, SpringerVerlag, pages 114127, 2009. 
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), pages 462464. 2011. 
A. Atserias and E. Maneva. Meanpayoff games and propositional proofs, Information and Computation, 209(4), pages 664691, 2011. A preliminary version appeared in the Proceedings of 37th International Colloquium on Automata, Languages and Programming (ICALP 2010), volume 6198 of Lecture Notes in Computer Science, SpringerVerlag, pages 102113, 2010. 
A. Atserias and E. Maneva. MeanPayoff Games and the MaxAtom Problem, technical report, 2009. 
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 2009), volume 5771 of Lecture Notes in Computer Science, SpringerVerlag, pages 102116, 2009. 
A. Atserias, M. Grohe, and D. Marx. Size bounds and query plans for relational joins, SIAM Journal on Computing, 42(4), pages 17371767, 2013. A preliminary version appeared in the Proceedings of 49th IEEE Symposium on Foundations of Computer Science (FOCS 2008), pages 739748, 2008. 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. SpringerVerlag, 2007. Computer Science Review 2(1), pages 5559, 2008. pdf. 
A. Atserias, A. Bulatov, and A. Dawar. Affine Systems of Equations and Counting Infinitary Logic, Theoretical Computer Science, 410(18), pages 16661683, 2009. A preliminary version appeared in the Proceedings of 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), volume 4596 of Lecture Notes in Computer Science, SpringerVerlag, pages 558570, 2007. pdf. 
A. Atserias, A. Bulatov, and V. Dalmau. On the Power of kConsistency, in Proceedings of 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), volume 4596 of Lecture Notes in Computer Science, SpringerVerlag, pages 279290, 2007. pdf. 
A. Atserias. Distinguishing SAT from PolynomialSize Circuits, through BlackBox Queries, in Procceedings of 21st Annual IEEE Conference on Computational Complexity (CCC 2006), IEEE Press, pages 8895, 2006. pdf. 
A. Atserias, A. Dawar, and M. Grohe. Preservation under Extensions on WellBehaved Finite Structures, SIAM Journal on Computing, 38(4), pages 1834, 2008. A preliminary version appeared in the Proceedings of 32nd International Colloquium on Automata, Languages and Programming (ICALP 2005), volume 3580 of Lecture Notes in Computer Science, SpringerVerlag, pages 14371449, 2005. pdf. 
A. Atserias. On Digraph Coloring Problems and Treewidth Duality, European Journal of Combinatorics, 29(4), pages 796820, 2008. A preliminary version appeared in the Proceedings of 20th IEEE Symposium on Logic in Computer Science (LICS 2005), IEEE Press, pages 106115, 2005. pdf. 
A. Atserias. Definability on a Random 3CNF Formula, in Proceedings of 20th IEEE Symposium on Logic in Computer Science (LICS 2005), IEEE Press, pages 458466, 2005. pdf. 
A. Atserias. Conjunctive Query Evaluation by SearchTree Revisited, Theoretical Computer Science, 371, pages 155168, 2007. A preliminary version appeared in the Proceedings of 10th International Conference on Database Theory (ICDT 2005), volume 3363 of Lecture Notes in Computer Science, SpringerVerlag, pages 5367, 2005. 
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, 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 2004), volume 3258 of Lecture Notes in Computer Science, SpringerVerlag, pages 7791, 2004. 
A. Atserias, A. Dawar, and Ph. G. Kolaitis. On Preservation under Homomorphisms and Unions of Conjunctive Queries, Journal of the ACM, 53(2), pages 208237, 2006. A preliminary version appeared in the Proceedings of 23rd ACM SIGMODSIGACTSIGART Symposium on Principles of Database Systems (PODS 2004), ACM, pages 319329, 2004. pdf. 
A. Atserias. Notions of AverageCase Complexity for Random 3SAT (Invited Talk), in the Proceedings of 13th Annual Conference of the EACSL (CSL 2004), volume 3210 of Lecture Notes in Computer Science, SpringerVerlag, pages 15, 2004. 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 717, 2003. Invited Talk at Sisena Trobada Matemàtica de la Societat Catalana de Matemàtiques, 2003. 
A. Atserias and V. Dalmau. A Combinatorial Characterization of Resolution Width, Journal of Computer and System Sciences, 74(3), pages 323334, 2008. A preliminary version appeared in the Proceedings of 18th IEEE Conference on Computational Complexity (CCC 2003), IEEE Press, pages 239247, 2003. pdf. 
A. Atserias and M. L. Bonet. On the Automatizability of Resolution and Related Propositional Proof Systems, Information and Computation, 189(2), pages 182201, 2004. A preliminary version appeared in the Proceedings of 11th Annual Conference of the EACSL (CSL 2002), volume 2471 of Lecture Notes in Computer Science, SpringerVerlag, pages 569583, 2002. pdf. 
A. Atserias. On Sufficient Conditions for Unsatisfiability of Random Formulas, Journal of the ACM, 51(2), pages 281311, 2004. A preliminary version appeared in the Proceedings of 17th IEEE Symposium on Logic in Computer Science (LICS 2002), pages 325334, 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(13), pages 2739, 2003. A preliminary version appeared in the Proceedings of 26th International Symposium on Mathematical Foundations of Computer Science (MFCS 2001), volume 2136 of Lecture Notes in Computer Science, SpringerVerlag, pages 148158, 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 136152, 2002. A preliminary version appeared in the Proceedings of 28th International Colloquium on Automata Languages and Programming (ICALP 2001), volume 2076 of Lecture Notes in Computer Science, SpringerVerlag, pages 10051016, 2001. pdf. 
A. Atserias, N. Galesi, and P. Pudlák. Monotone Simulations of Nonmonotone Proofs, Journal of Computer and System Sciences 65, pages 626638, 2002. A preliminary version appeared in the Proceedings of 16th IEEE Conference on Computational Complexity (CCC 2001), IEEE Press, pages 3641, 2001. pdf. 
A. Atserias. The Descriptive Complexity of the FixedPoints of Bounded Formulas, in the Proceedings of 9th Annual Conference of the EACSL (CSL 2000), volume 1862 of Lecture Notes in Computer Science, SpringerVerlag, pages 172186, 2000. pdf. 
A. Atserias, N. Galesi, and R. Gavaldà. Monotone Proofs of the Pigeon Hole Principle, Mathematical Logic Quarterly 47(4), pages 461474, 2001. A preliminary version appeared in the Proceedings of 27th International Colloquium on Automata, Languages and Programming (ICALP 2000), volume 1853 of Lecture Notes in Computer Science, SpringerVerlag, pages 151162, 2000. pdf. 
A. Atserias and Ph. G. Kolaitis. Firstorder logic vs. fixedpoint logic on finite set theory., in Proceedings of 14th IEEE Symposium on Logic in Computer Science (LICS 1999), IEEE Press, pages 275284, 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 157168, 1997. pdf. 
A. Atserias. Message complexity lower bounds for decentralized anonymous wave algorithms, Report LSI965T, 1996. 
Theses 
A. Atserias. FixedPoint Logics, Descriptive Complexity, and Random
Satisfiability. PhD Thesis, Department of Computer Science and Engineering, University of California, Santa Cruz, December 2002. 
A. Atserias. The Complexity of ResourceBounded Propositional
Proofs. PhD Thesis, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, February 2002. 
Back to Albert Atserias' homepage. 