• Publications
• Influence
The complexity of surjective homomorphism problems - a survey
• Mathematics, Computer Science
• Discret. Appl. Math.
• 27 April 2011
Surjective homomorphism problems seem to be harder to classify and this work examines especially three concrete problems that have arisen from the literature, two of whose complexity remains open. Expand
Parameterized Proof Complexity
• Mathematics, Computer Science
• computational complexity
• 1 March 2011
A dichotomy theorem is established that splits the exponential case of Riis’s complexity gap theorem into two subcases, one that admits proofs of size f(k)nO(1) and one that does not and how the set of parameterized contradictions may be embedded into theSet of (ordinary) contradictions by the addition of new axioms. Expand
Tight rank lower bounds for the Sherali-Adams proof system
• Mathematics, Computer Science
• Theor. Comput. Sci.
• 1 May 2009
It is proved that the SA rank of both the Pigeonhole Principle PHP"n"-"1^n and the Least Number Principle LNP"n is n-2 and the SA size of F is @?(k+1)s+1. Expand
On the Scope of the Universal-Algebraic Approach to Constraint Satisfaction
• Computer Science
• LICS
• 11 July 2010
It is proved that every CSP can be formulated with a template A such that a relation is primitive positive definable in A if and only if it is first-order definable on A and preserved by the infinitary polymorphisms of A. Expand
Parameterized Proof Complexity
• Mathematics, Computer Science
• 48th Annual IEEE Symposium on Foundations of…
• 21 October 2007
A dichotomy theorem is established that splits the exponential case of Riis's complexity-gap Theorem into two sub-cases, one that admits proofs of size f(k)nO(1) and one that does not, and how the set of parameterized contradictions may be embedded into theSet of (ordinary) contradictions by the addition of new axioms. Expand
The Computational Complexity of Disconnected Cut and 2K 2-Partition
• Mathematics, Computer Science
• CP
• 12 September 2011
It is shown that the problem to test whether a graph has a disconnected cut is NP-complete, which settles an open problem frequently posed in each of the four settings. Expand
The Complexity of Positive First-order Logic without Equality
• Mathematics, Computer Science
• 24th Annual IEEE Symposium on Logic In Computer…
• 3 March 2010
This work introduces surjective hyper-endomorphisms and uses them in proving a Galois connection that characterises definability in positive equality-free FO. Expand
Towards a Trichotomy for Quantified H-Coloring
• Mathematics, Computer Science
• CiE
• 30 June 2006
The complexity of the quantified H-colouring problem is investigated using a new two player colouring game and it is conjecture that the last case extends to all non-bipartite connected graphs. Expand
The computational complexity of disconnected cut and 2K2-partition
• Mathematics, Computer Science
• J. Comb. Theory, Ser. B
• 25 April 2011
It is shown that the problem to test whether a graph has a disconnected cut is NP-complete, which settles an open problem frequently posed in each of the four settings. Expand
Constraint satisfaction problems for reducts of homogeneous graphs
• Computer Science, Mathematics
• ICALP
• 18 February 2016
It is shown that for all structures with domain H_n whose relations are first-order definable in \$(H_n,E)\$ the constraint satisfaction problem for \$\Gamma\$ is either in P or is NP-complete, which completes the complexity classification of constraint satisfaction problems of structures first- order definability in countably infinite homogeneous graphs. Expand
{"ft_lang_label":"__label__en","ft_lang_prob":0.66070276,"math_prob":0.7866421,"size":1881,"snap":"2021-31-2021-39","text_gpt3_token_len":554,"char_repetition_ratio":0.17900905,"word_repetition_ratio":0.15,"special_character_ratio":0.2599681,"punctuation_ratio":0.1969697,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9926094,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-07-27T03:45:02Z\",\"WARC-Record-ID\":\"<urn:uuid:72e9ee99-3b73-4e84-bdfa-e196fd7db0f1>\",\"Content-Length\":\"524107\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:ae875534-9520-4704-bf05-e8f991744b8c>\",\"WARC-Concurrent-To\":\"<urn:uuid:d78d6f54-8a89-4eaf-a16a-ee5efccc6ad8>\",\"WARC-IP-Address\":\"13.32.199.28\",\"WARC-Target-URI\":\"https://www.semanticscholar.org/author/B.-Martin/35202653\",\"WARC-Payload-Digest\":\"sha1:4OIS6HSZXJXNGHP4CXRSJKS34JK5PTSV\",\"WARC-Block-Digest\":\"sha1:PMOUIKBCER25ILFVR6SXQEY2KHKZY5GZ\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-31/CC-MAIN-2021-31_segments_1627046152168.38_warc_CC-MAIN-20210727010203-20210727040203-00025.warc.gz\"}"}