Publications | Homepage of Albert Atserias |
Articles |
A. Atserias, S. Buss, and M. Müller. On the Consistency of Circuit Lower Bounds for Non-Deterministic Time. Submitted for journal publication. A prelimary version appeared in the Proceedings of the 55th ACM Symposium on the Theory of Computation (STOC 2023), Orlando, FL, USA, 2023. Also arXiv:2303.01016 [cs.CC], March 3, 2023. |
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:1--1:2, June 29, 2022. |
A. Atserias and V. Dalmau Promise Constraint Satisfaction and Width. In the Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA 2022). Also arXiv:2107.05886 [cs.CC], July 13, 2021. |
A. Atserias, Ph. G. Kolaitis, and Wei-Lin 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, January-June, 2021. |
A. Atserias and Ph. G. Kolaitis. Structure and Complexity of Bag Consistency. In the Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI 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. In Samson Abramsky on Logic and Structure in Computer Science and Beyond. Alessandra Palmigiano & Mehrnoosh Sadrzadeh (eds.), Springer Verlag. pp. 623-668, 2023. A preliminary version appeared in arxiv:2009.09488 [cs.DB], September 20, 2020. |
A. Atserias and M. Müller. Automating Resolution is NP-Hard. 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. Journal of the ACM, 68(4), Article No.: 26, pp 1--35. A preliminary version appeared in the Proceedings of 34th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2019), IEEE, pp. 1-13, Vancouver, Canada, July 2019. |
A. Atserias and T. Hakoniemi. Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs. In the Proceedings of Computational Complexity Conference (CCC 2019), LIPIcs series, vol. 137, pp. 24:1--24: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. 1185-1210, 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 Zero-One 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:1-116:14, July 2018. |
A. Atserias and M. Lauria. Circular (Yet Sound) Proofs. ACM Transactions on Computational Logic, Volume 24, Issue 3, Article No.: 20, pp. 1–26, 2023. 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. 1-18, 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. Journal of the ACM, Volume 68, Issue 4, Article No.: 23, pp. 1–26, 2021. A preliminary version appeared in the Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (STOC 2018), pp. 866-877, June 2018. |
A. Atserias and J. Ochremiak. Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem. SIAM Journal on Computing 52(5), pp. 1193-1229, 2023. A preliminary version appeared in the Proceedings of 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS 2018), pp. 66--75, 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. 20-1, 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:1-110:14, July 2017. |
A. Atserias, Ph. G. Kolaitis, and S. Severini. Generalized Satisfiability Problems via Operator Assignments. Journal of Computer and Systems Sciences, 105:171-198, 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. 56-68, September 2017. |
A. Atserias, L. Mančinska, D. E. Roberson, R. Šámal, S. Severini, and A. Varvitsiotis. Quantum and non-signalling graph isomorphisms. Journal of Combinatorial Theory, Series B, 136:289-328, 2019. |
A. Atserias and S. Toruńczyk. Non-Homogenizable 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:1-16:16, February 2016. |
A. Atserias. A Note on Semi-Algebraic 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 621-632, 2015. |
A. Atserias, M. Lauria, and J. Nordström. Narrow Proofs May Be Maximally Long, ACM Transactions on Computational Logic 17(3), pages 19:1-19:30, 2016. A preliminary version appeared in the Proceedings of 29th Annual IEEE Conference on Computational Complexity (CCC 2014), IEEE Press, pages 286-297, 2014. |
A. Atserias and N. Thapen. The Ordering Principle in a Fragment of Approximate Counting. ACM Transactions on Computational Logic 15(4), pages 29:1-29:11, 2014. |
A. Atserias. The Proof-Search Problem between Bounded-Width Resolution and Bounded-Degree Semi-Algebraic Proofs. In the Proceedings of 16th International Conference on Theory and Applications of Satisfiability Testing (SAT 2013), Lecture Notes in Computer Science vol. 7962, Springer-Verlag, pages 1-17, 2013. |
A. Atserias, M. Müller, and S. Oliva. Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle. The Journal of Symbolic Logic, 80(2), pages 450-476, 2015. A preliminary version appeared in the Proceedings of 28th Annual IEEE Conference on Computational Complexity (CCC 2013), IEEE Press, pages 109-120, 2013. |
A. Atserias and S. Oliva. Bounded-Width QBF is PSPACE-complete. Journal of Computer and System Sciences 80(7), pages 1415-1429, 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. 44-54, 2013. |
A. Atserias and M. Müller Partially definable forcing and bounded arithmetic. Archive for Mathematical Logic 54(1-2), pages 1-33, 2015. |
A. Atserias and A. Dawar. Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers. ACM Transactions on Computational Logic 15(1), pages 6:1-6: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, Springer-Verlag, pages 67--78, 2012. |
A. Atserias and E. Maneva. Sherali-Adams Relaxations and Indistinguishability in Counting Logics, SIAM Journal on Computing, 42(1), pages 112-137, 2013. A preliminary version appeared in the Proceedings of 3rd ACM-SIGACT Innovations in Theoretical Computer Science (ITCS 2012), ACM, pages 367-379, 2012. |
A. Atserias, J. K. Fichte, and M. Thurley. Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution, Journal of Artificial Intelligence Research, 40, pages 353-373, 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, Springer-Verlag, pages 114--127, 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 462-464. 2011. |
A. Atserias and E. Maneva. Mean-payoff games and propositional proofs, Information and Computation, 209(4), pages 664-691, 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, Springer-Verlag, pages 102-113, 2010. |
A. Atserias and E. Maneva. Mean-Payoff Games and the Max-Atom 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, Springer-Verlag, pages 102-116, 2009. |
A. Atserias, M. Grohe, and D. Marx. Size bounds and query plans for relational joins, SIAM Journal on Computing, 42(4), pages 1737-1767, 2013. A preliminary version appeared in the Proceedings of 49th IEEE Symposium on Foundations of Computer Science (FOCS 2008), pages 739-748, 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. Springer-Verlag, 2007. Computer Science Review 2(1), pages 55-59, 2008. pdf. |
A. Atserias, A. Bulatov, and A. Dawar. Affine Systems of Equations and Counting Infinitary Logic, Theoretical Computer Science, 410(18), pages 1666-1683, 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, Springer-Verlag, pages 558-570, 2007. pdf. |
A. Atserias, A. Bulatov, and V. Dalmau. On the Power of k-Consistency, in Proceedings of 34th International Colloquium on Automata, Languages and Programming (ICALP 2007), volume 4596 of Lecture Notes in Computer Science, Springer-Verlag, pages 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 2006), IEEE Press, pages 88-95, 2006. pdf. |
A. Atserias, A. Dawar, and M. Grohe. Preservation under Extensions on Well-Behaved Finite Structures, SIAM Journal on Computing, 38(4), pages 18-34, 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, 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 2005), IEEE Press, 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 2005), IEEE Press, 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 2005), volume 3363 of Lecture Notes in Computer Science, Springer-Verlag, pages 53-67, 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, Springer-Verlag, pages 77-91, 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 208-237, 2006. A preliminary version appeared in the Proceedings of 23rd ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2004), ACM, pages 319-329, 2004. pdf. |
A. Atserias. Notions of Average-Case Complexity for Random 3-SAT (Invited Talk), in the Proceedings of 13th Annual Conference of the EACSL (CSL 2004), volume 3210 of Lecture Notes in Computer Science, Springer-Verlag, pages 1-5, 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 7-17, 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 323-334, 2008. A preliminary version appeared in the Proceedings of 18th IEEE Conference on Computational Complexity (CCC 2003), IEEE Press, 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 2002), 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 2002), 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 2001), volume 2136 of Lecture Notes in Computer Science, Springer-Verlag, pages 148-158, 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 2001), volume 2076 of Lecture Notes in Computer Science, Springer-Verlag, pages 1005-1016, 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), IEEE Press, pages 36-41, 2001. pdf. |
A. Atserias. The Descriptive Complexity of the Fixed-Points of Bounded Formulas, in the Proceedings of 9th Annual Conference of the EACSL (CSL 2000), volume 1862 of Lecture Notes in Computer Science, Springer-Verlag, pages 172-186, 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 2000), volume 1853 of Lecture Notes in Computer Science, Springer-Verlag, pages 151-162, 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), IEEE Press, pages 275-284, 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. |
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. PhD Thesis, Department of Computer Science and Engineering, University of California, Santa Cruz, December 2002. |
A. Atserias. The Complexity of Resource-Bounded Propositional
Proofs. PhD Thesis, Departament de Llenguatges i Sistemes Informàtics, Universitat Politècnica de Catalunya, February 2002. |
Back to Albert Atserias' homepage. |