Albert Atserias

According to our database, Albert Atserias authored at least 69 papers between 1999 and 2023.

Collaborative distances:

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

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

Consistency of Relations over Monoids.

Albert Atserias, Phokion G. Kolaitis

CoRR, 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

Structure and Complexity of Bag Consistency.

Albert Atserias, Phokion G. Kolaitis

SIGMOD Rec., 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

On the Power of Symmetric Linear Programs.

Albert Atserias, Anuj Dawar, Joanna Ochremiak

J. ACM, 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 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

Automating Resolution is NP-Hard.

Albert Atserias, Moritz Müller

J. ACM, 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

Proof Complexity Meets Algebra.

Albert Atserias, Joanna Ochremiak

ACM Trans. Comput. Log., 2019

Definable inapproximability: new challenges for duplicator.

Albert Atserias, Anuj Dawar

J. Log. Comput., 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, Ser. B, 2019

Generalized satisfiability problems via operator assignments.

Albert Atserias, Phokion G. Kolaitis, Simone Severini

J. Comput. Syst. Sci., 2019

Circular (Yet Sound) Proofs.

Albert Atserias, Massimo Lauria

Proceedings of the Theory and Applications of Satisfiability Testing - SAT 2019, 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

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

2016

Narrow Proofs May Be Maximally Long.

Albert Atserias, Massimo Lauria, Jakob Nordström

ACM Trans. Comput. Log., 2016

Non-Homogenizable Classes of Finite Structures.

Albert Atserias, Szymon Torunczyk

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

2015

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

Albert Atserias, Moritz Müller, Sergi Oliva

J. Symb. Log., 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

The Ordering Principle in a Fragment of Approximate Counting.

Albert Atserias, Neil Thapen

ACM Trans. Comput. Log., 2014

Degree lower bounds of tower-type for approximating formulas with parity quantifiers.

Albert Atserias, Anuj Dawar

ACM Trans. Comput. Log., 2014

Bounded-width QBF is PSPACE-complete.

Albert Atserias, Sergi Oliva

J. Comput. Syst. Sci., 2014

2013

Sherali-Adams Relaxations and Indistinguishability in Counting Logics.

Albert Atserias, Elitza N. Maneva

SIAM J. Comput., 2013

Size Bounds and Query Plans for Relational Joins.

Albert Atserias, Martin Grohe, Dániel Marx

SIAM J. Comput., 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

2011

Foreword.

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

Theory Comput. Syst., 2011

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

Albert Atserias, Johannes Klaus Fichte, Marc Thurley

J. Artif. Intell. Res., 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

Electron. Colloquium Comput. Complex., 2010

2009

Affine systems of equations and counting infinitary logic.

Albert Atserias, Andrei A. Bulatov, Anuj Dawar

Theor. Comput. Sci., 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

Preservation under Extensions on Well-Behaved Finite Structures.

Albert Atserias, Anuj Dawar, Martin Grohe

SIAM J. Comput., 2008

A combinatorial characterization of resolution width.

Albert Atserias, Víctor Dalmau

J. Comput. Syst. Sci., 2008

On digraph coloring problems and treewidth duality.

Albert Atserias

Eur. J. Comb., 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

2007

Conjunctive query evaluation by search-tree revisited.

Albert Atserias

Theor. Comput. Sci., 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

On preservation under homomorphisms and unions of conjunctive queries.

Albert Atserias, Anuj Dawar, Phokion G. Kolaitis

J. ACM, 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

2004

On sufficient conditions for unsatisfiability of random formulas.

Albert Atserias

J. ACM, 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

Improved bounds on the Weak Pigeonhole Principle and infinitely many primes from weaker axioms.

Albert Atserias

Theor. Comput. Sci., 2003

On Chvatal Rank and Cutting Planes Proofs

Albert Atserias, Maria Luisa Bonet, Jordi Levy

Electron. Colloquium Comput. Complex., 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

On the Automatizability of Resolution and Related Propositional Proof Systems

Albert Atserias, Maria Luisa Bonet

Electron. Colloquium Comput. Complex., 2002

Unsatisfiable Random Formulas Are Hard to Certify.

Albert Atserias

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

2001

Monotone Proofs of the Pigeon Hole Principle.

Albert Atserias, Nicola Galesi, Ricard Gavaldà

Math. Log. Q., 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

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