Hard instances of algorithms and proof systems

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

Political Competition in Hard Times

This paper analyzes a spatial model of political competition between two policy- motivated parties in hard times of crisis. Hard times are modeled in terms of policy- making costs carried by a newly elected party. The results predict policy divergence in equilibrium. If the ideological preferences of parties are quite diverse and extreme, there is a unique equilibrium in which the parties announce symmetric platforms and each party wins with probability one half. If one party is extreme while the other is more moderate, there is a unique equilibrium in which the parties announce asymmetric platforms. If the preferred policies of the parties are not very distinct, there are two equilibria with asymmetric platforms. An important property of equilibrium with asymmetric platforms is that a winning party necessarily announces its most preferred policy as a platform. JEL classification: D72. Keywords: Spatial model; Political competition; Two-party system; Policy-motivated parties; Hard times; Crisis.

Sound Texture Modelling

In the PhD thesis “Sound Texture Modeling” we deal with statistical modelling or textural sounds like water, wind, rain, etc. For synthesis and classification. Our initial model is based on a wavelet tree signal decomposition and the modeling of the resulting sequence by means of a parametric probabilistic model, that can be situated within the family of models trainable via expectation maximization (hidden Markov tree model ). Our model is able to capture key characteristics of the source textures (water, rain, fire, applause, crowd chatter ), and faithfully reproduces some of the sound classes. In terms of a more general taxonomy of natural events proposed by Graver, we worked on models for natural event classification and segmentation. While the event labels comprise physical interactions between materials that do not have textural propierties in their enterity, those segmentation models can help in identifying textural portions of an audio recording useful for analysis and resynthesis. Following our work on concatenative synthesis of musical instruments, we have developed a pattern-based synthesis system, that allows to sonically explore a database of units by means of their representation in a perceptual feature space. Concatenative syntyhesis with “molecules” built from sparse atomic representations also allows capture low-level correlations in perceptual audio features, while facilitating the manipulation of textural sounds based on their physical and perceptual properties. We have approached the problem of sound texture modelling for synthesis from different directions, namely a low-level signal-theoretic point of view through a wavelet transform, and a more high-level point of view driven by perceptual audio features in the concatenative synthesis setting. The developed framework provides unified approach to the high-quality resynthesis of natural texture sounds. Our research is embedded within the Metaverse 1 European project (2008-2011), where our models are contributting as low level building blocks within a semi-automated soundscape generation system.

Detection of matchings in a sequence of underwater images through texture analysis

This paper presents an approach to ameliorate the reliability of the correspondence points relating two consecutive images of a sequence. The images are especially difficult to handle, since they have been acquired by a camera looking at the sea floor while carried by an underwater robot. Underwater images are usually difficult to process due to light absorption, changing image radiance and lack of well-defined features. A new approach based on gray-level region matching and selective texture analysis significantly improves the matching reliability

Deriving the hard thermal loops of QCD from classical transport theory

Classical transport theory is employed to analyze the hot quark-gluon plasma at the leading order in the coupling constant. A condition on the (covariantly conserved) color current is obtained. From this condition, the generating functional of hard thermal loops with an arbitrary number of soft external bosonic legs can be derived. Our approach, besides being more direct than alternative ones, shows that hard thermal loops are essentially classical.

Energy and structure of dilute hard- and soft-sphere gases

The energy and structure of dilute hard- and soft-sphere Bose gases are systematically studied in the framework of several many-body approaches, such as the variational correlated theory, the Bogoliubov model, and the uniform limit approximation, valid in the weak-interaction regime. When possible, the results are compared with the exact diffusion Monte Carlo ones. Jastrow-type correlation provides a good description of the systems, both hard- and soft-spheres, if the hypernetted chain energy functional is freely minimized and the resulting Euler equation is solved. The study of the soft-sphere potentials confirms the appearance of a dependence of the energy on the shape of the potential at gas paremeter values of x~0.001. For quantities other than the energy, such as the radial distribution functions and the momentum distributions, the dependence appears at any value of x. The occurrence of a maximum in the radial distribution function, in the momentum distribution, and in the excitation spectrum is a natural effect of the correlations when x increases. The asymptotic behaviors of the functions characterizing the structure of the systems are also investigated. The uniform limit approach is very easy to implement and provides a good description of the soft-sphere gas. Its reliability improves when the interaction weakens.

Ground-state properties of a dilute homogeneous Bose gas of hard disks in two dimensions

The energy and structure of a dilute hard-disks Bose gas are studied in the framework of a variational many-body approach based on a Jastrow correlated ground-state wave function. The asymptotic behaviors of the radial distribution function and the one-body density matrix are analyzed after solving the Euler equation obtained by a free minimization of the hypernetted chain energy functional. Our results show important deviations from those of the available low density expansions, already at gas parameter values x~0.001 . The condensate fraction in 2D is also computed and found generally lower than the 3D one at the same x.

Influence of the dipolar interactions in the magnetization reversal asymmetry of hard-soft magnetic ribbons

Partial crystallization of the metallic glass Co66Si16B12Fe4Mo2 was performed by annealing at temperatures between 500 and 540°C for 10-20 min, resulting in crystallite volume fractions of (0.7-5)×10¿3 and sizes of 50-100 nm. This two-phase alloy presents a remarkable feature: a hysteresis loop shift that can be tailored by simply premagnetizing the sample in the adequate magnetic field. Shifts as large as five times the coercive field have been obtained which make them interesting for application as magnetic cores in dc pulse transformers. The asymetrical magnetic reversal is explained in terms of the magnetic dipolar field interaction and the observed hysteresis loops have been satisfactorily simulated by a modification of Stoner-Wohlfarth¿s model of coherent rotations.

Local size segregation in polydisperse hard sphere fluids

The structure of polydisperse hard sphere fluids, in the presence of a wall, is studied by the Rosenfeld density functional theory. Within this approach, the local excess free energy depends on only four combinations of the full set of density fields. The case of continuous polydispersity thereby becomes tractable. We predict, generically, an oscillatory size segregation close to the wall, and connect this, by a perturbation theory for narrow distributions, with the reversible work for changing the size of one particle in a monodisperse reference fluid.

Metal complexation by electroanalytical techniques: hard- and soft-modelling approaches

En la investigació de la complexació de metalls mitjançant eines electroanalítiques són emprades dues aproximacions generals. La primera, anomenada de modelatge dur (hardmodelling), es basa en la formulació d'un model fisicoquímic conjunt per als processos electròdic i de complexació i en la resolució analítica o numèrica del model. Posteriorment, l'ajust dels paràmetres del model a les dades experimentals donarà la informació desitjada sobre el procés de complexació. La segona aproximació, anomenada de modelatge tou (soft-modelling), es basa en la identificació d'un model de complexació a partir de l'anàlisi numèrica i estadística de les dades, sense cap assumpció prèvia d'un model. Aquesta aproximació, que ha estat extensivament emprada amb dades espectroscòpiques, ho ha estat poquíssim amb dades electroquímiques. En aquest article tractem de la formulació d'un model (hard-modelling) per a la complexació de metalls en sistemes amb mescles de lligands, incloent-hi lligands macromoleculars, i de l'aplicació d

Analysis of sensitivity with respect to a compositional parameter : A comment on 'Local sensitivity analysis for compositional data with application to soil texture in hydrologic modelling' by L. Loosvelt and co-authors

A comment about the article “Local sensitivity analysis for compositional data with application to soil texture in hydrologic modelling” writen by L. Loosvelt and co-authors. The present comment is centered in three specific points. The first one is related to the fact that the authors avoid the use of ilr-coordinates. The second one refers to some generalization of sensitivity analysis when input parameters are compositional. The third tries to show that the role of the Dirichlet distribution in the sensitivity analysis is irrelevant

Generating highly balanced sudoku problems as hard problems

Sudoku problems are some of the most known and enjoyed pastimes, with a never diminishing popularity, but, for the last few years those problems have gone from an entertainment to an interesting research area, a twofold interesting area, in fact. On the one side Sudoku problems, being a variant of Gerechte Designs and Latin Squares, are being actively used for experimental design, as in [8, 44, 39, 9]. On the other hand, Sudoku problems, as simple as they seem, are really hard structured combinatorial search problems, and thanks to their characteristics and behavior, they can be used as benchmark problems for refining and testing solving algorithms and approaches. Also, thanks to their high inner structure, their study can contribute more than studies of random problems to our goal of solving real-world problems and applications and understanding problem characteristics that make them hard to solve. In this work we use two techniques for solving and modeling Sudoku problems, namely, Constraint Satisfaction Problem (CSP) and Satisfiability Problem (SAT) approaches. To this effect we define the Generalized Sudoku Problem (GSP), where regions can be of rectangular shape, problems can be of any order, and solution existence is not guaranteed. With respect to the worst-case complexity, we prove that GSP with block regions of m rows and n columns with m = n is NP-complete. For studying the empirical hardness of GSP, we define a series of instance generators, that differ in the balancing level they guarantee between the constraints of the problem, by finely controlling how the holes are distributed in the cells of the GSP. Experimentally, we show that the more balanced are the constraints, the higher the complexity of solving the GSP instances, and that GSP is harder than the Quasigroup Completion Problem (QCP), a problem generalized by GSP. Finally, we provide a study of the correlation between backbone variables – variables with the same value in all the solutions of an instance– and hardness of GSP.

Generating hard SAT/CSP instances using expander graphs

In this paper we provide a new method to generate hard k-SAT instances. We incrementally construct a high girth bipartite incidence graph of the k-SAT instance. Having high girth assures high expansion for the graph, and high expansion implies high resolution width. We have extended this approach to generate hard n-ary CSP instances and we have also adapted this idea to increase the expansion of the system of linear equations used to generate XORSAT instances, being able to produce harder satisfiable instances than former generators.

How hard is a commercial puzzle: the eternity II challenge

Recently, edge matching puzzles, an NP-complete problem, have received, thanks to money-prized contests, considerable attention from wide audiences. We consider these competitions not only a challenge for SAT/CSP solving techniques but also as an opportunity to showcase the advances in the SAT/CSP community to a general audience. This paper studies the NP-complete problem of edge matching puzzles focusing on providing generation models of problem instances of variable hardness and on its resolution through the application of SAT and CSP techniques. From the generation side, we also identify the phase transition phenomena for each model. As solving methods, we employ both; SAT solvers through the translation to a SAT formula, and two ad-hoc CSP solvers we have developed, with different levels of consistency, employing several generic and specialized heuristics. Finally, we conducted an extensive experimental investigation to identify the hardest generation models and the best performing solving techniques.