Albert Atserias

ORCID

Publication Activity (10 Years)

Years Active: 1999-2024
Publications (10 Years): 49

Top Venues

CoRR

ACM Trans. Comput. Log.

LICS

ICALP

Publications

Albert Atserias, Phokion G. Kolaitis
Consistency of Relations over Monoids. Proc. ACM Manag. Data 2 (2) (2024)
Albert Atserias, Joanna Fijalkow
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem. SIAM J. Comput. 52 (5) (2023)
Albert Atserias, Massimo Lauria
Circular (Yet Sound) Proofs in Propositional Logic. ACM Trans. Comput. Log. 24 (3) (2023)
Albert Atserias, Sam Buss, Moritz Müller
On the Consistency of Circuit Lower Bounds for Non-Deterministic Time. CoRR (2023)
Albert Atserias, Phokion G. Kolaitis
Consistency of Relations over Monoids. CoRR (2023)
Albert Atserias, Sam Buss, Moritz Müller
On the Consistency of Circuit Lower Bounds for Non-deterministic Time. STOC (2023)
Albert Atserias
Towards a Theory of Algorithmic Proof Complexity (Invited Talk). ICALP (2022)
Albert Atserias, Víctor Dalmau
Promise Constraint Satisfaction and Width. SODA (2022)
Albert Atserias, Phokion G. Kolaitis
Structure and Complexity of Bag Consistency. SIGMOD Rec. 51 (1) (2022)
Albert Atserias, Christoph Berkholz, Kousha Etessami, Joanna Ochremiak
Finite and Algorithmic Model Theory (Dagstuhl Seminar 22051). Dagstuhl Reports 12 (1) (2022)
Albert Atserias, Phokion G. Kolaitis, Wei-Lin Wu
On the Expressive Power of Homomorphism Counts. CoRR (2021)
Albert Atserias, Anuj Dawar, Joanna Ochremiak
On the Power of Symmetric Linear Programs. J. ACM 68 (4) (2021)
Albert Atserias, Phokion G. Kolaitis, Wei-Lin Wu
On the Expressive Power of Homomorphism Counts. LICS (2021)
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov
Clique Is Hard on Average for Regular Resolution. J. ACM 68 (4) (2021)
Albert Atserias, Phokion G. Kolaitis
Structure and Complexity of Bag Consistency. PODS (2021)
Albert Atserias, Víctor Dalmau
Promise Constraint Satisfaction and Width. CoRR (2021)
Albert Atserias, Phokion G. Kolaitis
Structure and Complexity of Bag Consistency. CoRR (2020)
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov
Clique Is Hard on Average for Regular Resolution. CoRR (2020)
Albert Atserias
Proofs of Soundness and Proof Search (Invited Talk). FSTTCS (2020)
Albert Atserias, Moritz Müller
Automating Resolution is NP-Hard. J. ACM 67 (5) (2020)
Albert Atserias, Phokion G. Kolaitis
Consistency, Acyclicity, and Positive Semirings. CoRR (2020)
Albert Atserias, Phokion G. Kolaitis, Simone Severini
Generalized satisfiability problems via operator assignments. J. Comput. Syst. Sci. 105 (2019)
Albert Atserias, Anuj Dawar
Definable inapproximability: new challenges for duplicator. J. Log. Comput. 29 (8) (2019)
Albert Atserias, José L. Balcázar, Marie Ely Piceno
Relative Entailment Among Probabilistic Implications. Log. Methods Comput. Sci. 15 (1) (2019)
Albert Atserias, Moritz Müller
Automating Resolution is NP-Hard. FOCS (2019)
Albert Atserias, Joanna Ochremiak
Proof Complexity Meets Algebra. ACM Trans. Comput. Log. 20 (1) (2019)
Albert Atserias, Tuomas Hakoniemi
Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs. Computational Complexity Conference (2019)
Albert Atserias, Massimo Lauria
Circular (Yet Sound) Proofs. SAT (2019)
Albert Atserias, Anuj Dawar, Joanna Ochremiak
On the Power of Symmetric Linear Programs. CoRR (2019)
Albert Atserias, Laura Mancinska, David E. Roberson, Robert Sámal, Simone Severini, Antonios Varvitsiotis
Quantum and non-signalling graph isomorphisms. J. Comb. Theory, Ser. B 136 (2019)
Albert Atserias, Moritz Müller
Automating Resolution is NP-Hard. CoRR (2019)
Albert Atserias, Anuj Dawar, Joanna Ochremiak
On the Power of Symmetric Linear Programs. LICS (2019)
Albert Atserias, Tuomas Hakoniemi
Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs. CoRR (2018)
Albert Atserias, Anuj Dawar
Definable Inapproximability: New Challenges for Duplicator. CSL (2018)
Albert Atserias, Joanna Ochremiak
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem. LICS (2018)
Albert Atserias, Joanna Ochremiak
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem. CoRR (2018)
Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov
Clique is hard on average for regular resolution. STOC (2018)
Albert Atserias, Anuj Dawar
Definable Inapproximability: New Challenges for Duplicator. CoRR (2018)
Albert Atserias, Stephan Kreutzer, Marc Noy
On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface. ICALP (2018)
Albert Atserias, Jakob Nordström, Pavel Pudlák, Rahul Santhanam
Proof Complexity (Dagstuhl Seminar 18051). Dagstuhl Reports 8 (1) (2018)
Albert Atserias, Massimo Lauria
Circular (Yet Sound) Proofs. CoRR (2018)
Albert Atserias, Phokion G. Kolaitis, Simone Severini
Generalized Satisfiability Problems via Operator Assignments. CoRR (2017)
Albert Atserias, Joanna Ochremiak
Proof Complexity Meets Algebra. CoRR (2017)
Albert Atserias, Phokion G. Kolaitis, Simone Severini
Generalized Satisfiability Problems via Operator Assignments. FCT (2017)
Albert Atserias, Joanna Ochremiak
Proof Complexity Meets Algebra. ICALP (2017)
Albert Atserias, Martin Grohe, Dániel Marx
Size bounds and query plans for relational joins. CoRR (2017)
Albert Atserias, Szymon Torunczyk
Non-Homogenizable Classes of Finite Structures. CSL (2016)
Albert Atserias, Szymon Torunczyk
Non-Homogenizable Classes of Finite Structures. CoRR (2016)
Albert Atserias, Massimo Lauria, Jakob Nordström
Narrow Proofs May Be Maximally Long. ACM Trans. Comput. Log. 17 (3) (2016)
Albert Atserias, José L. Balcázar
Entailment among Probabilistic Implications. LICS (2015)
Albert Atserias
A Note on Semi-Algebraic Proofs and Gaussian Elimination over Prime Fields. CoRR (2015)
Albert Atserias, Moritz Müller
Partially definable forcing and bounded arithmetic. Arch. Math. Log. 54 (1-2) (2015)
Albert Atserias, Moritz Müller, Sergi Oliva
Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle. J. Symb. Log. 80 (2) (2015)
Albert Atserias, José L. Balcázar
Entailment among probabilistic implications. CoRR (2015)
Albert Atserias, Anuj Dawar
Degree lower bounds of tower-type for approximating formulas with parity quantifiers. ACM Trans. Comput. Log. 15 (1) (2014)
Albert Atserias, Johannes Klaus Fichte, Marc Thurley
Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution. CoRR (2014)
Albert Atserias, Neil Thapen
The Ordering Principle in a Fragment of Approximate Counting. ACM Trans. Comput. Log. 15 (4) (2014)
Albert Atserias, Massimo Lauria, Jakob Nordström
Narrow Proofs May Be Maximally Long. Computational Complexity Conference (2014)
Albert Atserias, Massimo Lauria, Jakob Nordström
Narrow Proofs May Be Maximally Long. CoRR (2014)
Albert Atserias, Massimo Lauria, Jakob Nordström
Narrow Proofs May Be Maximally Long. Electron. Colloquium Comput. Complex. 21 (2014)
Albert Atserias, Sergi Oliva
Bounded-width QBF is PSPACE-complete. J. Comput. Syst. Sci. 80 (7) (2014)
Albert Atserias, Moritz Müller, Sergi Oliva
Lower Bounds for DNF-refutations of a Relativized Weak Pigeonhole Principle. Computational Complexity Conference (2013)
Albert Atserias, Martin Grohe, Dániel Marx
Size Bounds and Query Plans for Relational Joins. SIAM J. Comput. 42 (4) (2013)
Albert Atserias, Neil Thapen
The Ordering Principle in a Fragment of Approximate Counting. Electron. Colloquium Comput. Complex. 20 (2013)
Albert Atserias, Moritz Müller, Sergi Oliva
Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle. Electron. Colloquium Comput. Complex. 20 (2013)
Albert Atserias
The Proof-Search Problem between Bounded-Width Resolution and Bounded-Degree Semi-algebraic Proofs. SAT (2013)
Albert Atserias, Elitza N. Maneva
Sherali-Adams Relaxations and Indistinguishability in Counting Logics. SIAM J. Comput. 42 (1) (2013)
Albert Atserias, Sergi Oliva
Bounded-width QBF is PSPACE-complete. STACS (2013)
Albert Atserias, Anuj Dawar
Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers. Electron. Colloquium Comput. Complex. 19 (2012)
Albert Atserias, Elitza N. Maneva
Sherali-Adams relaxations and indistinguishability in counting logics. ITCS (2012)
Albert Atserias, Anuj Dawar
Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers. ICALP (2) (2012)
Albert Atserias, Sergi Oliva
Bounded-width QBF is PSPACE-complete. Electron. Colloquium Comput. Complex. 19 (2012)
Albert Atserias, Johannes Klaus Fichte, Marc Thurley
Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution. J. Artif. Intell. Res. 40 (2011)
Albert Atserias, Elitza N. Maneva
Graph Isomorphism, Sherali-Adams Relaxations and Expressibility in Counting Logics. Electron. Colloquium Comput. Complex. 18 (2011)
Albert Atserias, Elitza N. Maneva
Mean-payoff games and propositional proofs. Inf. Comput. 209 (4) (2011)
Albert Atserias, Mikolaj Bojanczyk, Balder ten Cate, Ronald Fagin, Floris Geerts, Kenneth Ross
Foreword. Theory Comput. Syst. 49 (2) (2011)
Albert Atserias
A Why-on-Earth Tutorial on Finite Model Theory. LICS (2011)
Albert Atserias, Elitza N. Maneva
Mean-Payoff Games and Propositional Proofs. ICALP (1) (2010)
Albert Atserias, Elitza N. Maneva
Mean-payoff games and propositional proofs. Electron. Colloquium Comput. Complex. 17 (2010)
Albert Atserias, Johannes Klaus Fichte, Marc Thurley
Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution. SAT (2009)
Albert Atserias
Four Subareas of the Theory of Constraints, and Their Links. MFCS (2009)
Albert Atserias, Mark Weyer
Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems. CSL (2009)
Albert Atserias, Andrei A. Bulatov, Anuj Dawar
Affine systems of equations and counting infinitary logic. Theor. Comput. Sci. 410 (18) (2009)
Albert Atserias
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). Comput. Sci. Rev. 2 (1) (2008)
Albert Atserias
On digraph coloring problems and treewidth duality. Eur. J. Comb. 29 (4) (2008)
Albert Atserias, Anuj Dawar, Martin Grohe
Preservation under Extensions on Well-Behaved Finite Structures. SIAM J. Comput. 38 (4) (2008)
Albert Atserias, Víctor Dalmau
A combinatorial characterization of resolution width. J. Comput. Syst. Sci. 74 (3) (2008)
Albert Atserias, Martin Grohe, Dániel Marx
Size Bounds and Query Plans for Relational Joins. FOCS (2008)
Albert Atserias, Andrei A. Bulatov, Anuj Dawar
Affine Systems of Equations and Counting Infinitary Logic. ICALP (2007)
Albert Atserias, Andrei A. Bulatov, Víctor Dalmau
-Consistency. ICALP (2007)
Albert Atserias
Conjunctive query evaluation by search-tree revisited. Theor. Comput. Sci. 371 (3) (2007)
Albert Atserias
Distinguishing SAT from Polynomial-Size Circuits, through Black-Box Queries. Computational Complexity Conference (2006)
Albert Atserias, Anuj Dawar, Phokion G. Kolaitis
On preservation under homomorphisms and unions of conjunctive queries. J. ACM 53 (2) (2006)
Albert Atserias
Conjunctive Query Evaluation by Search Tree Revisited. ICDT (2005)
Albert Atserias
On Digraph Coloring Problems and Treewidth Duality. LICS (2005)
Albert Atserias, Anuj Dawar, Martin Grohe
Preservation Under Extensions on Well-Behaved Finite Structures. ICALP (2005)
Albert Atserias
Definability on a Random 3-CNF Formula. LICS (2005)
Albert Atserias
Non-Uniform Hardness for NP via Black-Box Adversaries Electron. Colloquium Comput. Complex. (154) (2005)
Albert Atserias, Phokion G. Kolaitis, Moshe Y. Vardi
Constraint Propagation as a Proof System. CP (2004)
Albert Atserias, Anuj Dawar, Phokion G. Kolaitis
On Preservation under Homomorphisms and Unions of Conjunctive Queries. PODS (2004)

Albert Atserias.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Albert Atserias