Albert Atserias

134 papers A* 26A 15B 9Journal 80Unranked 4

Year	Rank	Type	Title / Venue / Authors
2026	A	`conf`	Gamma Acyclicity, Annotated Relations, and Consistency Witness Functions. ICDT Albert Atserias, Phokion G. Kolaitis
2025	J	`jnl`	Consistency Witnesses for Annotated Relations. SIGMOD Rec. Albert Atserias, Phokion G. Kolaitis
2025	J	`jnl`	Consistency of Relations over Monoids. J. ACM Albert Atserias, Phokion G. Kolaitis
2025	A*	`conf`	Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets. STOC Albert Atserias, Iddo Tzameret
2025	J	`jnl`	Gamma Acyclicity, Annotated Relations, and Consistency Witness Functions. CoRR Albert Atserias, Phokion G. Kolaitis
2025	—	`conf`	Local-vs-Global Consistency of Annotated Relations. PODS Companion Albert Atserias
2025	J	`jnl`	On the consistency of circuit lower bounds for non-deterministic time. J. Math. Log. Albert Atserias, Sam Buss, Moritz Müller
2025	A	`conf`	Proof Complexity and Its Relations to SAT Solving (Invited Talk). STACS Albert Atserias
2025	J	`jnl`	Simple general magnification of circuit lower bounds. CoRR Albert Atserias, Moritz Müller
2025	A*	`conf`	The Proof Analysis Problem. FOCS Noel Arteche, Albert Atserias, Susanna F. de Rezende, Erfan Khaniki
2025	J	`jnl`	The Proof Analysis Problem. CoRR Noel Arteche, Albert Atserias, Susanna F. de Rezende, Erfan Khaniki
2024	J	`jnl`	Consistency of Relations over Monoids. Proc. ACM Manag. Data Albert Atserias, Phokion G. Kolaitis
2024	J	`jnl`	Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets. CoRR Albert Atserias, Iddo Tzameret
2024	J	`jnl`	Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets. Electron. Colloquium Comput. Complex. Albert Atserias, Iddo Tzameret
2023	J	`jnl`	Circular (Yet Sound) Proofs in Propositional Logic. ACM Trans. Comput. Log. Albert Atserias, Massimo Lauria
2023	J	`jnl`	Consistency of Relations over Monoids. CoRR Albert Atserias, Phokion G. Kolaitis
2023	J	`jnl`	Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem. SIAM J. Comput. Albert Atserias, Joanna Fijalkow
2023	J	`jnl`	On the Consistency of Circuit Lower Bounds for Non-Deterministic Time. CoRR Albert Atserias, Sam Buss, Moritz Müller
2023	A*	`conf`	On the Consistency of Circuit Lower Bounds for Non-deterministic Time. STOC Albert Atserias, Sam Buss, Moritz Müller
2022	J	`jnl`	Finite and Algorithmic Model Theory (Dagstuhl Seminar 22051). Dagstuhl Reports Albert Atserias, Christoph Berkholz, Kousha Etessami, Joanna Ochremiak
2022	A*	`conf`	Promise Constraint Satisfaction and Width. SODA Albert Atserias, Víctor Dalmau
2022	J	`jnl`	Structure and Complexity of Bag Consistency. SIGMOD Rec. Albert Atserias, Phokion G. Kolaitis
2022	A*	`conf`	Towards a Theory of Algorithmic Proof Complexity (Invited Talk). ICALP Albert Atserias
2021	J	`jnl`	Clique Is Hard on Average for Regular Resolution. J. ACM Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov
2021	A*	`conf`	On the Expressive Power of Homomorphism Counts. LICS Albert Atserias, Phokion G. Kolaitis, Wei-Lin Wu
2021	J	`jnl`	On the Expressive Power of Homomorphism Counts. CoRR Albert Atserias, Phokion G. Kolaitis, Wei-Lin Wu
2021	J	`jnl`	On the Power of Symmetric Linear Programs. J. ACM Albert Atserias, Anuj Dawar, Joanna Ochremiak
2021	J	`jnl`	Promise Constraint Satisfaction and Width. CoRR Albert Atserias, Víctor Dalmau
2021	A*	`conf`	Structure and Complexity of Bag Consistency. PODS Albert Atserias, Phokion G. Kolaitis
2020	J	`jnl`	Automating Resolution is NP-Hard. J. ACM Albert Atserias, Moritz Müller
2020	J	`jnl`	Clique Is Hard on Average for Regular Resolution. CoRR Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov
2020	J	`jnl`	Consistency, Acyclicity, and Positive Semirings. CoRR Albert Atserias, Phokion G. Kolaitis
2020	—	`conf`	Proofs of Soundness and Proof Search (Invited Talk). FSTTCS Albert Atserias
2020	J	`jnl`	Structure and Complexity of Bag Consistency. CoRR Albert Atserias, Phokion G. Kolaitis
2019	A*	`conf`	Automating Resolution is NP-Hard. FOCS Albert Atserias, Moritz Müller
2019	J	`jnl`	Automating Resolution is NP-Hard. CoRR Albert Atserias, Moritz Müller
2019	A	`conf`	Circular (Yet Sound) Proofs. SAT Albert Atserias, Massimo Lauria
2019	J	`jnl`	Definable inapproximability: new challenges for duplicator. J. Log. Comput. Albert Atserias, Anuj Dawar
2019	J	`jnl`	Generalized satisfiability problems via operator assignments. J. Comput. Syst. Sci. Albert Atserias, Phokion G. Kolaitis, Simone Severini
2019	A*	`conf`	On the Power of Symmetric Linear Programs. LICS Albert Atserias, Anuj Dawar, Joanna Ochremiak
2019	J	`jnl`	On the Power of Symmetric Linear Programs. CoRR Albert Atserias, Anuj Dawar, Joanna Ochremiak
2019	J	`jnl`	Proof Complexity Meets Algebra. ACM Trans. Comput. Log. Albert Atserias, Joanna Ochremiak
2019	J	`jnl`	Quantum and non-signalling graph isomorphisms. J. Comb. Theory B Albert Atserias, Laura Mancinska, David E. Roberson, Robert Sámal, Simone Severini, Antonios Varvitsiotis
2019	J	`jnl`	Relative Entailment Among Probabilistic Implications. Log. Methods Comput. Sci. Albert Atserias, José L. Balcázar, Marie Ely Piceno
2019	A	`conf`	Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs. CCC Albert Atserias, Tuomas Hakoniemi
2018	J	`jnl`	Circular (Yet Sound) Proofs. CoRR Albert Atserias, Massimo Lauria
2018	A*	`conf`	Clique is hard on average for regular resolution. STOC Albert Atserias, Ilario Bonacina, Susanna F. de Rezende, Massimo Lauria, Jakob Nordström, Alexander A. Razborov
2018	A*	`conf`	Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem. LICS Albert Atserias, Joanna Ochremiak
2018	J	`jnl`	Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem. CoRR Albert Atserias, Joanna Ochremiak
2018	B	`conf`	Definable Inapproximability: New Challenges for Duplicator. CSL Albert Atserias, Anuj Dawar
2018	J	`jnl`	Definable Inapproximability: New Challenges for Duplicator. CoRR Albert Atserias, Anuj Dawar
2018	A*	`conf`	On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface. ICALP Albert Atserias, Stephan Kreutzer, Marc Noy
2018	J	`jnl`	Proof Complexity (Dagstuhl Seminar 18051). Dagstuhl Reports Albert Atserias, Jakob Nordström, Pavel Pudlák, Rahul Santhanam
2018	J	`jnl`	Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs. CoRR Albert Atserias, Tuomas Hakoniemi
2017	B	`conf`	Generalized Satisfiability Problems via Operator Assignments. FCT Albert Atserias, Phokion G. Kolaitis, Simone Severini
2017	J	`jnl`	Generalized Satisfiability Problems via Operator Assignments. CoRR Albert Atserias, Phokion G. Kolaitis, Simone Severini
2017	A*	`conf`	Proof Complexity Meets Algebra. ICALP Albert Atserias, Joanna Ochremiak
2017	J	`jnl`	Proof Complexity Meets Algebra. CoRR Albert Atserias, Joanna Ochremiak
2017	J	`jnl`	Size bounds and query plans for relational joins. CoRR Albert Atserias, Martin Grohe, Dániel Marx
2016	J	`jnl`	Narrow Proofs May Be Maximally Long. ACM Trans. Comput. Log. Albert Atserias, Massimo Lauria, Jakob Nordström
2016	B	`conf`	Non-Homogenizable Classes of Finite Structures. CSL Albert Atserias, Szymon Torunczyk
2016	J	`jnl`	Non-Homogenizable Classes of Finite Structures. CoRR Albert Atserias, Szymon Torunczyk
2015	J	`jnl`	A Note on Semi-Algebraic Proofs and Gaussian Elimination over Prime Fields. CoRR Albert Atserias
2015	A*	`conf`	Entailment among Probabilistic Implications. LICS Albert Atserias, José L. Balcázar
2015	J	`jnl`	Entailment among probabilistic implications. CoRR Albert Atserias, José L. Balcázar
2015	J	`jnl`	Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle. J. Symb. Log. Albert Atserias, Moritz Müller, Sergi Oliva
2015	J	`jnl`	Partially definable forcing and bounded arithmetic. Arch. Math. Log. Albert Atserias, Moritz Müller
2014	J	`jnl`	Bounded-width QBF is PSPACE-complete. J. Comput. Syst. Sci. Albert Atserias, Sergi Oliva
2014	J	`jnl`	Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution. CoRR Albert Atserias, Johannes Klaus Fichte, Marc Thurley
2014	J	`jnl`	Degree lower bounds of tower-type for approximating formulas with parity quantifiers. ACM Trans. Comput. Log. Albert Atserias, Anuj Dawar
2014	A	`conf`	Narrow Proofs May Be Maximally Long. CCC Albert Atserias, Massimo Lauria, Jakob Nordström
2014	J	`jnl`	Narrow Proofs May Be Maximally Long. CoRR Albert Atserias, Massimo Lauria, Jakob Nordström
2014	J	`jnl`	Narrow Proofs May Be Maximally Long. Electron. Colloquium Comput. Complex. Albert Atserias, Massimo Lauria, Jakob Nordström
2014	J	`jnl`	The Ordering Principle in a Fragment of Approximate Counting. ACM Trans. Comput. Log. Albert Atserias, Neil Thapen
2013	A	`conf`	Bounded-width QBF is PSPACE-complete. STACS Albert Atserias, Sergi Oliva
2013	J	`jnl`	Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle. Electron. Colloquium Comput. Complex. Albert Atserias, Moritz Müller, Sergi Oliva
2013	A	`conf`	Lower Bounds for DNF-refutations of a Relativized Weak Pigeonhole Principle. CCC Albert Atserias, Moritz Müller, Sergi Oliva
2013	J	`jnl`	Sherali-Adams Relaxations and Indistinguishability in Counting Logics. SIAM J. Comput. Albert Atserias, Elitza N. Maneva
2013	J	`jnl`	Size Bounds and Query Plans for Relational Joins. SIAM J. Comput. Albert Atserias, Martin Grohe, Dániel Marx
2013	J	`jnl`	The Ordering Principle in a Fragment of Approximate Counting. Electron. Colloquium Comput. Complex. Albert Atserias, Neil Thapen
2013	A	`conf`	The Proof-Search Problem between Bounded-Width Resolution and Bounded-Degree Semi-algebraic Proofs. SAT Albert Atserias
2012	J	`jnl`	Bounded-width QBF is PSPACE-complete. Electron. Colloquium Comput. Complex. Albert Atserias, Sergi Oliva
2012	—	`conf`	Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers. ICALP (2) Albert Atserias, Anuj Dawar
2012	J	`jnl`	Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers. Electron. Colloquium Comput. Complex. Albert Atserias, Anuj Dawar
2012	A	`conf`	Sherali-Adams relaxations and indistinguishability in counting logics. ITCS Albert Atserias, Elitza N. Maneva
2011	A*	`conf`	A Why-on-Earth Tutorial on Finite Model Theory. LICS Albert Atserias
2011	J	`jnl`	Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution. J. Artif. Intell. Res. Albert Atserias, Johannes Klaus Fichte, Marc Thurley
2011	J	`jnl`	Foreword. Theory Comput. Syst. Albert Atserias, Mikolaj Bojanczyk, Balder ten Cate, Ronald Fagin, Floris Geerts, Kenneth A. Ross
2011	J	`jnl`	Graph Isomorphism, Sherali-Adams Relaxations and Expressibility in Counting Logics. Electron. Colloquium Comput. Complex. Albert Atserias, Elitza N. Maneva
2011	J	`jnl`	Mean-payoff games and propositional proofs. Inf. Comput. Albert Atserias, Elitza N. Maneva
2010	—	`conf`	Mean-Payoff Games and Propositional Proofs. ICALP (1) Albert Atserias, Elitza N. Maneva
2010	J	`jnl`	Mean-payoff games and propositional proofs. Electron. Colloquium Comput. Complex. Albert Atserias, Elitza N. Maneva
2009	J	`jnl`	Affine systems of equations and counting infinitary logic. Theor. Comput. Sci. Albert Atserias, Andrei A. Bulatov, Anuj Dawar
2009	A	`conf`	Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution. SAT Albert Atserias, Johannes Klaus Fichte, Marc Thurley
2009	B	`conf`	Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems. CSL Albert Atserias, Mark Weyer
2009	B	`conf`	Four Subareas of the Theory of Constraints, and Their Links. MFCS Albert Atserias
2008	J	`jnl`	A combinatorial characterization of resolution width. J. Comput. Syst. Sci. Albert Atserias, Víctor Dalmau
2008	J	`jnl`	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. Albert Atserias
2008	J	`jnl`	On digraph coloring problems and treewidth duality. Eur. J. Comb. Albert Atserias
2008	J	`jnl`	Preservation under Extensions on Well-Behaved Finite Structures. SIAM J. Comput. Albert Atserias, Anuj Dawar, Martin Grohe
2008	A*	`conf`	Size Bounds and Query Plans for Relational Joins. FOCS Albert Atserias, Martin Grohe, Dániel Marx
2007	A*	`conf`	Affine Systems of Equations and Counting Infinitary Logic. ICALP Albert Atserias, Andrei A. Bulatov, Anuj Dawar
2007	J	`jnl`	Conjunctive query evaluation by search-tree revisited. Theor. Comput. Sci. Albert Atserias
2007	A*	`conf`	On the Power of ICALP Albert Atserias, Andrei A. Bulatov, Víctor Dalmau
2006	A	`conf`	Distinguishing SAT from Polynomial-Size Circuits, through Black-Box Queries. CCC Albert Atserias
2006	J	`jnl`	On preservation under homomorphisms and unions of conjunctive queries. J. ACM Albert Atserias, Anuj Dawar, Phokion G. Kolaitis
2005	A	`conf`	Conjunctive Query Evaluation by Search Tree Revisited. ICDT Albert Atserias
2005	A*	`conf`	Definability on a Random 3-CNF Formula. LICS Albert Atserias
2005	J	`jnl`	Non-Uniform Hardness for NP via Black-Box Adversaries Electron. Colloquium Comput. Complex. Albert Atserias
2005	A*	`conf`	On Digraph Coloring Problems and Treewidth Duality. LICS Albert Atserias
2005	A*	`conf`	Preservation Under Extensions on Well-Behaved Finite Structures. ICALP Albert Atserias, Anuj Dawar, Martin Grohe
2004	A	`conf`	Constraint Propagation as a Proof System. CP Albert Atserias, Phokion G. Kolaitis, Moshe Y. Vardi
2004	B	`conf`	Notions of Average-Case Complexity for Random 3-SAT. CSL Albert Atserias
2004	A*	`conf`	On Preservation under Homomorphisms and Unions of Conjunctive Queries. PODS Albert Atserias, Anuj Dawar, Phokion G. Kolaitis
2004	J	`jnl`	On sufficient conditions for unsatisfiability of random formulas. J. ACM Albert Atserias
2004	J	`jnl`	On the automatizability of resolution and related propositional proof systems. Inf. Comput. Albert Atserias, Maria Luisa Bonet
2003	A	`conf`	A Combinatorial Characterization of Resolution Width. CCC Albert Atserias, Víctor Dalmau
2003	J	`jnl`	Improved bounds on the Weak Pigeonhole Principle and infinitely many primes from weaker axioms. Theor. Comput. Sci. Albert Atserias
2003	J	`jnl`	On Chvatal Rank and Cutting Planes Proofs Electron. Colloquium Comput. Complex. Albert Atserias, Maria Luisa Bonet, Jordi Levy
2002	J	`jnl`	A Combinatorial Characterization of Resolution Width Electron. Colloquium Comput. Complex. Albert Atserias, Víctor Dalmau
2002	J	`jnl`	Lower Bounds for the Weak Pigeonhole Principle and Random Formulas beyond Resolution. Inf. Comput. Albert Atserias, Maria Luisa Bonet, Juan Luis Esteban
2002	J	`jnl`	Monotone simulations of non-monotone proofs. J. Comput. Syst. Sci. Albert Atserias, Nicola Galesi, Pavel Pudlák
2002	J	`jnl`	On the Automatizability of Resolution and Related Propositional Proof Systems Electron. Colloquium Comput. Complex. Albert Atserias, Maria Luisa Bonet
2002	B	`conf`	On the Automatizability of Resolution and Related Propositional Proof Systems. CSL Albert Atserias, Maria Luisa Bonet
2002	A*	`conf`	Unsatisfiable Random Formulas Are Hard to Certify. LICS Albert Atserias
2001	B	`conf`	Improved Bounds on the Weak Pigeonhole Principle and Infinitely Many Primes from Weaker Axioms. MFCS Albert Atserias
2001	A*	`conf`	Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution. ICALP Albert Atserias, Maria Luisa Bonet, Juan Luis Esteban
2001	J	`jnl`	Monotone Proofs of the Pigeon Hole Principle. Math. Log. Q. Albert Atserias, Nicola Galesi, Ricard Gavaldà
2001	A	`conf`	Monotone Simulations of Nonmonotone Proofs. CCC Albert Atserias, Nicola Galesi, Pavel Pudlák
2000	J	`jnl`	Monotone Proofs of the Pigeon Hole Principle Electron. Colloquium Comput. Complex. Albert Atserias, Nicola Galesi, Ricard Gavaldà
2000	A*	`conf`	Monotone Proofs of the Pigeon Hole Principle. ICALP Albert Atserias, Nicola Galesi, Ricard Gavaldà
2000	J	`jnl`	Monotone simulations of nonmonotone propositional proofs Electron. Colloquium Comput. Complex. Albert Atserias, Nicola Galesi, Pavel Pudlák
2000	B	`conf`	The Descriptive Comlexity of the Fixed-Points of Bounded Formulas. CSL Albert Atserias
1999	A*	`conf`	First-Order Logic vs. Fixed-Point Logic in Finite Set Theory. LICS Albert Atserias, Phokion G. Kolaitis