Runtime Analysis of Randomized Search Heuristics for Dynamic Graph Coloring - Bossek, Jakob; Neumann, Frank; Peng, Pan; Sudholt, Dirk (Proceedings of the Genetic and Evolutionary Computation Conference)
We contribute to the theoretical understanding of randomized search heuristics for dynamic problems. We consider the classical graph coloring problem and investigate the dynamic setting where edges are added to the current graph. We then analyze the expected time for randomized search heuristics to recompute high quality solutions. This includes the (1+1) EA and RLS in a setting where the number of colors is bounded and we are minimizing the number of conflicts as well as iterated local search algorithms that use an unbounded color palette and aim to use the smallest colors and - as a consequence - the smallest number of colors. We identify classes of bipartite graphs where reoptimization is as hard as or even harder than optimization from scratch, i. e. starting with a random initialization. Even adding a single edge can lead to hard symmetry problems. However, graph classes that are hard for one algorithm turn out to be easy for others. In most cases our bounds show that reoptimization is faster than optimizing from scratch. Furthermore, we show how to speed up computations by using problem specific operators concentrating on parts of the graph where changes have occurred.
Keywords: dynamic optimization; evolutionary algorithms; running time analysis; theory

Work in the Age of Intelligent Machines: The Rise of Invisible Automation - Klowait, Nils; Erofeeva, Maria (Philosophical Literary Journal Logos)
The article analyzes how an emerging form of automation may drastically transform contemporary employment dynamics. Recent breakthroughs in the field of artificial intelligence (AI) make it possible to automate both manual and mental non-standard tasks. The first part of the article traces the development of AI. Whereas classical algorithms required the creation of a hermetic environment for AI to thrive, modern neural network-based AI is capable of surviving in the chaotic realm occupied by humans. Based on an analysis of changes in the nature of AI, the authors distinguish between substitutive and supplemental automation. The former refers to a complete replacement of humans by machines, while the latter indicates a selective substitution of humans in specific professional functions. In order to conceptualize professions as a nexus of automatable components, the authors employ Goffman’s dramaturgical framework. Goffman studied the social visibility of professional activity. Goffman held that any profession can be divided into invisible routines that are fundamental to it and a dramatization that makes the profession socially visible. The article demonstrates that the current utopian and antiutopian views of automation both reduce work to its visible components and neglect the logic of supplemental automation. The authors argue that the targets of modern automation are not the socially visible components but the invisible routines. In the final section, the authors develop a model that takes these invisible professional routines into account and analyze what effect this new type of automation may have on different types of professions with differing degrees of social visibility.
Keywords: Literature and Literary Theory; Philosophy; Cultural Studies

Paying for Performance in Private Equity: Evidence from Venture Capital Partnerships - Hüther, Niklas; Robinson, David T.; Sievers, Sönke; Hartmann-Wendels, Thomas (Management Science (VHB-JOURQUAL 4 Ranking A+))
We offer the first empirical analysis connecting the timing of general partner (GP) compensation to private equity fund performance. Using detailed information on limited partnership agreements between private equity limited and general partners, we find that “GP-friendly” contracts—agreements that pay general partners on a deal-by-deal basis instead of withholding carried interest until a benchmark return has been earned—are associated with higher returns, both gross and net of fees. This is robust to measures of performance persistence, time period effects, and other contract terms and is related to exit-timing incentives. Timing practices balance GP incentives against limited partner downside protection.
Keywords: venture capital; compensation; private equity; VC partnership; pay-performance relation

Triadic relationships in the context of services for animal companions - Rötzmeier-Keuper, Julia; Hendricks, Jennifer; Wünderlich, Nancy; Schmitz, Gertrud (Journal of Business Research)
Triadic service relationships comprise complex relationships in which not only the customer and provider are involved as partners but also other individuals with caregiving relationships with the customer. A triadic constellation may arise in the context of services for animal companions, for example, when veterinarians provide counsel and treatment to the animal companion and its owner. Through interviews with both owners of animal companions and providers of services for animal companions, this study explores typical constellations and characteristics of the three relationships in this service triad. In line with balance theory, the results show that four distinct types of triadic relationships exist in services for animal companions: the harmonious, the dysfunctional, the challenging, and the doubtful triad. The study highlights the potential conflicts and dynamics in the triads to advise providers on how to address customers depending on the types of triads to which they belong.
Keywords: Triadic relationships; Balance theory; Pet-related services; Animal companions; Service relationship typology; Service triads

Quantum Generalizations of the Polynomial Hierarchy with Applications to QMA(2) - Gharibian, Sevag; Santha, Miklos; Sikora, Jamie; Sundaram, Aarthi; Yirka, Justin (43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018))
The polynomial-time hierarchy (PH) has proven to be a powerful tool for providing separations in computational complexity theory (modulo standard conjectures such as PH does not collapse). Here, we study whether two quantum generalizations of PH can similarly prove separations in the quantum setting. The first generalization, QCPH, uses classical proofs, and the second, QPH, uses quantum proofs. For the former, we show quantum variants of the Karp-Lipton theorem and Toda's theorem. For the latter, we place its third level, Q Sigma_3, into NEXP using the Ellipsoid Method for efficiently solving semidefinite programs. These results yield two implications for QMA(2), the variant of Quantum Merlin-Arthur (QMA) with two unentangled proofs, a complexity class whose characterization has proven difficult. First, if QCPH=QPH (i.e., alternating quantifiers are sufficiently powerful so as to make classical and quantum proofs "equivalent"), then QMA(2) is in the Counting Hierarchy (specifically, in P^{PP^{PP}}). Second, unless QMA(2)= Q Sigma_3 (i.e., alternating quantifiers do not help in the presence of "unentanglement"), QMA(2) is strictly contained in NEXP.
Keywords: Complexity Theory; Quantum Computing; Polynomial Hierarchy; Semidefinite Programming; QMA(2); Quantum Complexity

The Complexity of Simulating Local Measurements on Quantum Systems - Gharibian, Sevag; Yirka, Justin (12th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2017))
An important task in quantum physics is the estimation of local quantities for ground states of local Hamiltonians. Recently, Ambainis defined the complexity class P^QMA[log], and motivated its study by showing that the physical task of estimating the expectation value of a local observable against the ground state of a local Hamiltonian is P^QMA[log]-complete. In this paper, we continue the study of P^QMA[log], obtaining the following results. The P^QMA[log]-completeness result of Ambainis requires O(log n)-local observ- ables and Hamiltonians. We show that simulating even a single qubit measurement on ground states of 5-local Hamiltonians is P^QMA[log]-complete, resolving an open question of Ambainis. We formalize the complexity theoretic study of estimating two-point correlation functions against ground states, and show that this task is similarly P^QMA[log]-complete. P^QMA[log] is thought of as "slightly harder" than QMA. We justify this formally by exploiting the hierarchical voting technique of Beigel, Hemachandra, and Wechsung to show P^QMA[log] \subseteq PP. This improves the containment QMA \subseteq PP from Kitaev and Watrous. A central theme of this work is the subtlety involved in the study of oracle classes in which the oracle solves a promise problem. In this vein, we identify a flaw in Ambainis' prior work regarding a P^UQMA[log]-hardness proof for estimating spectral gaps of local Hamiltonians. By introducing a "query validation" technique, we build on his prior work to obtain P^UQMA[log]-hardness for estimating spectral gaps under polynomial-time Turing reductions.
Keywords: Complexity theory; Quantum Merlin Arthur (QMA); local Hamiltonian; local measurement; spectral gap

Computing subfields of number fields and applications to Galois group computations - Elsenhans, Andreas-Stephan; Klüners, Jürgen (Journal of Symbolic Computation)
A polynomial time algorithm to find generators of the lattice of all subfields of a given number field was given in van Hoeij et al. (2013). This article reports on a massive speedup of this algorithm. This is primary achieved by our new concept of Galois-generating subfields. In general this is a very small set of subfields that determine all other subfields in a group-theoretic way. We compute them by targeted calls to the method from van Hoeij et al. (2013). For an early termination of these calls, we give a list of criteria that imply that further calls will not result in additional subfields. Finally, we explain how we use subfields to get a good starting group for the computation of Galois groups.
Keywords: Computational Mathematics; Algebra and Number Theory

One-class genera of exceptional groups over number fields - Kirschmer, Markus (Journal de Théorie des Nombres de Bordeaux)
We show that exceptional algebraic groups over number fields do not admit one-class genera of parahoric groups, except in the case G₂ . For the group G₂, we enumerate all such one-class genera for the usual seven-dimensional representation.
Keywords: Algebra and Number Theory

Hamiltonian boundary value problems, conformal symplectic symmetries, and conjugate loci - McLachlan, Robert I; Offen, Christian (New Zealand Journal of Mathematics)
In this paper we continue our study of bifurcations of solutions of boundary-value problems for symplectic maps arising as Hamiltonian diffeomorphisms. These have been shown to be connected to catastrophe theory via generating functions and ordinary and reversal phase space symmetries have been considered. Here we present a convenient, coordinate free framework to analyse separated Lagrangian boundary value problems which include classical Dirichlet, Neumann and Robin boundary value problems. The framework is then used to prove the existence of obstructions arising from conformal symplectic symmetries on the bifurcation behaviour of solutions to Hamiltonian boundary value problems. Under non-degeneracy conditions, a group action by conformal symplectic symmetries has the effect that the flow map cannot degenerate in a direction which is tangential to the action. This imposes restrictions on which singularities can occur in boundary value problems. Our results generalise classical results about conjugate loci on Riemannian manifolds to a large class of Hamiltonian boundary value problems with, for example, scaling symmetries.
Keywords: Hamiltonian boundary value problems; singularities; conformal symplectic geometry; catastrophe theory; conjugate loci

Wie kommen die Dinge in den Musikunterricht? Zur Materialität musikpädagogischer Praxis am Beispiel divergierender Orientierungen im Kontext unterrichtsbezogenen Handelns angehender Lehrkräfte - Godau, Marc (Soziale Aspekte des Musiklernens)
During the past decade, there has been an increase of pedagogical research under conditions of posthuman theories, such as the Actor Network Theory or post-phenomenology. Yet, there has not been much research on the materiality of music pedagogical practices. This article introduces an ongoing grounded-theory study on the role of things (e.g., music instruments, black board, or digital devices) within the music classroom. Results from the analysis of group discussions and interviews with student teachers show tensions between personal preferences, school conventions, and material conventions within the process of introducing things into the classroom. (DIPF/Orig.)
Keywords: Interview; Lehrer; Musical education; Musikpädagogik; Musikunterricht; Teacher; Music lessons; Qualitative Forschung; Qualitative research; Teaching of music; Object; Objekt; Ding; Handlung; Practice; Praxis; Probationary teacher training; Referendariat

Paying for Performance in Private Equity: Evidence from VC Partnerships - Hüther, Niklas; Robinson, David; Sievers, Sönke; Hartmann-Wendels, Thomas (SSRN Electronic Journal)
We offer the first empirical analysis connecting the timing of general partner (GP) compensation to private equity fund performance. Using detailed information on limited partnership agreements between private equity limited and general partners, we find that "GP-friendly" contracts - agreements that pay general partners on a deal-by-deal basis instead of withholding carried interest until a benchmark return has been earned - are associated with higher returns, both gross and net of fees. This is robust to measures of performance persistence, time period effects, and other contract terms, and is related to exit-timing incentives. Timing practices balance GP incentives against limited partner downside protection.
Keywords: venture capital; compensation; private equity; VC partnership; pay-performance relation

Efficient PAW-based bond strength analysis for understanding the In/Si(111)(8 × 2) – (4 × 1) phase transition - Lücke, Andreas; Gerstmann, Uwe; Kühne, Thomas D.; Schmidt, Wolf G. (Journal of Computational Chemistry)
A numerically efficient yet highly accurate implementation of the crystal orbital Hamilton population (COHP) scheme for plane-wave calculations is presented. It is based on the projector-augmented wave (PAW) formalism in combination with norm-conserving pseudopotentials and allows to extract chemical interactions between atoms from band-structure calculations even for large and complex systems. The potential of the present COHP implementation is demonstrated by an in-depth analysis of the intensively investigated metal-insulator transition in atomic-scale indium wires self-assembled on the Si(111) surface. Thereby bond formation between In atoms of adjacent zigzag chains is found to be instrumental for the phase change. © 2017 Wiley Periodicals, Inc.
Keywords: density functional theory; bonding; crystal orbital Hamilton population; indium nanowires; phase transition

Measuring and modeling salience with the theory of visual attention. - Krüger, Alexander; Tünnermann, Jan; Scharlau, Ingrid (Attention, Perception, & Psychophysics)
For almost three decades, the theory of visual attention (TVA) has been successful in mathematically describing and explaining a wide variety of phenomena in visual selection and recognition with high quantitative precision. Interestingly, the influence of feature contrast on attention has been included in TVA only recently, although it has been extensively studied outside the TVA framework. The present approach further develops this extension of TVA’s scope by measuring and modeling salience. An empirical measure of salience is achieved by linking different (orientation and luminance) contrasts to a TVA parameter. In the modeling part, the function relating feature contrasts to salience is described mathematically and tested against alternatives by Bayesian model comparison. This model comparison reveals that the power function is an appropriate model of salience growth in the dimensions of orientation and luminance contrast. Furthermore, if contrasts from the two dimensions are comb
Keywords: Salience; Visual attention; Bayesian inference; Theory of visual attention; Computational modeling; Inference; Object Recognition; Theories; Visual Perception; Visual Attention; Luminance; Perceptual Orientation; Statistical Probability; Stimulus Salience; Computational Modeling

The constructive membership problem for discrete two-generator subgroups of SL(2,R) - Kirschmer, Markus; Rüther, Marion G. (Journal of Algebra)
We describe a practical algorithm to solve the constructive membership problem for discrete two-generator subgroups of SL₂(R) or PSL₂(R). This algorithm has been implemented in Magma for groups defined over real algebraic number fields.
Keywords: Algebra and Number Theory

Shoulda, Coulda, Woulda – Non-Canonical Forms on the Move? - Freudinger, Markus (Zeitschrift für Anglistik und Amerikanistik)
Abstract In this paper, the contractions shoulda, coulda, woulda are compared with their respective full forms should have , would have , and could have . Although the full forms are used much more frequently and are, therefore, considered canonical, the non-canonical forms have increased in frequency throughout the better part of the twentieth century. They are predominantly used in American English – in conversation as well as in fictional writing to imitate speech. With respect to their syntactic environment, shoulda, coulda , and woulda behave differently than their full counterparts since they are often used without subjects and without lexical verbs. Some of these uses can be explained by the fact that shoulda, coulda , and woulda are not always used as verbal items but also as nouns, adjectives, and interjections. Due to their overall low frequency and their restriction to a particular register, however, it appears they will keep their non-canonical status for the foreseeable future.
Keywords: Literature and Literary Theory; Linguistics and Language; Language and Linguistics

The interplay between subjective abilities and subjective demands and its relationship with academic success. An application of the person–environment fit theory - Bohndick, Carla; Rosman, Tom; Kohlmeyer, Susanne; Buhl, Heike M. (Higher Education)
In this study, we draw on person–environment fit theory to analyze whether academic success is best explained by individual abilities subjectively exceeding situational demands or by abilities matching the demands. Moreover, we disentangled effects of perceived abilities and subjective person–environment (P-E) fit on academic success. All in all, 693 teacher education students participated in an online questionnaire. Students were asked to rate general requirements of their academic programs (e.g., self-discipline) on a 5-point scale in terms of (1) their own abilities and (2) the perceived relevance for their studies. P-E fit was determined by difference scores between abilities and relevance ratings. Academic success was assessed by grades, perceived performance, and study satisfaction. Data were analyzed through structural equation modeling and suggest that academic success is best explained by a match between abilities and demands. Moreover, all three criteria for academic success were more strongly related to subjective fit than to subjective abilities.
Keywords: Academic success; Person–environment fit theory; Demands–abilities fit; Higher education

Reflections on Context in Service Research. - Voss, Chris; Perks, Helen; Sousa, Rui; Witell, Lars; Wünderlich, Nancy (Journal of Service Management)
Purpose – The purpose of this paper is to examine the nature of context and its implications for theory and research in service. Design/methodology/approach – This is a conceptual paper based on exploring existing research and theory related to context in service research. Findings – The characteristics of service make context both important and challenging, there is great contextual diversity in service research as reflected, for example in ecosystems made up of multiple contextual variables. There is a need to identify the context-specific nature of middle range theory and the contextual logic of general theory. The authors explore the challenges of context for service theory and how we might learn from theory in a particular context and test or adapt it in other contexts. Originality/value – The findings of this paper are of value to researchers seeking to develop and justify theory in service research (general, middle range or theory in use).
Keywords: Research; Service theory

An Economic Theory of 'Destabilization War' - Gries, Thomas; Haake, Claus-Jochen
While Islamic State is the most present example, it is a fact that in many places around the globe, throughout history initially small groups have tried to challenge and destabilize or even overthrow governments by means of terrorist and guerrilla strategies. Therefore, we answer two questions. Why does a small group of insurgents believe it can overthrow the government by turning violent, even if the government is clearly superior? And how does a conflict develop into terrorism, a guerilla war, or a major conventional civil war, or is resolved peacefully? We develop a formal model for rebels and government and derive optimal choices. Further, we focus on three elements as important ingredients of a "destabilization war". All three of these - large random events, time preference (which we relate to ideology), and choice of duration of fight - are rarely considered in formal conflict theory. We can answer the above two questions using game theory analysis. First, insurgents rise up because they hope to destabilize through permanent challenging attacks. In this context, large randomness is an important ally of rebels. While each individual attack may have a low impact, at some point a large random event could lead to success. Hence, the duration of activities is a constitutive element of this kind of armed conflict. Patience (low time preference), which may reflect rebels' degree of ideological motivation, is crucial. Second, the mode of warfare or the conflict resolutions that develop are generally path-dependent and conditioned on the full set of options (including compromise). Various conditions (level of funding, ease of recruitment, access to weapons) influence different modes of warfare or a peaceful compromise in a complex way.
Keywords: terrorism; civil war; conflict duration; game theory; stochastic process; ideology

Improved parameterization of the quantum harmonic oscillator model based on localized wannier functions to describe Van der Waals interactions in density functional theory - Partovi-Azar, Pouya; Berg, Matthias; Sanna, Simone; Kühne, Thomas D. (International Journal of Quantum Chemistry)
Recently, the quantum harmonic oscillator model has been combined with maximally localized Wannier functions to account for long-range dispersion interactions in density functional theory calculations (Silvestrelli, J. Chem. Phys. 2013, 139, 054106). Here, we present a new, improved set of values for the three parameters involved in this scheme. To test the new parameter set we have computed the potential energy curves for various systems, including an isolated Ar2 dimer, two N2 dimers interacting within different configurations, and a water molecule physisorbed on pristine graphene. While the original set of parameters generally overestimates the interaction energies and underestimates the equilibrium distances, the new parameterization substantially improves the agreement with experimental and theoretical reference values. © 2016 Wiley Periodicals, Inc.
Keywords: Wannier orbitals; Van der Waals interactions; density functional theory; quantum harmonic oscillator

Fast and conspicuous? Quantifying salience with the theory of visual attention. - Krüger, Alexander; Tünnermann, Jan; Scharlau, Ingrid (Advances in Cognitive Psychology)
Particular differences between an object and its surrounding cause salience, guide attention, and improve performance in various tasks. While much research has been dedicated to identifying which feature dimensions contribute to salience, much less regard has been paid to the quantitative strength of the salience caused by feature differences. Only a few studies systematically related salience effects to a common salience measure, and they are partly outdated in the light of new findings on the time course of salience effects. We propose Bundesen’s Theory of Visual Attention (TV A) as a theoretical basis for measuring salience and introduce an empirical and modeling approach to link this theory to data retrieved from temporal-order judgments. With this procedure, TV A becomes applicable to a broad range of salience-related stimulus material. Three experiments with orientation pop-out displays demonstrate the feasibility of the method. A 4th experiment substantiates its applicability t
Keywords: salience; visual attention; Bayesian inference; theory of visual attention; computational modeling; Visual Attention; Computational Modeling; Inference; Judgment; Statistical Probability