default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDAlbert Atserias
Person information
- affiliation: Polytechnic University of Catalonia, Barcelona, Spain
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2024
[j36]Albert Atserias
, Phokion G. Kolaitis:
Consistency of Relations over Monoids. Proc. ACM Manag. Data 2(2): 107 (2024)- [i37]Albert Atserias, Iddo Tzameret:
Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [j35]Albert Atserias, Joanna Fijalkow:
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem. SIAM J. Comput. 52(5): 1193-1229 (2023) - [j34]Albert Atserias, Massimo Lauria:
Circular (Yet Sound) Proofs in Propositional Logic. ACM Trans. Comput. Log. 24(3): 20:1-20:26 (2023) - [c49]Albert Atserias, Sam Buss, Moritz Müller:
On the Consistency of Circuit Lower Bounds for Non-deterministic Time. STOC 2023: 1257-1270 - [i36]Albert Atserias, Sam Buss, Moritz Müller:
On the Consistency of Circuit Lower Bounds for Non-Deterministic Time. CoRR abs/2303.01016 (2023) - [i35]Albert Atserias, Phokion G. Kolaitis:
Consistency of Relations over Monoids. CoRR abs/2312.02023 (2023) - 2022
- [j33]Albert Atserias, Phokion G. Kolaitis:
Structure and Complexity of Bag Consistency. SIGMOD Rec. 51(1): 78-85 (2022) - [c48]Albert Atserias:
Towards a Theory of Algorithmic Proof Complexity (Invited Talk). ICALP 2022: 1:1-1:2 - [c47]Albert Atserias, Víctor Dalmau:
Promise Constraint Satisfaction and Width. SODA 2022: 1129-1153 - [i34]Albert Atserias, Christoph Berkholz, Kousha Etessami, Joanna Ochremiak:
Finite and Algorithmic Model Theory (Dagstuhl Seminar 22051). Dagstuhl Reports 12(1): 101-118 (2022) - 2021
- [j32]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): 23:1-23:26 (2021) - [j31]Albert Atserias, Anuj Dawar, Joanna Ochremiak:
On the Power of Symmetric Linear Programs. J. ACM 68(4): 26:1-26:35 (2021) - [c46]Albert Atserias, Phokion G. Kolaitis, Wei-Lin Wu:
On the Expressive Power of Homomorphism Counts. LICS 2021: 1-13 - [c45]Albert Atserias, Phokion G. Kolaitis:
Structure and Complexity of Bag Consistency. PODS 2021: 247-259 - [i33]Albert Atserias, Phokion G. Kolaitis, Wei-Lin Wu:
On the Expressive Power of Homomorphism Counts. CoRR abs/2101.12733 (2021) - [i32]Albert Atserias, Víctor Dalmau:
Promise Constraint Satisfaction and Width. CoRR abs/2107.05886 (2021) - 2020
- [j30]Albert Atserias, Moritz Müller:
Automating Resolution is NP-Hard. J. ACM 67(5): 31:1-31:17 (2020) - [c44]Albert Atserias:
Proofs of Soundness and Proof Search (Invited Talk). FSTTCS 2020: 2:1-2:1 - [i31]Albert Atserias, Phokion G. Kolaitis:
Consistency, Acyclicity, and Positive Semirings. CoRR abs/2009.09488 (2020) - [i30]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 abs/2012.09476 (2020) - [i29]Albert Atserias, Phokion G. Kolaitis:
Structure and Complexity of Bag Consistency. CoRR abs/2012.12126 (2020)
2010 – 2019
- 2019
- [j29]Albert Atserias, Phokion G. Kolaitis, Simone Severini:
Generalized satisfiability problems via operator assignments. J. Comput. Syst. Sci. 105: 171-198 (2019) - [j28]Albert Atserias, Laura Mancinska, David E. Roberson, Robert Sámal, Simone Severini, Antonios Varvitsiotis:
Quantum and non-signalling graph isomorphisms. J. Comb. Theory B 136: 289-328 (2019) - [j27]Albert Atserias, José L. Balcázar, Marie Ely Piceno:
Relative Entailment Among Probabilistic Implications. Log. Methods Comput. Sci. 15(1) (2019) - [j26]Albert Atserias, Anuj Dawar:
Definable inapproximability: new challenges for duplicator. J. Log. Comput. 29(8): 1185-1210 (2019) - [j25]Albert Atserias, Joanna Ochremiak:
Proof Complexity Meets Algebra. ACM Trans. Comput. Log. 20(1): 1:1-1:46 (2019) - [c43]Albert Atserias, Tuomas Hakoniemi:
Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs. CCC 2019: 24:1-24:20 - [c42]Albert Atserias, Moritz Müller:
Automating Resolution is NP-Hard. FOCS 2019: 498-509 - [c41]Albert Atserias, Anuj Dawar, Joanna Ochremiak:
On the Power of Symmetric Linear Programs. LICS 2019: 1-13 - [c40]Albert Atserias, Massimo Lauria:
Circular (Yet Sound) Proofs. SAT 2019: 1-18 - [i28]Albert Atserias, Anuj Dawar, Joanna Ochremiak:
On the Power of Symmetric Linear Programs. CoRR abs/1901.07825 (2019) - [i27]Albert Atserias, Moritz Müller:
Automating Resolution is NP-Hard. CoRR abs/1904.02991 (2019) - 2018
- [c39]Albert Atserias, Anuj Dawar:
Definable Inapproximability: New Challenges for Duplicator. CSL 2018: 7:1-7:21 - [c38]Albert Atserias, Stephan Kreutzer, Marc Noy:
On Zero-One and Convergence Laws for Graphs Embeddable on a Fixed Surface. ICALP 2018: 116:1-116:14 - [c37]Albert Atserias, Joanna Ochremiak:
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem. LICS 2018: 66-75 - [c36]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: 866-877 - [i26]Albert Atserias, Joanna Ochremiak:
Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem. CoRR abs/1802.02388 (2018) - [i25]Albert Atserias, Massimo Lauria:
Circular (Yet Sound) Proofs. CoRR abs/1802.05266 (2018) - [i24]Albert Atserias, Anuj Dawar:
Definable Inapproximability: New Challenges for Duplicator. CoRR abs/1806.11307 (2018) - [i23]Albert Atserias, Tuomas Hakoniemi:
Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs. CoRR abs/1811.01351 (2018) - [i22]Albert Atserias, Jakob Nordström, Pavel Pudlák, Rahul Santhanam:
Proof Complexity (Dagstuhl Seminar 18051). Dagstuhl Reports 8(1): 124-157 (2018) - 2017
- [c35]Albert Atserias, Phokion G. Kolaitis, Simone Severini:
Generalized Satisfiability Problems via Operator Assignments. FCT 2017: 56-68 - [c34]Albert Atserias, Joanna Ochremiak:
Proof Complexity Meets Algebra. ICALP 2017: 110:1-110:14 - [i21]Albert Atserias, Phokion G. Kolaitis, Simone Severini:
Generalized Satisfiability Problems via Operator Assignments. CoRR abs/1704.01736 (2017) - [i20]Albert Atserias, Martin Grohe, Dániel Marx:
Size bounds and query plans for relational joins. CoRR abs/1711.03860 (2017) - [i19]Albert Atserias, Joanna Ochremiak:
Proof Complexity Meets Algebra. CoRR abs/1711.07320 (2017) - 2016
- [j24]Albert Atserias, Massimo Lauria, Jakob Nordström:
Narrow Proofs May Be Maximally Long. ACM Trans. Comput. Log. 17(3): 19 (2016) - [c33]Albert Atserias, Szymon Torunczyk:
Non-Homogenizable Classes of Finite Structures. CSL 2016: 16:1-16:16 - [i18]Albert Atserias, Szymon Torunczyk:
Non-Homogenizable Classes of Finite Structures. CoRR abs/1605.01199 (2016) - 2015
- [j23]Albert Atserias, Moritz Müller:
Partially definable forcing and bounded arithmetic. Arch. Math. Log. 54(1-2): 1-33 (2015) - [j22]Albert Atserias, Moritz Müller, Sergi Oliva:
Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle. J. Symb. Log. 80(2): 450-476 (2015) - [c32]Albert Atserias, José L. Balcázar:
Entailment among Probabilistic Implications. LICS 2015: 621-632 - [i17]Albert Atserias, José L. Balcázar:
Entailment among probabilistic implications. CoRR abs/1501.04826 (2015) - [i16]Albert Atserias:
A Note on Semi-Algebraic Proofs and Gaussian Elimination over Prime Fields. CoRR abs/1502.03974 (2015) - 2014
- [j21]Albert Atserias, Sergi Oliva:
Bounded-width QBF is PSPACE-complete. J. Comput. Syst. Sci. 80(7): 1415-1429 (2014) - [j20]Albert Atserias, Anuj Dawar:
Degree lower bounds of tower-type for approximating formulas with parity quantifiers. ACM Trans. Comput. Log. 15(1): 6:1-6:24 (2014) - [j19]Albert Atserias, Neil Thapen:
The Ordering Principle in a Fragment of Approximate Counting. ACM Trans. Comput. Log. 15(4): 29:1-29:11 (2014) - [c31]Albert Atserias, Massimo Lauria, Jakob Nordström:
Narrow Proofs May Be Maximally Long. CCC 2014: 286-297 - [i15]Albert Atserias, Johannes Klaus Fichte, Marc Thurley:
Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution. CoRR abs/1401.3868 (2014) - [i14]Albert Atserias, Massimo Lauria, Jakob Nordström:
Narrow Proofs May Be Maximally Long. CoRR abs/1409.2731 (2014) - [i13]Albert Atserias, Massimo Lauria, Jakob Nordström:
Narrow Proofs May Be Maximally Long. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [j18]Albert Atserias, Elitza N. Maneva:
Sherali-Adams Relaxations and Indistinguishability in Counting Logics. SIAM J. Comput. 42(1): 112-137 (2013) - [j17]Albert Atserias, Martin Grohe, Dániel Marx:
Size Bounds and Query Plans for Relational Joins. SIAM J. Comput. 42(4): 1737-1767 (2013) - [c30]Albert Atserias, Moritz Müller, Sergi Oliva:
Lower Bounds for DNF-refutations of a Relativized Weak Pigeonhole Principle. CCC 2013: 109-120 - [c29]Albert Atserias:
The Proof-Search Problem between Bounded-Width Resolution and Bounded-Degree Semi-algebraic Proofs. SAT 2013: 1-17 - [c28]Albert Atserias, Sergi Oliva:
Bounded-width QBF is PSPACE-complete. STACS 2013: 44-54 - [i12]Albert Atserias, Moritz Müller, Sergi Oliva:
Lower Bounds for DNF-Refutations of a Relativized Weak Pigeonhole Principle. Electron. Colloquium Comput. Complex. TR13 (2013) - [i11]Albert Atserias, Neil Thapen:
The Ordering Principle in a Fragment of Approximate Counting. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [c27]Albert Atserias, Anuj Dawar:
Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers. ICALP (2) 2012: 67-78 - [c26]Albert Atserias, Elitza N. Maneva:
Sherali-Adams relaxations and indistinguishability in counting logics. ITCS 2012: 367-379 - [i10]Albert Atserias, Anuj Dawar:
Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers. Electron. Colloquium Comput. Complex. TR12 (2012) - [i9]Albert Atserias, Sergi Oliva:
Bounded-width QBF is PSPACE-complete. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j16]Albert Atserias, Elitza N. Maneva:
Mean-payoff games and propositional proofs. Inf. Comput. 209(4): 664-691 (2011) - [j15]Albert Atserias, Johannes Klaus Fichte, Marc Thurley:
Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution. J. Artif. Intell. Res. 40: 353-373 (2011) - [j14]Albert Atserias, Mikolaj Bojanczyk, Balder ten Cate, Ronald Fagin, Floris Geerts, Kenneth A. Ross:
Foreword. Theory Comput. Syst. 49(2): 365-366 (2011) - [c25]Albert Atserias:
A Why-on-Earth Tutorial on Finite Model Theory. LICS 2011: 3 - [i8]Albert Atserias, Elitza N. Maneva:
Graph Isomorphism, Sherali-Adams Relaxations and Expressibility in Counting Logics. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [c24]Albert Atserias, Elitza N. Maneva:
Mean-Payoff Games and Propositional Proofs. ICALP (1) 2010: 102-113 - [i7]Albert Atserias, Elitza N. Maneva:
Mean-payoff games and propositional proofs. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j13]Albert Atserias, Andrei A. Bulatov, Anuj Dawar:
Affine systems of equations and counting infinitary logic. Theor. Comput. Sci. 410(18): 1666-1683 (2009) - [c23]Albert Atserias, Mark Weyer:
Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems. CSL 2009: 102-116 - [c22]Albert Atserias:
Four Subareas of the Theory of Constraints, and Their Links. MFCS 2009: 1 - [c21]Albert Atserias, Johannes Klaus Fichte, Marc Thurley:
Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution. SAT 2009: 114-127 - 2008
- [j12]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): 55-59 (2008) - [j11]Albert Atserias:
On digraph coloring problems and treewidth duality. Eur. J. Comb. 29(4): 796-820 (2008) - [j10]Albert Atserias, Víctor Dalmau:
A combinatorial characterization of resolution width. J. Comput. Syst. Sci. 74(3): 323-334 (2008) - [j9]Albert Atserias, Anuj Dawar, Martin Grohe:
Preservation under Extensions on Well-Behaved Finite Structures. SIAM J. Comput. 38(4): 1364-1381 (2008) - [c20]Albert Atserias, Martin Grohe, Dániel Marx:
Size Bounds and Query Plans for Relational Joins. FOCS 2008: 739-748 - 2007
- [j8]Albert Atserias:
Conjunctive query evaluation by search-tree revisited. Theor. Comput. Sci. 371(3): 155-168 (2007) - [c19]Albert Atserias, Andrei A. Bulatov, Víctor Dalmau:
On the Power of k -Consistency. ICALP 2007: 279-290 - [c18]Albert Atserias, Andrei A. Bulatov, Anuj Dawar:
Affine Systems of Equations and Counting Infinitary Logic. ICALP 2007: 558-570 - 2006
- [j7]Albert Atserias, Anuj Dawar, Phokion G. Kolaitis:
On preservation under homomorphisms and unions of conjunctive queries. J. ACM 53(2): 208-237 (2006) - [c17]Albert Atserias:
Distinguishing SAT from Polynomial-Size Circuits, through Black-Box Queries. CCC 2006: 88-95 - 2005
- [c16]Albert Atserias, Anuj Dawar, Martin Grohe:
Preservation Under Extensions on Well-Behaved Finite Structures. ICALP 2005: 1437-1449 - [c15]Albert Atserias:
Conjunctive Query Evaluation by Search Tree Revisited. ICDT 2005: 53-67 - [c14]Albert Atserias:
On Digraph Coloring Problems and Treewidth Duality. LICS 2005: 106-115 - [c13]Albert Atserias:
Definability on a Random 3-CNF Formula. LICS 2005: 458-466 - [i6]Albert Atserias:
Non-Uniform Hardness for NP via Black-Box Adversaries. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j6]Albert Atserias, Maria Luisa Bonet:
On the automatizability of resolution and related propositional proof systems. Inf. Comput. 189(2): 182-201 (2004) - [j5]Albert Atserias:
On sufficient conditions for unsatisfiability of random formulas. J. ACM 51(2): 281-311 (2004) - [c12]Albert Atserias, Phokion G. Kolaitis, Moshe Y. Vardi:
Constraint Propagation as a Proof System. CP 2004: 77-91 - [c11]Albert Atserias:
Notions of Average-Case Complexity for Random 3-SAT. CSL 2004: 1-5 - [c10]Albert Atserias, Anuj Dawar, Phokion G. Kolaitis:
On Preservation under Homomorphisms and Unions of Conjunctive Queries. PODS 2004: 319-329 - 2003
- [j4]Albert Atserias:
Improved bounds on the Weak Pigeonhole Principle and infinitely many primes from weaker axioms. Theor. Comput. Sci. 295: 27-39 (2003) - [c9]Albert Atserias, Víctor Dalmau:
A Combinatorial Characterization of Resolution Width. CCC 2003: 239-247 - [i5]Albert Atserias, Maria Luisa Bonet, Jordi Levy:
On Chvatal Rank and Cutting Planes Proofs. Electron. Colloquium Comput. Complex. TR03 (2003) - 2002
- [j3]Albert Atserias, Maria Luisa Bonet, Juan Luis Esteban:
Lower Bounds for the Weak Pigeonhole Principle and Random Formulas beyond Resolution. Inf. Comput. 176(2): 136-152 (2002) - [j2]Albert Atserias, Nicola Galesi, Pavel Pudlák:
Monotone simulations of non-monotone proofs. J. Comput. Syst. Sci. 65(4): 626-638 (2002) - [c8]Albert Atserias, Maria Luisa Bonet:
On the Automatizability of Resolution and Related Propositional Proof Systems. CSL 2002: 569-583 - [c7]Albert Atserias:
Unsatisfiable Random Formulas Are Hard to Certify. LICS 2002: 325-334 - [i4]Albert Atserias, Maria Luisa Bonet:
On the Automatizability of Resolution and Related Propositional Proof Systems. Electron. Colloquium Comput. Complex. TR02 (2002) - [i3]Albert Atserias, Víctor Dalmau:
A Combinatorial Characterization of Resolution Width. Electron. Colloquium Comput. Complex. TR02 (2002) - 2001
- [j1]Albert Atserias, Nicola Galesi, Ricard Gavaldà:
Monotone Proofs of the Pigeon Hole Principle. Math. Log. Q. 47(4): 461-474 (2001) - [c6]Albert Atserias, Nicola Galesi, Pavel Pudlák:
Monotone Simulations of Nonmonotone Proofs. CCC 2001: 36-41 - [c5]Albert Atserias, Maria Luisa Bonet, Juan Luis Esteban:
Lower Bounds for the Weak Pigeonhole Principle Beyond Resolution. ICALP 2001: 1005-1016 - [c4]Albert Atserias:
Improved Bounds on the Weak Pigeonhole Principle and Infinitely Many Primes from Weaker Axioms. MFCS 2001: 148-158 - 2000
- [c3]Albert Atserias:
The Descriptive Comlexity of the Fixed-Points of Bounded Formulas. CSL 2000: 172-186 - [c2]Albert Atserias, Nicola Galesi, Ricard Gavaldà:
Monotone Proofs of the Pigeon Hole Principle. ICALP 2000: 151-162 - [i2]Albert Atserias, Nicola Galesi, Ricard Gavaldà:
Monotone Proofs of the Pigeon Hole Principle. Electron. Colloquium Comput. Complex. TR00 (2000) - [i1]Albert Atserias, Nicola Galesi, Pavel Pudlák:
Monotone simulations of nonmonotone propositional proofs. Electron. Colloquium Comput. Complex. TR00 (2000)
1990 – 1999
- 1999
- [c1]Albert Atserias, Phokion G. Kolaitis:
First-Order Logic vs. Fixed-Point Logic in Finite Set Theory. LICS 1999: 275-284
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-18 19:21 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
