Albert Atserias

According to our database, Albert Atserias authored at least 76 papers between 1999 and 2025.

Collaborative distances:

• Dijkstra number of four.
• Erdős number of three.

2025

Gamma Acyclicity, Annotated Relations, and Consistency Witness Functions.

Albert Atserias, Phokion G. Kolaitis

CoRR, September, 2025

Consistency Witnesses for Annotated Relations.

Albert Atserias, Phokion G. Kolaitis

SIGMOD Rec., June, 2025

Consistency of Relations over Monoids.

Albert Atserias, Phokion G. Kolaitis

J. ACM, June, 2025

The Proof Analysis Problem.

Noel Arteche, Albert Atserias, Susanna F. de Rezende, Erfan Khaniki

CoRR, June, 2025

Simple general magnification of circuit lower bounds.

Albert Atserias, Moritz Müller

CoRR, March, 2025

Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets.

Albert Atserias, Iddo Tzameret

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

Proof Complexity and Its Relations to SAT Solving (Invited Talk).

Albert Atserias

Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, 2025

Local-vs-Global Consistency of Annotated Relations.

Albert Atserias

Proceedings of the Companion of the 44th Symposium on Principles of Database Systems, 2025

2023

Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem.

Albert Atserias, Joanna Fijalkow

SIAM J. Comput., October, 2023

Circular (Yet Sound) Proofs in Propositional Logic.

Albert Atserias, Massimo Lauria

ACM Trans. Comput. Log., 2023

On the Consistency of Circuit Lower Bounds for Non-deterministic Time.

Albert Atserias, Sam Buss, Moritz Müller

Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023

2022

Finite and Algorithmic Model Theory (Dagstuhl Seminar 22051).

Albert Atserias, Christoph Berkholz, Kousha Etessami, Joanna Ochremiak

Dagstuhl Reports, 2022

Promise Constraint Satisfaction and Width.

Albert Atserias, Víctor Dalmau

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

Towards a Theory of Algorithmic Proof Complexity (Invited Talk).

Albert Atserias

Proceedings of the 49th International Colloquium on Automata, Languages, and Programming, 2022

2021

Structure and Complexity of Bag Consistency.

Albert Atserias, Phokion G. Kolaitis

Proceedings of the PODS'21: Proceedings of the 40th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, 2021

On the Expressive Power of Homomorphism Counts.

Albert Atserias, Phokion G. Kolaitis, Wei-Lin Wu

Proceedings of the 36th Annual ACM/IEEE Symposium on Logic in Computer Science, 2021

2020

Consistency, Acyclicity, and Positive Semirings.

Albert Atserias, Phokion G. Kolaitis

CoRR, 2020

Proofs of Soundness and Proof Search (Invited Talk).

Albert Atserias

Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2020

2019

Relative Entailment Among Probabilistic Implications.

Albert Atserias, José L. Balcázar, Marie Ely Piceno

Log. Methods Comput. 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

Circular (Yet Sound) Proofs.

Albert Atserias, Massimo Lauria

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2019, 2019

On the Power of Symmetric Linear Programs.

Albert Atserias, Anuj Dawar, Joanna Ochremiak

Proceedings of the 34th Annual ACM/IEEE Symposium on Logic in Computer Science, 2019

Automating Resolution is NP-Hard.

Albert Atserias, Moritz Müller

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs.

Albert Atserias, Tuomas Hakoniemi

Proceedings of the 34th Computational Complexity Conference, 2019

2018

Proof Complexity (Dagstuhl Seminar 18051).

Albert Atserias, Jakob Nordström, Pavel Pudlák, Rahul Santhanam

Dagstuhl Reports, 2018

Clique is hard on average for regular resolution.

Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem.

Albert Atserias, Joanna Ochremiak

Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science, 2018

On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface.

Albert Atserias, Stephan Kreutzer, Marc Noy

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

Definable Inapproximability: New Challenges for Duplicator.

Albert Atserias, Anuj Dawar

Proceedings of the 27th EACSL Annual Conference on Computer Science Logic, 2018

2017

Proof Complexity Meets Algebra.

Albert Atserias, Joanna Ochremiak

Proceedings of the 44th International Colloquium on Automata, Languages, and Programming, 2017

Generalized Satisfiability Problems via Operator Assignments.

Albert Atserias, Phokion G. Kolaitis, Simone Severini

Proceedings of the Fundamentals of Computation Theory - 21st International Symposium, 2017

2016

Non-Homogenizable Classes of Finite Structures.

Albert Atserias, Szymon Torunczyk

Proceedings of the 25th EACSL Annual Conference on Computer Science Logic, 2016

2015

A Note on Semi-Algebraic Proofs and Gaussian Elimination over Prime Fields.

Albert Atserias

CoRR, 2015

Partially definable forcing and bounded arithmetic.

Albert Atserias, Moritz Müller

Arch. Math. Log., 2015

Entailment among Probabilistic Implications.

Albert Atserias, José L. Balcázar

Proceedings of the 30th Annual ACM/IEEE Symposium on Logic in Computer Science, 2015

2014

Narrow Proofs May Be Maximally Long.

Albert Atserias, Massimo Lauria, Jakob Nordström

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

2013

The Ordering Principle in a Fragment of Approximate Counting.

Albert Atserias, Neil Thapen

Electron. Colloquium Comput. Complex., 2013

Bounded-width QBF is PSPACE-complete.

Albert Atserias, Sergi Oliva

Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

The Proof-Search Problem between Bounded-Width Resolution and Bounded-Degree Semi-algebraic Proofs.

Albert Atserias

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2013, 2013

Lower Bounds for DNF-refutations of a Relativized Weak Pigeonhole Principle.

Albert Atserias, Moritz Müller, Sergi Oliva

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

Sherali-Adams relaxations and indistinguishability in counting logics.

Albert Atserias, Elitza N. Maneva

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers.

Albert Atserias, Anuj Dawar

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Foreword.

Albert Atserias, Mikolaj Bojanczyk, Balder ten Cate, Ronald Fagin, Floris Geerts, Kenneth A. Ross

Theory Comput. Syst., 2011

Graph Isomorphism, Sherali-Adams Relaxations and Expressibility in Counting Logics.

Albert Atserias, Elitza N. Maneva

Electron. Colloquium Comput. Complex., 2011

A Why-on-Earth Tutorial on Finite Model Theory.

Albert Atserias

Proceedings of the 26th Annual IEEE Symposium on Logic in Computer Science, 2011

2010

Mean-Payoff Games and Propositional Proofs.

Albert Atserias, Elitza N. Maneva

Proceedings of the Automata, Languages and Programming, 37th International Colloquium, 2010

2009

Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution.

Albert Atserias, Johannes Klaus Fichte, Marc Thurley

Proceedings of the Theory and Applications of Satisfiability Testing, 2009

Four Subareas of the Theory of Constraints, and Their Links.

Albert Atserias

Proceedings of the Mathematical Foundations of Computer Science 2009, 2009

Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems.

Albert Atserias, Mark Weyer

Proceedings of the Computer Science Logic, 23rd international Workshop, 2009

2008

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

Size Bounds and Query Plans for Relational Joins.

Albert Atserias, Martin Grohe, Dániel Marx

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

2007

Affine Systems of Equations and Counting Infinitary Logic.

Albert Atserias, Andrei A. Bulatov, Anuj Dawar

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

On the Power of <i>k</i> -Consistency.

Albert Atserias, Andrei A. Bulatov, Víctor Dalmau

Proceedings of the Automata, Languages and Programming, 34th International Colloquium, 2007

2006

Distinguishing SAT from Polynomial-Size Circuits, through Black-Box Queries.

Albert Atserias

Proceedings of the 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 2006

2005

Non-Uniform Hardness for NP via Black-Box Adversaries

Albert Atserias

Electron. Colloquium Comput. Complex., 2005

Definability on a Random 3-CNF Formula.

Albert Atserias

Proceedings of the 20th IEEE Symposium on Logic in Computer Science (LICS 2005), 2005

On Digraph Coloring Problems and Treewidth Duality.

Albert Atserias

Proceedings of the 20th IEEE Symposium on Logic in Computer Science (LICS 2005), 2005

Conjunctive Query Evaluation by Search Tree Revisited.

Albert Atserias

Proceedings of the Database Theory, 2005

Preservation Under Extensions on Well-Behaved Finite Structures.

Albert Atserias, Anuj Dawar, Martin Grohe

Proceedings of the Automata, Languages and Programming, 32nd International Colloquium, 2005

2004

On sufficient conditions for unsatisfiability of random formulas.

Albert Atserias

J. ACM, 2004

On Preservation under Homomorphisms and Unions of Conjunctive Queries.

Albert Atserias, Anuj Dawar, Phokion G. Kolaitis

Proceedings of the Twenty-third ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 2004

Notions of Average-Case Complexity for Random 3-SAT.

Albert Atserias

Proceedings of the Computer Science Logic, 18th International Workshop, 2004

Constraint Propagation as a Proof System.

Albert Atserias, Phokion G. Kolaitis, Moshe Y. Vardi

Proceedings of the Principles and Practice of Constraint Programming, 2004

2003

On Chvatal Rank and Cutting Planes Proofs

Albert Atserias, Maria Luisa Bonet, Jordi Levy

Electron. Colloquium Comput. Complex., 2003

A Combinatorial Characterization of Resolution Width.

Albert Atserias, Víctor Dalmau

Proceedings of the 18th Annual IEEE Conference on Computational Complexity (Complexity 2003), 2003

2002

Monotone simulations of non-monotone proofs.

Albert Atserias, Nicola Galesi, Pavel Pudlák

J. Comput. Syst. Sci., 2002

Lower Bounds for the Weak Pigeonhole Principle and Random Formulas beyond Resolution.

Albert Atserias, Maria Luisa Bonet, Juan Luis Esteban

Inf. Comput., 2002

Unsatisfiable Random Formulas Are Hard to Certify.

Albert Atserias

Proceedings of the 17th IEEE Symposium on Logic in Computer Science (LICS 2002), 2002

On the Automatizability of Resolution and Related Propositional Proof Systems.

Albert Atserias, Maria Luisa Bonet

Proceedings of the Computer Science Logic, 16th International Workshop, 2002

2001

Improved Bounds on the Weak Pigeonhole Principle and Infinitely Many Primes from Weaker Axioms.

Albert Atserias

Proceedings of the Mathematical Foundations of Computer Science 2001, 2001

Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution.

Albert Atserias, Maria Luisa Bonet, Juan Luis Esteban

Proceedings of the Automata, Languages and Programming, 28th International Colloquium, 2001

Monotone Simulations of Nonmonotone Proofs.

Albert Atserias, Nicola Galesi, Pavel Pudlák

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

2000

Monotone simulations of nonmonotone propositional proofs

Albert Atserias, Nicola Galesi, Pavel Pudlák

Electron. Colloquium Comput. Complex., 2000

Monotone Proofs of the Pigeon Hole Principle.

Albert Atserias, Nicola Galesi, Ricard Gavaldà

Proceedings of the Automata, Languages and Programming, 27th International Colloquium, 2000

The Descriptive Comlexity of the Fixed-Points of Bounded Formulas.

Albert Atserias

Proceedings of the Computer Science Logic, 2000

1999

First-Order Logic vs. Fixed-Point Logic in Finite Set Theory.

Albert Atserias, Phokion G. Kolaitis

Proceedings of the 14th Annual IEEE Symposium on Logic in Computer Science, 1999