A. Atserias and J. Ochremiak.
Proof Complexity Meets Algebra,
in the Proceedings of 44th Annual Colloquium on Automata, Languages and Programming (ICALP), LIPIcs 110:1-110:14, July 2017.
pdf
A. Atserias, Ph. G. Kolaitis and S. Severini.
Generalized Satisfiability Problems via Operator Assignments,
arXiv:1704.01736 [cs.LO], May 2017.
A preliminary version to appear in the Proceedings of 21st International Symposium on Fundamentals of Computation Theory (FCT), September 2017.
pdf
Albert Atserias, Laura Mančinska, David E. Roberson, Robert Šámal, Simone Severini, and Antonios Varvitsiotis.
Quantum and non-signalling graph isomorphisms,
submitted, arXiv:1611.09837 [quant-ph], May 2017.
pdf
A. Atserias and S. Toruńczyk.
Non-Homogenizable Classes of Finite Structures,
in the Proceedings of 25th EACSL Annual Conference on Computer Science Logic (CSL), LIPIcs 16:1-16:16, February 2016.
pdf
A. Atserias.
A Note on Semi-Algebraic Proofs and Gaussian Elimination over Prime Fields,
technical report, arxiv.org/abs/1502.03974, February 2015.
pdf
A. Atserias and J. L. Balcázar.
Entailment Among Probabilistic Implications,
in the Proceedings of 30th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), IEEE Press, pages 621-632, 2015.
pdf
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), IEEE Press, pages 286-297, 2014.
pdf
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.
pdf
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), Lecture Notes in Computer Science vol. 7962, Springer-Verlag, pages 1-17, 2013.
pdf
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), IEEE Press, pages 109-120, 2013.
pdf
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), LIPIcs series vol. 20, Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, pages 44-54, 2013.
pdf
A. Atserias and M. Müller
Partially definable forcing and bounded arithmetic,
Archive for Mathematical Logic 54(1-2), pages 1-33, 2015.
pdf
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), Part II, volume 7392 of Lecture Notes in Computer Science, Springer-Verlag, pages 67--78, 2012.
pdf
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), ACM, pages 367-379, 2012.
pdf
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), volume 5584 of Lecture Notes in Computer Science, Springer-Verlag, pages 114--127, 2009.
pdf
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.
pdf
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), volume 6198 of Lecture Notes in Computer Science, Springer-Verlag, pages 102-113, 2010.
pdf
A. Atserias and E. Maneva.
Mean-Payoff Games and the Max-Atom Problem,
technical report, 2009.
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, pages 102-116, 2009.
pdf
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), 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, 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), volume 4596 of Lecture Notes in Computer Science, Springer-Verlag, pages 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, 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), 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), 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), 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), 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), volume 3363 of Lecture Notes in Computer Science, Springer-Verlag, pages 53-67, 2005.
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, 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, Springer-Verlag, pages 77-91, 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), ACM, pages 319-329, 2004.
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, Springer-Verlag, pages 1-5, 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 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), 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), 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, 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), 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), IEEE Press, pages 36-41, 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, 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), 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), 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.

Back to Albert Atserias' homepage.