Sherali-Adams Relaxations and Indistinguishability in Counting Logics

Two graphs with adjacency matrices $\mathbf{A}$ and $\mathbf{B}$ are isomorphic if there exists a permutation matrix $\mathbf{P}$ for which the identity $\mathbf{P}^{\mathrm{T}} \mathbf{A} \mathbf{P} = \mathbf{B}$ holds. Multiplying through by $\mathbf{P}$ and relaxing the permutation matrix to a doubly stochastic matrix leads to the linear programming relaxation known as fractional isomorphism. We show that the levels of the Sherali--Adams (SA) hierarchy of linear programming relaxations applied to fractional isomorphism interleave in power with the levels of a well-known color-refinement heuristic for graph isomorphism called the Weisfeiler--Lehman algorithm, or, equivalently, with the levels of indistinguishability in a logic with counting quantifiers and a bounded number of variables. This tight connection has quite striking consequences. For example, it follows immediately from a deep result of Grohe in the context of logics with counting quantifiers that a fixed number of levels of SA suffice to determine isomorphism of planar and minor-free graphs. We also offer applications in both finite model theory and polyhedral combinatorics. First, we show that certain properties of graphs, such as that of having a flow circulation of a prescribed value, are definable in the infinitary logic with counting with a bounded number of variables. Second, we exploit a lower bound construction due to Cai, Fürer, and Immerman in the context of counting logics to give simple explicit instances that show that the SA relaxations of the vertex-cover and cut polytopes do not reach their integer hulls for up to $\Omega(n)$ levels, where $n$ is the number of vertices in the graph.

La teoria del codis. Una entrevista a Basil Berstein

En el context d'aquesta monografia dedicada a l'obra del professor Bernstein ens va semblar oportú de comptar amb alguna aportació original de l'autor. Estant a punt de publicar-se la seva obra clàssica principal (ja apareguda quan s'editi aquest número de Temps d'educació ), va sorgir la idea d'una entrevista- una entrevista, en aquest cas, 'epistolar'.

Dinámica no lineal en la motivación en el trabajo: propuesta de un modelo y resultados preliminares

Muchos especialistas estarían de acuerdo en que la motivación en el trabajo debe entenderse como un proceso dinámico. Sin embargo, son pocas las investigaciones que se han interesado por la descripción y explicación de dicha dinámica motivacional. Este artículo propone un modelo complejo de motivación en el trabajo que integra tres variables clásicas en la literatura: motivos, autoeficacia e instrumentalidad. El modelo incorpora los cambios que se producen en la motivación a lo largo del tiempo como consecuencia de la retroalimentación producida por la variable ejecución (evaluada con un indicador de compromiso). En una muestra de 271 personas se establecen las relaciones que configuran el modelo y, utilizando la simulación informática, se demuestra que la dinámica del modelo es estable sólo cuando los motivos de la persona cambian de manera caótica. Este fenómeno tiene una serie de consecuencias, tanto para la investigación como para la gestión, que son ampliamente discutidas.

La relació teoria-pràctica en la pedagogia de Paulo Freire

Em costaria iniciar aquest discurs de presentació de Paulo Freire, a qui la Universitat de Barcelona té avui el goig de retre homenatge investint-lo Doctor Honoris Causa, sense fer prèviament tres coses. En primer lloc, agrair molt sincerament l'encàrrec que se m'ha fet de dirigir-vos aquestes paraules. En segon lloc, referir-me a un deis significats d'aquest acte. Paulo Freire serà el primer Doctor Honoris Causa de la Universitat de Barcelona proposat per la recentment creada Facultat de Pedagogia i per la Divisió de Ciències de l'Educació amb el suport de l'Escola de Formació del Professorat d'EGB i de l'ICE. Amb una unanimitat total, els centres d'aquesta universitat que tenen com a objecte específic la formació d'educadors i la recerca pedagògica han volgut honorar-se incorporant a la seva comunitat qui és avui, probablement, el pedagog viu més universalment conegut i reconegut.

Implantació d'un sistema integrat : ERP, web i CRM a un distribuïdor d'informàtica

Aquest treball de final de grau tracta de donar una solució basada en sistemes d'informació a un distribuïdor d'informàtica anomenat DistriTiC, que ha perdut competitivitat i clients en els darrers anys. A través d'un anàlisi inicial de la situació de l'empresa i dels requeriments organitzatius de la direcció, hem realitzat un pla estratègic de renovació de sistemes d'informació estudiant les quatre etapes del cicle de vida i els seus processos transversals.

Spectral properties of the Laplacian of multiplex networks.

One of the more challenging tasks in the understanding of dynamical properties of models on top of complex networks is to capture the precise role of multiplex topologies. In a recent paper, Gómez et al. [ Phys. Rev. Lett. 110 028701 (2013)], some of the authors proposed a framework for the study of diffusion processes in such networks. Here, we extend the previous framework to deal with general configurations in several layers of networks and analyze the behavior of the spectrum of the Laplacian of the full multiplex. We derive an interesting decoupling of the problem that allow us to unravel the role played by the interconnections of the multiplex in the dynamical processes on top of them. Capitalizing on this decoupling we perform an asymptotic analysis that allow us to derive analytical expressions for the full spectrum of eigenvalues. This spectrum is used to gain insight into physical phenomena on top of multiplex, specifically, diffusion processes and synchronizability.

Strategisen laskentatoimen teoria ja käytäntö - Kyselytutkimus suomalaisyrityksistä

Tutkimus on jaettu kahteen osa-alueeseen. Ensimmäisessä osiossa kuvataan strategisen laskentatoimen ja perinteisen strategiatyön välistä yhteyttä teoreettisesta näkökulmasta ja osoitetaan strategisen laskentatoimen hyödynnettävyys yritysjohdon apuna strategiaprosessin eri vaiheissa ja strategisen asemoinnin apuvälineenä. Teoriaosan lopuksi esitetään ehdotus strategisen laskentatoimen viitekehykseksi. Toisessa osiossa tutkitaan kyselytutkimuksen avulla suomaisyritysten strategisen laskentatoimen menetelmien käyttöastetta ja menetelmien uskottua hyödyllisyyttä. Tutkimustuloksia verrataan lisäksi aiemmin tehtyyn tutkimukseen muiden maiden vastaavista tuloksista. Tutkimuksesta käy ilmi suomalaisten yritysten suosivan samoja menetelmiä kuin muissakin maissa ja niin suomalaisyritysten kuin myös muiden maiden uskovan kaikkien menetelmien olevan hyödyllisempiä kuin mitä niitä yrityksissä käytetään.

Debilitat de la teoria de l'educació: sobre la narrativitat científica de l'educació

En aquest assaig es revisen les aportacions que el professor Antoni J. Colom ha fet a la teoria de l'educació en els últims anys. Es dibuixa, per tant, un itinerari que es troba representat per diferents moments: debilitat constitutiva de la teoria de l'educació; crisi del model de la física newtoniana; construcció científica de l'educació a partir e la biologia i del mètode experimental, fins arribar a la teoria del caos que així constitueix una nova narrativa científica per a la pedagogia. Es tracta, en definitiva, d'una proposta alternativa que a la dècada dels anys noranta va sorgir amb força als Estats Units i que vol superar la visió lineal i simple del fenòmen educatiu com una mera relació de causa-efecte. En el seu lloc, es proposa una nova narrativa basada en la complexitat de la teoria que així pot servir per explicar la teoria i la pràctica educatives, bo i establint alts nivells de coherència entre ambdós estadis -el teòric i el pràctic- perquè, en darrer terme, la narrativa educativa ha de ser sempre coherent amb l'educació narrada.

Aplicación informática al estudio del territorio en época antigua: Centuriaciones Romanas

Presentamos una aplicación informática realizada en GW-BASIC para el estudio de las centuriaciones romanas, que facilita la determinación de orientaciones y módulos de centuria, así como la definición de la retícula teórica para su posterior contrastación y evaluación.

Carola Milà i la felicitat de ser una dona : La teoria feminista de Maria Aurèlia Capmany en 'Feliçment, jo sóc una dona'

Aquest treball presenta una anàlisi textual de l'obra de Maria Aurèlia Capmany 'Feliçment, jo sóc una dona'. D'una banda, a través d'una breu presentació de l'autora fins al moment de la publicació de l'obra i, d'una altra, d'una síntesi del feminisme a Catalunya, l'autora del treball ens apropa a les teories feministes que Capmany aboca en la seva novel·la, fet que representa un punt d'inflació en la seva trajectòria novel·lística. L'anàlisi textual ens permet apropar-nos al concepte d'identitat femenina i a la seva construcció, així com relacionar-lo amb les teories feministes més recents.