Twisted conjugacy in braid groups

"Vegeu el resum a l'inici del document del fitxer adjunt."

Hankel operators on holomorphic Hardy-Orlicz spaces

"Vegeu el resum a l'inici del document del fitxer adjunt."

Generalized descriptive set theory and classification theory

Descriptive set theory is mainly concerned with studying subsets of the space of all countable binary sequences. In this paper we study the generalization where countable is replaced by uncountable. We explore properties of generalized Baire and Cantor spaces, equivalence relations and their Borel reducibility. The study shows that the descriptive set theory looks very different in this generalized setting compared to the classical, countable case. We also draw the connection between the stability theoretic complexity of first-order theories and the descriptive set theoretic complexity of their isomorphism relations. Our results suggest that Borel reducibility on uncountable structures is a model theoretically natural way to compare the complexity of isomorphism relations.

Potential isomorphism of elementary substructures of a strictly stable homogeneous model

"Vegeu el resum a l'inici del document del fitxer adjunt."

Consistency and optimality

Assume that the problem Qo is not solvable in polynomial time. For theories T containing a sufficiently rich part of true arithmetic we characterize T U {ConT} as the minimal extension of T proving for some algorithm that it decides Qo as fast as any algorithm B with the property that T proves that B decides Qo. Here, ConT claims the consistency of T. Moreover, we characterize problems with an optimal algorithm in terms of arithmetical theories.

Hard instances of algorithms and proof systems

"Vegeu el resum a l'inici del document del fitxer adjunt."

On Borel equivalence relations in generalized Baire space

"Vegeu el resum a l'inici del document del fitxer adjunt."

An approximation algorithm for #k-SAT

"Vegeu el resum a l'inici del document del fitxer adjunt"

The β-Meixner model

We propose to approximate the Meixner model by a member of the B–family introduced in [Kuz10a]. The advantage of such approximations are the semi–explicit formulas for the running extrema under the B–family processes which enables us to produce more efficient algorithms for certain path dependent options.

On the system of the functions x (s) / (s-r)k

"Vegeu el resum a l'inici del document del fitxer adjunt."

Computing hypergraph width measures exactly

Hypergraph width measures are a class of hypergraph invariants important in studying the complexity of constraint satisfaction problems (CSPs). We present a general exact exponential algorithm for a large variety of these measures. A connection between these and tree decompositions is established. This enables us to almost seamlessly adapt the combinatorial and algorithmic results known for tree decompositions of graphs to the case of hypergraphs and obtain fast exact algorithms. As a consequence, we provide algorithms which, given a hypergraph H on n vertices and m hyperedges, compute the generalized hypertree-width of H in time O*(2n) and compute the fractional hypertree-width of H in time O(1.734601n.m).1

A lower bound in Nehari's theorem on the polydisc

"Vegeu el resum a l'inici del document del fitxer adjunt"

Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs

In a seminal paper [10], Weitz gave a deterministic fully polynomial approximation scheme for counting exponentially weighted independent sets (which is the same as approximating the partition function of the hard-core model from statistical physics) in graphs of degree at most d, up to the critical activity for the uniqueness of the Gibbs measure on the innite d-regular tree. ore recently Sly [8] (see also [1]) showed that this is optimal in the sense that if here is an FPRAS for the hard-core partition function on graphs of maximum egree d for activities larger than the critical activity on the innite d-regular ree then NP = RP. In this paper we extend Weitz's approach to derive a deterministic fully polynomial approximation scheme for the partition function of general two-state anti-ferromagnetic spin systems on graphs of maximum degree d, up to the corresponding critical point on the d-regular tree. The main ingredient of our result is a proof that for two-state anti-ferromagnetic spin systems on the d-regular tree, weak spatial mixing implies strong spatial mixing. his in turn uses a message-decay argument which extends a similar approach proposed recently for the hard-core model by Restrepo et al [7] to the case of general two-state anti-ferromagnetic spin systems.