Albert Atserias

Generating author description...

All published works

Action	Title	Year	Authors
+ PDF Chat	Feasibly Constructive Proof of Schwartz-Zippel Lemma and the Complexity of Finding Hitting Sets	2024	Albert Atserias Iddo Tzameret
+ PDF Chat	On the Consistency of Circuit Lower Bounds for Non-Deterministic Time	2024	Albert Atserias Sam Buss Moritz Müller
+ PDF Chat	Consistency of Relations over Monoids	2024	Albert Atserias Phokion G. Kolaitis
+ PDF Chat	Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem	2023	Albert Atserias Joanna Fijalkow
+	On the Consistency of Circuit Lower Bounds for Non-deterministic Time	2023	Albert Atserias Sam Buss Moritz Müller
+	Circular (Yet Sound) Proofs in Propositional Logic	2023	Albert Atserias Massimo Lauria
+	On the Consistency of Circuit Lower Bounds for Non-Deterministic Time	2023	Albert Atserias Sam Buss Moritz Müller
+	Consistency of Relations over Monoids	2023	Albert Atserias Phokion G. Kolaitis
+ PDF Chat	Structure and Complexity of Bag Consistency	2022	Albert Atserias Phokion G. Kolaitis
+ PDF Chat	Promise Constraint Satisfaction and Width	2022	Albert Atserias Víctor Dalmau
+ PDF Chat	On the Power of Symmetric Linear Programs	2021	Albert Atserias Anuj Dawar Joanna Ochremiak
+	Promise Constraint Satisfaction and Width.	2021	Albert Atserias Víctor Dalmau
+ PDF Chat	Clique Is Hard on Average for Regular Resolution	2021	Albert Atserias Ilario Bonacina Susanna F. de Rezende Massimo Lauria Jakob Nordström Alexander Razborov
+ PDF Chat	On the Expressive Power of Homomorphism Counts	2021	Albert Atserias Phokion G. Kolaitis Wei-Lin Wu
+	Structure and Complexity of Bag Consistency	2021	Albert Atserias Phokion G. Kolaitis
+	On the Expressive Power of Homomorphism Counts	2021	Albert Atserias Phokion G. Kolaitis Wei-Lin Wu
+	Promise Constraint Satisfaction and Width	2021	Albert Atserias Víctor Dalmau
+	Clique Is Hard on Average for Regular Resolution	2020	Albert Atserias Ilario Bonacina Susanna F. de Rezende Massimo Lauria Jakob Nordström Alexander Razborov
+ PDF Chat	Automating Resolution is NP-Hard	2020	Albert Atserias Moritz Müller
+	Structure and Complexity of Bag Consistency	2020	Albert Atserias Phokion G. Kolaitis
+	Clique Is Hard on Average for Regular Resolution	2020	Albert Atserias Ilario Bonacina Susanna F. de Rezende Massimo Lauria Jakob Nordström Alexander Razborov
+	Consistency, Acyclicity, and Positive Semirings	2020	Albert Atserias Phokion G. Kolaitis
+ PDF Chat	Automating Resolution is NP-Hard	2019	Albert Atserias Moritz Müller
+ PDF Chat	Definable inapproximability: new challenges for duplicator	2019	Albert Atserias Anuj Dawar
+ PDF Chat	On the Power of Symmetric Linear Programs	2019	Albert Atserias Anuj Dawar Joanna Ochremiak
+	Generalized satisfiability problems via operator assignments	2019	Albert Atserias Phokion G. Kolaitis Simone Severini
+	Automating Resolution is NP-Hard	2019	Albert Atserias Moritz Müller
+	On the Power of Symmetric Linear Programs	2019	Albert Atserias Anuj Dawar Joanna Ochremiak
+ PDF Chat	Circular (Yet Sound) Proofs	2019	Albert Atserias Massimo Lauria
+	Automating Resolution is NP-Hard	2019	Albert Atserias Moritz Müller
+	On the Power of Symmetric Linear Programs	2019	Albert Atserias Anuj Dawar Joanna Ochremiak
+ PDF Chat	Proof Complexity Meets Algebra	2018	Albert Atserias Joanna Ochremiak
+	Quantum and non-signalling graph isomorphisms	2018	Albert Atserias Laura Mančinska David E. Roberson Robert Šámal Simone Severini Antonios Varvitsiotis
+	Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs	2018	Albert Atserias Tuomas Hakoniemi
+	Definable Inapproximability: New Challenges for Duplicator	2018	Albert Atserias Anuj Dawar
+	Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem	2018	Albert Atserias Joanna Ochremiak
+ PDF Chat	Clique is hard on average for regular resolution	2018	Albert Atserias Ilario Bonacina Susanna F. de Rezende Massimo Lauria Jakob Nordström Alexander Razborov
+	Circular (Yet Sound) Proofs	2018	Albert Atserias Massimo Lauria
+	Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Isomorphism Problem	2018	Albert Atserias Joanna Ochremiak
+	Size-Degree Trade-Offs for Sums-of-Squares and Positivstellensatz Proofs	2018	Albert Atserias Tuomas Hakoniemi
+	Definable Inapproximability: New Challenges for Duplicator	2018	Albert Atserias Anuj Dawar
+	Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem	2018	Albert Atserias Joanna Fijalkow
+	Circular (Yet Sound) Proofs	2018	Albert Atserias Massimo Lauria
+	Proof Complexity Meets Algebra	2017	Albert Atserias Joanna Ochremiak
+	Size bounds and query plans for relational joins	2017	Albert Atserias Martin Grohe Dániel Marx
+	Generalized Satisfiability Problems via Operator Assignments	2017	Albert Atserias Phokion G. Kolaitis Simone Severini
+ PDF Chat	Generalized Satisfiability Problems via Operator Assignments	2017	Albert Atserias Phokion G. Kolaitis Simone Severini
+	Generalized Satisfiability Problems via Operator Assignments	2017	Albert Atserias Phokion G. Kolaitis Simone Severini
+	Proof Complexity Meets Algebra	2017	Albert Atserias Joanna Ochremiak
+	Size bounds and query plans for relational joins	2017	Albert Atserias Martin Grohe Dániel Marx
+	Quantum and non-signalling graph isomorphisms	2016	Albert Atserias Laura Mančinska David E. Roberson Robert Šámal Simone Severini Antonios Varvitsiotis
+ PDF Chat	Narrow Proofs May Be Maximally Long	2016	Albert Atserias Massimo Lauria Jakob Nordström
+	Non-Homogenizable Classes of Finite Structures	2016	Albert Atserias Szymon Toruńczyk
+	Non-Homogenizable Classes of Finite Structures	2016	Albert Atserias Szymon Toruńczyk
+	Quantum and non-signalling graph isomorphisms	2016	Albert Atserias Laura Mančinska David E. Roberson Robert Šámal Simone Severini Antonios Varvitsiotis
+	A Note on Semi-Algebraic Proofs and Gaussian Elimination over Prime Fields.	2015	Albert Atserias
+	Relative Entailment Among Probabilistic Implications	2015	Albert Atserias José L. Balcázar Marie Ely Piceno
+	A Note on Semi-Algebraic Proofs and Gaussian Elimination over Prime Fields	2015	Albert Atserias
+	Relative Entailment Among Probabilistic Implications	2015	Albert Atserias José L. Balcázar Marie Ely Piceno
+	Narrow Proofs May Be Maximally Long	2014	Albert Atserias Massimo Lauria Jakob Nordström
+ PDF Chat	The Ordering Principle in a Fragment of Approximate Counting	2014	Albert Atserias Neil Thapen
+ PDF Chat	Narrow Proofs May Be Maximally Long	2014	Albert Atserias Massimo Lauria Jakob Nordström
+ PDF Chat	Degree lower bounds of tower-type for approximating formulas with parity quantifiers	2014	Albert Atserias Anuj Dawar
+	Narrow Proofs May Be Maximally Long.	2014	Albert Atserias Massimo Lauria Jakob Nordström
+	Narrow Proofs May Be Maximally Long	2014	Albert Atserias Massimo Lauria Jakob Nordström
+ PDF Chat	Size Bounds and Query Plans for Relational Joins	2013	Albert Atserias Martin Grohe Dániel Marx
+	The Ordering Principle in a Fragment of Approximate Counting.	2013	Albert Atserias Neil Thapen
+	Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers.	2012	Albert Atserias Anuj Dawar
+ PDF Chat	Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers	2012	Albert Atserias Anuj Dawar
+ PDF Chat	Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution	2011	Albert Atserias Johannes K. Fichte Marc Thurley
+ PDF Chat	Decidable Relationships between Consistency Notions for Constraint Satisfaction Problems	2009	Albert Atserias Mark Weyer
+ PDF Chat	Clause-Learning Algorithms with Many Restarts and Bounded-Width Resolution	2009	Albert Atserias Johannes K. Fichte Marc Thurley
+ PDF Chat	Size Bounds and Query Plans for Relational Joins	2008	Albert Atserias Martin Grohe Dániel Marx
+	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).	2008	Albert Atserias
+	Complexitat de Kolmogorov i qüestions de fonament	2003	Albert Atserias
+	On the Automatizability of Resolution and Related Propositional Proof Systems	2002	Albert Atserias Marı́a Luisa Bonet
+	A Note on polynomial-size monotone proofs of the pigeon hole principle	2000	Albert Atserias

Common Coauthors

Coauthor	Papers Together
Massimo Lauria	13
Phokion G. Kolaitis	12
Anuj Dawar	10
Jakob Nordström	9
Joanna Ochremiak	9
Simone Severini	7
Alexander Razborov	4
Martin Grohe	4
Dániel Marx	4
Ilario Bonacina	4
Susanna F. de Rezende	4
Víctor Dalmau	3
Moritz Müller	3
Laura Mančinska	3
David E. Roberson	3
Sam Buss	3
Antonios Varvitsiotis	3
Robert Šámal	3
Moritz Müller	3
José L. Balcázar	2
Joanna Fijalkow	2
Marie Ely Piceno	2
Tuomas Hakoniemi	2
Neil Thapen	2
Marc Thurley	2
Szymon Toruńczyk	2
Wei-Lin Wu	2
Johannes K. Fichte	2
Iddo Tzameret	1
Marı́a Luisa Bonet	1
Mark Weyer	1
Moritz Müller	1

Commonly Cited References

Action	Title	Year	Authors	# of times referenced
+ PDF Chat	Narrow Proofs May Be Maximally Long	2016	Albert Atserias Massimo Lauria Jakob Nordström	7
+ PDF Chat	On the weak pigeonhole principle	2001	Jan Krajı́ček	7
+	Complexity of Null- and Positivstellensatz proofs	2001	Dima Grigoriev Nicolai Vorobjov	6
+ PDF Chat	Characterization of Binary Constraint System Games	2014	Richard Cleve Rajat Mittal	5
+ PDF Chat	Hypercontractivity, sum-of-squares proofs, and their applications	2012	Boaz Barak Fernando G. S. L. Brandão Aram W. Harrow Jonathan A. Kelner David Steurer Yuan Zhou	5
+	Structured semidefinite programs and semialgebraic geometry methods in robustness and optimization	2000	Pablo A. Parrilo	5
+ PDF Chat	Strong duality in Lasserre’s hierarchy for polynomial optimization	2015	Cédric Josz Didier Henrion	5
+ PDF Chat	A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming	2003	Monique Laurent	5
+	Tsirelson’s problem and an embedding theorem for groups arising from non-local games	2019	William Slofstra	4
+ PDF Chat	Hardness of Robust Graph Isomorphism, Lasserre Gaps, and Asymmetry of Random Graphs	2013	Ryan O’Donnell John C. Wright Chenggang Wu Yuan Zhou	4
+	Global Optimization with Polynomials and the Problem of Moments	2001	Jean B. Lasserre	4
+ PDF Chat	On polynomial time computation over unordered structures	2002	Andreas Blass Yuri Gurevich Saharon Shelah	4
+ PDF Chat	Perfect commuting-operator strategies for linear system games	2017	Richard Cleve Li Liu William Slofstra	4
+ PDF Chat	Which graphs are determined by their spectrum?	2003	Edwin van Dam Willem H. Haemers	4
+	Sherali–Adams relaxations of graph isomorphism polytopes	2014	Peter N. Malkin	4
+	Lower bounds for polynomial calculus: non-binomial case	2001	M. Alekhnovich Alexander Razborov	4
+	Tight rank lower bounds for the Sherali–Adams proof system	2009	Stefan Dantchev Barnaby Martin Mark Rhodes	4
+ PDF Chat	Finding a large hidden clique in a random graph	1998	Noga Alon Michael Krivelevich Benny Sudakov	4
+ PDF Chat	The complexity of proving that a graph is Ramsey	2016	Massimo Lauria Pavel Pudlák Vojtěch Rödl Neil Thapen	3
+	Introduction to Hilbert Space: And the Theory of Spectral Multiplicity	1998	Paul R. Halmos	3
+	On the Shannon capacity of a graph	1979	László Lovász	3
+ PDF Chat	The Constant Inapproximability of the Parameterized Dominating Set Problem	2019	Yijia Chen Bingkai Lin	3
+	The Sandwich Theorem	1994	Donald E. Knuth	3
+	Galois theory for post algebras. I	1972	В. Г. Боднарчук Lev Arkadʹevich Kaluzhnin V. N. Kotov B. A. Romov	3
+	Analysis of Boolean Functions	2014	Ryan O’Donnell	3
+ PDF Chat	The Matching Polytope has Exponential Extension Complexity	2017	Thomas Rothvoß	3
+	Consistent Families of Measures and Their Extensions	1962	N. N. Vorob’ëv	3
+ PDF Chat	A Dichotomy Theorem for Nonuniform CSPs	2017	Andreĭ A. Bulatov	3
+	A Course in Abstract Harmonic Analysis	2015	Gerald B. Folland	3
+	An Explicit Exact SDP Relaxation for Nonlinear 0-1 Programs	2001	Jean B. Lasserre	3
+	Graph isomorphism in quasipolynomial time [extended abstract]	2016	László Babai	3
+ PDF Chat	The Power of Sherali--Adams Relaxations for General-Valued CSPs	2017	Johan Thapper Stanislav Živný	3
+ PDF Chat	A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem	2016	Boaz Barak Samuel B. Hopkins Jonathan A. Kelner Pravesh K. Kothari Ankur Moitra Aaron Potechin	3
+ PDF Chat	Communication lower bounds via critical block sensitivity	2014	Mika Göös Toniann Pitassi	3
+ PDF Chat	Efficient algorithms for clique problems	2008	Virginia Vassilevska	3
+	Some intersection theorems for ordered sets and graphs	1986	Fan Chung Ronald Graham Péter Frankl James B. Shearer	3
+	An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle	1995	Jan Krajı́ček Pavel Pudlák Alan R. Woods	3
+	The Monotone Complexity of $k$-Clique on Random Graphs	2014	Benjamin Rossman	3
+ PDF Chat	Hidden variables and the two theorems of John Bell	1993	N. David Mermin	3
+ PDF Chat	Limitations of Algebraic Approaches to Graph Isomorphism Testing	2015	Christoph Berkholz Martin Grohe	3
+	Semidefinite programming and arithmetic circuit evaluation	2007	S. Yu. Tarasov M. Vyalyi	3
+ PDF Chat	Properties of Almost All Graphs and Generalized Quantifiers	2010	Anuj Dawar Erich Grädel	2
+ PDF Chat	Homogenizable relational structures	1990	Jacinta Covington	2
+	A shorter model theory	1997	Wilfrid Hodges	2
+ PDF Chat	Towards an Understanding of Polynomial Calculus: New Separations and Lower Bounds	2013	Yuval Filmus Massimo Lauria Mladen Mikša Jakob Nordström Marc Vinyals	2
+ PDF Chat	On the Quantum Chromatic Number of a Graph	2007	Peter J‎. Cameron Ashley Montanaro Michael Newman Simone Severini Andreas Winter	2
+	Binary Constraint System Games and Locally Commutative Reductions	2013	Zhengfeng Ji	2
+ PDF Chat	Distributing an Exact Algorithm for Maximum Clique: Maximising the Costup	2012	Ciaran McCreesh Patrick Prosser	2
+	Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures	2009	Toniann Pitassi Nathan Segerlind	2
+	On the complexity of H-coloring	1990	Pavol Hell Jaroslav Nešetřil	2