Search

We propose an approach for simultaneous diarization and separation of meeting data. It consists of a complex Angular Central Gaussian Mixture Model (cACGMM) for speech source separation, and a von-Mises-Fisher Mixture Model (VMFMM) for diarization in a joint statistical framework. Through the integration, both spatial and spectral information are exploited for diarization and separation. We also develop a method for counting the number of active speakers in a segment of a meeting to support block-wise processing. While the total number of speakers in a meeting may be known, it is usually not known on a per-segment level. With the proposed speaker counting, joint diarization and source separation can be done segment-by-segment, and the permutation problem across segments is solved, thus allowing for block-online processing in the future. Experimental results on the LibriCSS meeting corpus show that the integrated approach outperforms a cascaded approach of diarization and speech enhancement in terms of WER, both on a per-segment and on a per-meeting level., Comment: Submitted to ICASSP2025

Diarization is a crucial component in meeting transcription systems to ease the challenges of speech enhancement and attribute the transcriptions to the correct speaker. Particularly in the presence of overlapping or noisy speech, these systems have problems reliably assigning the correct speaker labels, leading to a significant amount of speaker confusion errors. We propose to add segment-level speaker reassignment to address this issue. By revisiting, after speech enhancement, the speaker attribution for each segment, speaker confusion errors from the initial diarization stage are significantly reduced. Through experiments across different system configurations and datasets, we further demonstrate the effectiveness and applicability in various domains. Our results show that segment-level speaker reassignment successfully rectifies at least 40% of speaker confusion word errors, highlighting its potential for enhancing diarization accuracy in meeting transcription systems., Comment: Accepted for Interspeech 2024

Hyperbolic deep learning has become a growing research direction in computer vision for the unique properties afforded by the alternate embedding space. The negative curvature and exponentially growing distance metric provide a natural framework for capturing hierarchical relationships between datapoints and allowing for finer separability between their embeddings. However, these methods are still computationally expensive and prone to instability, especially when attempting to learn the negative curvature that best suits the task and the data. Current Riemannian optimizers do not account for changes in the manifold which greatly harms performance and forces lower learning rates to minimize projection errors. Our paper focuses on curvature learning by introducing an improved schema for popular learning algorithms and providing a novel normalization approach to constrain embeddings within the variable representative radius of the manifold. Additionally, we introduce a novel formulation for Riemannian AdamW, and alternative hybrid encoder techniques and foundational formulations for current convolutional hyperbolic operations, greatly reducing the computational penalty of the hyperbolic embedding space. Our approach demonstrates consistent performance improvements across both direct classification and hierarchical metric learning tasks while allowing for larger hyperbolic models.

We propose a modified teacher-student training for the extraction of frame-wise speaker embeddings that allows for an effective diarization of meeting scenarios containing partially overlapping speech. To this end, a geodesic distance loss is used that enforces the embeddings computed from regions with two active speakers to lie on the shortest path on a sphere between the points given by the d-vectors of each of the active speakers. Using those frame-wise speaker embeddings in clustering-based diarization outperforms segment-level clustering-based diarization systems such as VBx and Spectral Clustering. By extending our approach to a mixture-model-based diarization, the performance can be further improved, approaching the diarization error rates of diarization systems that use a dedicated overlap detection, and outperforming these systems when also employing an additional overlap detection., Comment: Accepted at ICASSP 2024

We propose a modular pipeline for the single-channel separation, recognition, and diarization of meeting-style recordings and evaluate it on the Libri-CSS dataset. Using a Continuous Speech Separation (CSS) system with a TF-GridNet separation architecture, followed by a speaker-agnostic speech recognizer, we achieve state-of-the-art recognition performance in terms of Optimal Reference Combination Word Error Rate (ORC WER). Then, a d-vector-based diarization module is employed to extract speaker embeddings from the enhanced signals and to assign the CSS outputs to the correct speaker. Here, we propose a syntactically informed diarization using sentence- and word-level boundaries of the ASR module to support speaker turn detection. This results in a state-of-the-art Concatenated minimum-Permutation Word Error Rate (cpWER) for the full meeting recognition pipeline., Comment: Accepted at HSCMA Sattelite Workshop at ICASSP 2024

We introduce a monaural neural speaker embeddings extractor that computes an embedding for each speaker present in a speech mixture. To allow for supervised training, a teacher-student approach is employed: the teacher computes the target embeddings from each speaker's utterance before the utterances are added to form the mixture, and the student embedding extractor is then tasked to reproduce those embeddings from the speech mixture at its input. The system much more reliably verifies the presence or absence of a given speaker in a mixture than a conventional speaker embedding extractor, and even exhibits comparable performance to a multi-channel approach that exploits spatial information for embedding extraction. Further, it is shown that a speaker embedding computed from a mixture can be used to check for the presence of that speaker in another mixture., Comment: Proceedings of INTERSPEECH

Using a Teacher-Student training approach we developed a speaker embedding extraction system that outputs embeddings at frame rate. Given this high temporal resolution and the fact that the student produces sensible speaker embeddings even for segments with speech overlap, the frame-wise embeddings serve as an appropriate representation of the input speech signal for an end-to-end neural meeting diarization (EEND) system. We show in experiments that this representation helps mitigate a well-known problem of EEND systems: when increasing the number of speakers the diarization performance drop is significantly reduced. We also introduce block-wise processing to be able to diarize arbitrarily long meetings., Comment: ICASSP 2023

Real-world visual data exhibit intrinsic hierarchical structures that can be represented effectively in hyperbolic spaces. Hyperbolic neural networks (HNNs) are a promising approach for learning feature representations in such spaces. However, current HNNs in computer vision rely on Euclidean backbones and only project features to the hyperbolic space in the task heads, limiting their ability to fully leverage the benefits of hyperbolic geometry. To address this, we present HCNN, a fully hyperbolic convolutional neural network (CNN) designed for computer vision tasks. Based on the Lorentz model, we generalize fundamental components of CNNs and propose novel formulations of the convolutional layer, batch normalization, and multinomial logistic regression. {Experiments on standard vision tasks demonstrate the promising performance of our HCNN framework in both hybrid and fully hyperbolic settings.} Overall, we believe our contributions provide a foundation for developing more powerful HNNs that can better represent complex structures found in image data. Our code is publicly available at https://github.com/kschwethelm/HyperbolicCV.

The scope of speech enhancement has changed from a monolithic view of single, independent tasks, to a joint processing of complex conversational speech recordings. Training and evaluation of these single tasks requires synthetic data with access to intermediate signals that is as close as possible to the evaluation scenario. As such data often is not available, many works instead use specialized databases for the training of each system component, e.g WSJ0-mix for source separation. We present a Multi-purpose Multi-Speaker Mixture Signal Generator (MMS-MSG) for generating a variety of speech mixture signals based on any speech corpus, ranging from classical anechoic mixtures (e.g., WSJ0-mix) over reverberant mixtures (e.g., SMS-WSJ) to meeting-style data. Its highly modular and flexible structure allows for the simulation of diverse environments and dynamic mixing, while simultaneously enabling an easy extension and modification to generate new scenarios and mixture types. These meetings can be used for prototyping, evaluation, or training purposes. We provide example evaluation data and baseline results for meetings based on the WSJ corpus. Further, we demonstrate the usefulness for realistic scenarios by using MMS-MSG to provide training data for the LibriCSS database., Comment: Accepted at IWAENC 2022

We propose a system that transcribes the conversation of a typical meeting scenario that is captured by a set of initially unsynchronized microphone arrays at unknown positions. It consists of subsystems for signal synchronization, including both sampling rate and sampling time offset estimation, diarization based on speaker and microphone array position estimation, multi-channel speech enhancement, and automatic speech recognition. With the estimated diarization information, a spatial mixture model is initialized that is used to estimate beamformer coefficients for source separation. Simulations show that the speech recognition accuracy can be improved by synchronizing and combining multiple distributed microphone arrays compared to a single compact microphone array. Furthermore, the proposed informed initialization of the spatial mixture model delivers a clear performance advantage over random initialization., Comment: Submitted to INTERSPEECH 2022

Spatial mixture model (SMM) supported acoustic beamforming has been extensively used for the separation of simultaneously active speakers. However, it has hardly been considered for the separation of meeting data, that are characterized by long recordings and only partially overlapping speech. In this contribution, we show that the fact that often only a single speaker is active can be utilized for a clever initialization of an SMM that employs time-varying class priors. In experiments on LibriCSS we show that the proposed initialization scheme achieves a significantly lower Word Error Rate (WER) on a downstream speech recognition task than a random initialization of the class probabilities by drawing from a Dirichlet distribution. With the only requirement that the number of speakers has to be known, we obtain a WER of 5.9 %, which is comparable to the best reported WER on this data set. Furthermore, the estimated speaker activity from the mixture model serves as a diarization based on spatial information., Comment: Submitted to INTERSPEECH 2022

We present a Reduced Order Model (ROM) which exploits recent developments in Physics Informed Neural Networks (PINNs) for solving inverse problems for the Navier--Stokes equations (NSE). In the proposed approach, the presence of simulated data for the fluid dynamics fields is assumed. A POD-Galerkin ROM is then constructed by applying POD on the snapshots matrices of the fluid fields and performing a Galerkin projection of the NSE (or the modified equations in case of turbulence modeling) onto the POD reduced basis. A $\textit{POD-Galerkin PINN ROM}$ is then derived by introducing deep neural networks which approximate the reduced outputs with the input being time and/or parameters of the model. The neural networks incorporate the physical equations (the POD-Galerkin reduced equations) into their structure as part of the loss function. Using this approach, the reduced model is able to approximate unknown parameters such as physical constants or the boundary conditions. A demonstration of the applicability of the proposed ROM is illustrated by two cases which are the steady flow around a backward step and the unsteady turbulent flow around a surface mounted cubic obstacle., Comment: Second version with additional test case

Impressive progress in neural network-based single-channel speech source separation has been made in recent years. But those improvements have been mostly reported on anechoic data, a situation that is hardly met in practice. Taking the SepFormer as a starting point, which achieves state-of-the-art performance on anechoic mixtures, we gradually modify it to optimize its performance on reverberant mixtures. Although this leads to a word error rate improvement by 7 percentage points compared to the standard SepFormer implementation, the system ends up with only marginally better performance than a PIT-BLSTM separation system, that is optimized with rather straightforward means. This is surprising and at the same time sobering, challenging the practical usefulness of many improvements reported in recent years for monaural source separation on nonreverberant data., Comment: Submitted to IWAENC 2022

Using machine learning (ML) techniques in general and deep learning techniques in specific needs a certain amount of data often not available in large quantities in technical domains. The manual inspection of machine tool components and the manual end-of-line check of products are labor-intensive tasks in industrial applications that companies often want to automate. To automate classification processes and develop reliable and robust machine learning-based classification and wear prognostics models, one needs real-world datasets to train and test the models. The dataset is available under https://doi.org/10.5445/IR/1000129520., Comment: 7 pages, 13 figures

The rapid uptake of renewable energy technologies in recent decades has increased the demand of energy researchers, policymakers and energy planners for reliable data on the spatial distribution of their costs and potentials. For onshore wind energy this has resulted in an active research field devoted to analysing these resources for regions, countries or globally. A particular thread of this research attempts to go beyond purely technical or spatial restrictions and determine the realistic, feasible or actual potential for wind energy. Motivated by these developments, this paper reviews methods and assumptions for analysing geographical, technical, economic and, finally, feasible onshore wind potentials. We address each of these potentials in turn, including aspects related to land eligibility criteria, energy meteorology, and technical developments relating to wind turbine characteristics such as power density, specific rotor power and spacing aspects. Economic aspects of potential assessments are central to future deployment and are discussed on a turbine and system level covering levelized costs depending on locations, and the system integration costs which are often overlooked in such analyses. Non-technical approaches include scenicness assessments of the landscape, expert and stakeholder workshops, willingness to pay / accept elicitations and socioeconomic cost-benefit studies. For each of these different potential estimations, the state of the art is critically discussed, with an attempt to derive best practice recommendations and highlight avenues for future research.

In this work we address disentanglement of style and content in speech signals. We propose a fully convolutional variational autoencoder employing two encoders: a content encoder and a style encoder. To foster disentanglement, we propose adversarial contrastive predictive coding. This new disentanglement method does neither need parallel data nor any supervision. We show that the proposed technique is capable of separating speaker and content traits into the two different representations and show competitive speaker-content disentanglement performance compared to other unsupervised approaches. We further demonstrate an increased robustness of the content representation against a train-test mismatch compared to spectral features, when used for phone recognition., Comment: accepted by icassp 2021

Protecting embedded security is becoming an increasingly challenging research problem for embedded systems due to a number of emerging trends in hardware, software, networks, and applications. Without fundamental advances in, and an understanding of embedded security it will be difficult for future engineers to provide assurance for the Internet of Things (IoT) and Operational Technology (OT) in wide ranging applications, from home automation and autonomous transportation to medical devices and factory floors. Common to such applications are cyberphysical risks and consequences stemming from a lack of embedded security. The Computing Community Consortium (CCC) held a one-day visioning workshop to explore these issues. The workshop focused on five major application areas of embedded systems, namely (1) medical/wearable devices, (2) autonomous systems (drones, vehicles, robots), (3) smart homes, (4) industry and supply chain, and (5) critical infrastructure. This report synthesizes the results of that workshop and develops a list of strategic goals for research and education over the next 5-10 years. Embedded security in connected devices presents challenges that require a broad look at the overall systems design, including human and societal dimensions as well as technical. Particular issues related to embedded security are a subset of the overall security of the application areas, which must also balance other design criteria such as cost, power, reliability, usability and function. Recent trends are converging to make the security of embedded systems an increasingly important and difficult objective, requiring new trans-disciplinary approaches to solve problems on a 5-10 year horizon., Comment: A Computing Community Consortium (CCC) workshop report, 24 pages

Deep metric learning employs deep neural networks to embed instances into a metric space such that distances between instances of the same class are small and distances between instances from different classes are large. In most existing deep metric learning techniques, the embedding of an instance is given by a feature vector produced by a deep neural network and Euclidean distance or cosine similarity defines distances between these vectors. In this paper, we study deep distributional embeddings of sequences, where the embedding of a sequence is given by the distribution of learned deep features across the sequence. This has the advantage of capturing statistical information about the distribution of patterns within the sequence in the embedding. When embeddings are distributions rather than vectors, measuring distances between embeddings involves comparing their respective distributions. We propose a distance metric based on Wasserstein distances between the distributions and a corresponding loss function for metric learning, which leads to a novel end-to-end trainable embedding model. We empirically observe that distributional embeddings outperform standard vector embeddings and that training with the proposed Wasserstein metric outperforms training with other distance functions.

We study the problem of inferring readers' identities and estimating their level of text comprehension from observations of their eye movements during reading. We develop a generative model of individual gaze patterns (scanpaths) that makes use of lexical features of the fixated words. Using this generative model, we derive a Fisher-score representation of eye-movement sequences. We study whether a Fisher-SVM with this Fisher kernel and several reference methods are able to identify readers and estimate their level of text comprehension based on eye-tracking data. While none of the methods are able to estimate text comprehension accurately, we find that the SVM with Fisher kernel excels at identifying readers., Comment: Proceedings of the European Conference on Machine Learning, 2018

We study the problem of identifying individuals based on their characteristic gaze patterns during reading of arbitrary text. The motivation for this problem is an unobtrusive biometric setting in which a user is observed during access to a document, but no specific challenge protocol requiring the user's time and attention is carried out. Existing models of individual differences in gaze control during reading are either based on simple aggregate features of eye movements, or rely on parametric density models to describe, for instance, saccade amplitudes or word fixation durations. We develop flexible semiparametric models of eye movements during reading in which densities are inferred under a Gaussian process prior centered at a parametric distribution family that is expected to approximate the true distribution well. An empirical study on reading data from 251 individuals shows significant improvements over the state of the art.

Instead of defining goodness of fit (GOF) tests in terms of their test statistics, we present an alternative method by introducing the concept of local levels, which indicate high or low local sensitivity of a test. Local levels can act as a starting point for the construction of new GOF tests. We study the behavior of local levels when applied to some well-known GOF tests such as Kolmogorov-Smirnov (KS) tests, higher criticism (HC) tests and tests based on phi-divergences. The main focus is on a rigorous characterization of the asymptotic behavior of local levels of the original HC tests which leads to several further asymptotic results for local levels of other GOF tests including GOF tests with equal local levels. While local levels of KS tests, which are related to the central range, are asymptotically strictly larger than zero, all local levels of HC tests converge to zero as the sample size increases. Consequently, there exists no asymptotic level $\alpha$ GOF test such that all local levels are asymptotically bounded away from zero. Finally, by means of numerical computations we compare classical KS and HC tests to a GOF test with equal local levels., Comment: Published at http://dx.doi.org/10.3150/14-BEJ694 in the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)

In this paper, we solve the local gathering problem of a swarm of $n$ indistinguishable, point-shaped robots on a two dimensional grid in asymptotically optimal time $\mathcal{O}(n)$ in the fully synchronous $\mathcal{FSYNC}$ time model. Given an arbitrarily distributed (yet connected) swarm of robots, the gathering problem on the grid is to locate all robots within a $2\times 2$-sized area that is not known beforehand. Two robots are connected if they are vertical or horizontal neighbors on the grid. The locality constraint means that no global control, no compass, no global communication and only local vision is available; hence, a robot can only see its grid neighbors up to a constant $L_1$-distance, which also limits its movements. A robot can move to one of its eight neighboring grid cells and if two or more robots move to the same location they are \emph{merged} to be only one robot. The locality constraint is the significant challenging issue here, since robot movements must not harm the (only globally checkable) swarm connectivity. For solving the gathering problem, we provide a synchronous algorithm -- executed by every robot -- which ensures that robots merge without breaking the swarm connectivity. In our model, robots can obtain a special state, which marks such a robot to be performing specific connectivity preserving movements in order to allow later merge operations of the swarm. Compared to the grid, for gathering in the Euclidean plane for the same robot and time model the best known upper bound is $\mathcal{O}(n^2)$., Comment: arXiv admin note: substantial text overlap with arXiv:1510.05454

We consider the following variant of the two dimensional gathering problem for swarms of robots: Given a swarm of $n$ indistinguishable, point shaped robots on a two dimensional grid. Initially, the robots form a closed chain on the grid and must keep this connectivity during the whole process of their gathering. Connectivity means, that neighboring robots of the chain need to be positioned at the same or neighboring points of the grid. In our model, gathering means to keep shortening the chain until the robots are located inside a $2\times 2$ subgrid. Our model is completely local (no global control, no global coordinates, no compass, no global communication or vision, \ldots). Each robot can only see its next constant number of left and right neighbors on the chain. This fixed constant is called the \emph{viewing path length}. All its operations and detections are restricted to this constant number of robots. Other robots, even if located at neighboring or the same grid point cannot be detected. Only based on the relative positions of its detectable chain neighbors, a robot can decide to obtain a certain state. Based on this state and their local knowledge, the robots do local modifications to the chain by moving to neighboring grid points without breaking the chain. These modifications are performed without the knowledge whether they lead to a global progress or not. We assume the fully synchronous $\mathcal{FSYNC}$ model. For this problem, we present a gathering algorithm which needs linear time. This result generalizes the result from \cite{hopper}, where an open chain with specified distinguishable (and fixed) endpoints is considered.

We study learning problems in which the conditional distribution of the output given the input varies as a function of additional task variables. In varying-coefficient models with Gaussian process priors, a Gaussian process generates the functional relationship between the task variables and the parameters of this conditional. Varying-coefficient models subsume hierarchical Bayesian multitask models, but also generalizations in which the conditional varies continuously, for instance, in time or space. However, Bayesian inference in varying-coefficient models is generally intractable. We show that inference for varying-coefficient models with isotropic Gaussian process priors resolves to standard inference for a Gaussian process that can be solved efficiently. MAP inference in this model resolves to multitask learning using task and instance kernels, and inference for hierarchical Bayesian multitask models can be carried out efficiently using graph-Laplacian kernels. We report on experiments for geospatial prediction., Comment: 17 pages, 4 Figures, minor revision

We investigate a non-cooperative game-theoretic model for the formation of communication networks by selfish agents. Each agent aims for a central position at minimum cost for creating edges. In particular, the general model (Fabrikant et al., PODC'03) became popular for studying the structure of the Internet or social networks. Despite its significance, locality in this game was first studied only recently (Bil\`o et al., SPAA'14), where a worst case locality model was presented, which came with a high efficiency loss in terms of quality of equilibria. Our main contribution is a new and more optimistic view on locality: agents are limited in their knowledge and actions to their local view ranges, but can probe different strategies and finally choose the best. We study the influence of our locality notion on the hardness of computing best responses, convergence to equilibria, and quality of equilibria. Moreover, we compare the strength of local versus non-local strategy-changes. Our results address the gap between the original model and the worst case locality variant. On the bright side, our efficiency results are in line with observations from the original model, yet we have a non-constant lower bound on the price of anarchy., Comment: An extended abstract of this paper has been accepted for publication in the proceedings of the 40th International Conference on Mathematical Foundations on Computer Science

In the gathering problem, n autonomous robots have to meet on a single point. We consider the gathering of a closed chain of point-shaped, anonymous robots on a grid. The robots only have local knowledge about a constant number of neighboring robots along the chain in both directions. Actions are performed in the fully synchronous time model FSYNC. Every robot has a limited memory that may contain one timestamp of the global clock, also visible to its direct neighbors. In this synchronous time model, there is no limited view gathering algorithm known to perform better than in quadratic runtime. The configurations that show the quadratic lower bound are closed chains. In this paper, we present the first sub-quadratic---in fact linear time---gathering algorithm for closed chains on a grid.

We consider a multilevel network game, where nodes can improve their communication costs by connecting to a high-speed network. The $n$ nodes are connected by a static network and each node can decide individually to become a gateway to the high-speed network. The goal of a node $v$ is to minimize its private costs, i.e., the sum (SUM-game) or maximum (MAX-game) of communication distances from $v$ to all other nodes plus a fixed price $\alpha > 0$ if it decides to be a gateway. Between gateways the communication distance is $0$, and gateways also improve other nodes' distances by behaving as shortcuts. For the SUM-game, we show that for $\alpha \leq n-1$, the price of anarchy is $\Theta(n/\sqrt{\alpha})$ and in this range equilibria always exist. In range $\alpha \in (n-1,n(n-1))$ the price of anarchy is $\Theta(\sqrt{\alpha})$, and for $\alpha \geq n(n-1)$ it is constant. For the MAX-game, we show that the price of anarchy is either $\Theta(1 + n/\sqrt{\alpha})$, for $\alpha\geq 1$, or else $1$. Given a graph with girth of at least $4\alpha$, equilibria always exist. Concerning the dynamics, both the SUM-game and the MAX-game are not potential games. For the SUM-game, we even show that it is not weakly acyclic., Comment: An extended abstract of this paper has been accepted for publication in the proceedings of the 10th International Conference on Web and Internet Economics (WINE)

Network creation games model the creation and usage costs of networks formed by n selfish nodes. Each node v can buy a set of edges, each for a fixed price \alpha > 0. Its goal is to minimize its private costs, i.e., the sum (SUM-game, Fabrikant et al., PODC 2003) or maximum (MAX-game, Demaine et al., PODC 2007) of distances from $v$ to all other nodes plus the prices of the bought edges. The above papers show the existence of Nash equilibria as well as upper and lower bounds for the prices of anarchy and stability. In several subsequent papers, these bounds were improved for a wide range of prices \alpha. In this paper, we extend these models by incorporating quality-of-service aspects: Each edge cannot only be bought at a fixed quality (edge length one) for a fixed price \alpha. Instead, we assume that quality levels (i.e., edge lengths) are varying in a fixed interval [\beta,B], 0 < \beta <= B. A node now cannot only choose which edge to buy, but can also choose its quality x, for the price p(x), for a given price function p. For both games and all price functions, we show that Nash equilibria exist and that the price of stability is either constant or depends only on the interval size of available edge lengths. Our main results are bounds for the price of anarchy. In case of the SUM-game, we show that they are tight if price functions decrease sufficiently fast., Comment: An extended abstract of this paper has been accepted for publication in the proceedings of the 10th International Conference on Web and Internet Economics (WINE)

We present and study a new model for energy-aware and profit-oriented scheduling on a single processor. The processor features dynamic speed scaling as well as suspension to a sleep mode. Jobs arrive over time, are preemptable, and have different sizes, values, and deadlines. On the arrival of a new job, the scheduler may either accept or reject the job. Accepted jobs need a certain energy investment to be finished in time, while rejected jobs cause costs equal to their values. Here, power consumption at speed $s$ is given by $P(s)=s^{\alpha}+\beta$ and the energy investment is power integrated over time. Additionally, the scheduler may decide to suspend the processor to a sleep mode in which no energy is consumed, though awaking entails fixed transition costs $\gamma$. The objective is to minimize the total value of rejected jobs plus the total energy. Our model combines aspects from advanced energy conservation techniques (namely speed scaling and sleep states) and profit-oriented scheduling models. We show that \emph{rejection-oblivious} schedulers (whose rejection decisions are not based on former decisions) have -- in contrast to the model without sleep states -- an unbounded competitive ratio w.r.t\text{.} the processor parameters $\alpha$ and $\beta$. It turns out that the worst-case performance of such schedulers depends linearly on the jobs' value densities (the ratio between a job's value and its work). We give an algorithm whose competitiveness nearly matches this lower bound. If the maximum value density is not too large, the competitiveness becomes $\alpha^{\alpha}+2e\alpha$. Also, we show that it suffices to restrict the value density of low-value jobs only. Using a technique from \cite{Chan:2010} we transfer our results to processors with a fixed maximum speed., Comment: An extended abstract of this paper has been accepted for publication in the proceedings of the 1st Mediterranean Conference on Algorithms

Network creation games model the creation and usage costs of networks formed by a set of selfish peers. Each peer has the ability to change the network in a limited way, e.g., by creating or deleting incident links. In doing so, a peer can reduce its individual communication cost. Typically, these costs are modeled by the maximum or average distance in the network. We introduce a generalized version of the basic network creation game (BNCG). In the BNCG (by Alon et al., SPAA 2010), each peer may replace one of its incident links by a link to an arbitrary peer. This is done in a selfish way in order to minimize either the maximum or average distance to all other peers. That is, each peer works towards a network structure that allows himself to communicate efficiently with all other peers. However, participants of large networks are seldom interested in all peers. Rather, they want to communicate efficiently only with a small subset of peers. Our model incorporates these (communication) interests explicitly. In the MAX-version, each node tries to minimize its maximum distance to nodes it is interested in. Given peers with interests and a communication network forming a tree, we prove several results on the structure and quality of equilibria in our model. For the MAX-version, we give an upper worst case bound of O(\sqrt{n}) for the private costs in an equilibrium of n peers. Moreover, we give an equilibrium for a circular interest graph where a node has private cost \Omega(\sqrt{n}), showing that our bound is tight. This example can be extended such that we get a tight bound of \Theta(\sqrt{n}) for the price of anarchy. For the case of general communication networks we show the price of anarchy to be \Theta(n). Additionally, we prove an interesting connection between a maximum independent set in the interest graph and the private costs of the peers., Comment: An extended abstract of this paper has been accepted for publication in the proceedings of the 5th International Symposium on Algorithmic Game Theory (SAGT)

This paper addresses the problem of inferring a regular expression from a given set of strings that resembles, as closely as possible, the regular expression that a human expert would have written to identify the language. This is motivated by our goal of automating the task of postmasters of an email service who use regular expressions to describe and blacklist email spam campaigns. Training data contains batches of messages and corresponding regular expressions that an expert postmaster feels confident to blacklist. We model this task as a learning problem with structured output spaces and an appropriate loss function, derive a decoder and the resulting optimization problem, and a report on a case study conducted with an email service., Comment: ICML2012

We study for a class of symmetric L\'evy processes with state space $\rn$ the transition density $p_t(x)$ in terms of two one-parameter families of metrics, $(d_t)_{t>0}$ and $(\delta_t)_{t>0}$. The first family of metrics describes the diagonal term $p_t(0)$; it is induced by the characteristic exponent $\psi$ of the L\'evy process by $d_t(x,y)=\sqrt{t\psi(x-y)}$. The second and new family of metrics $\delta_t$ relates to $\sqrt{t\psi}$ through the formula $$ \exp(-\delta_t^2(x,y)) = \Ff[\frac{e^{-t\psi}}{p_t(0)}](x-y) $$ where $\Ff$ denotes the Fourier transform. Thus we obtain the following "Gaussian" representation of the transition density: $p_t(x)=p_t(0) e^{-\delta_t^2(x,0)}$ where $p_t(0)$ corresponds to a volume term related to $\sqrt{t\psi}$ and where an "exponential" decay is governed by $\delta_t^2$. This gives a complete and new geometric, intrinsic interpretation of $p_t(x)$.

Several models for physics beyond the Standard Model predict new particles with a decay signature including hard photons and missing energy. Two well-motivated examples are supersymmetry with gauge-mediated breaking (GMSB) and the standard model with two universal extra dimensions. Both models lead to decay chains with similar collider signatures, including hard photon emission. The main discriminating feature are the spins of the new particles. In this paper we discuss how information about the spins of the particles can be extracted from lepton-photon or quark-photon invariant mass distributions at the Large Hadron Collider. The characteristic shapes of the distributions are derived analytically and then studied in a realistic Monte-Carlo simulation. We find that for a typical GMSB mass spectrum with particle masses below 1 TeV, already 10 fb$^{-1}$ integrated luminosity at 14 TeV center-of-mass energy are sufficient to discriminate the two models with high significance., Comment: 26 pages, 7 postscript figures, published version

Statistically resolving the underlying haplotype pair for a genotype measurement is an important intermediate step in gene mapping studies, and has received much attention recently. Consequently, a variety of methods for this problem have been developed. Different methods employ different statistical models, and thus implicitly encode different assumptions about the nature of the underlying haplotype structure. Depending on the population sample in question, their relative performance can vary greatly, and it is unclear which method to choose for a particular sample. Instead of choosing a single method, we explore combining predictions returned by different methods in a principled way, and thereby circumvent the problem of method selection. We propose several techniques for combining haplotype reconstructions and analyze their computational properties. In an experimental study on real-world haplotype data we show that such techniques can provide more accurate and robust reconstructions, and are useful for outlier detection. Typically, the combined prediction is at least as accurate as or even more accurate than the best individual method, effectively circumventing the method selection problem.

Yehuda Vardi introduced the term network tomography and was the first to propose and study how statistical inverse methods could be adapted to attack important network problems (Vardi, 1996). More recently, in one of his final papers, Vardi proposed notions of metrics on networks to define and measure distances between a network's links, its paths, and also between different networks (Vardi, 2004). In this paper, we apply Vardi's general approach for network metrics to a real data network by using data obtained from special data network tools and testing procedures presented here. We illustrate how the metrics help explicate interesting features of the traffic characteristics on the network. We also adapt the metrics in order to condition on traffic passing through a portion of the network, such as a router or pair of routers, and show further how this approach helps to discover and explain interesting network characteristics., Comment: Published at http://dx.doi.org/10.1214/074921707000000058 in the IMS Lecture Notes Monograph Series (http://www.imstat.org/publications/lecnotes.htm) by the Institute of Mathematical Statistics (http://www.imstat.org)

Comment: Monitoring Networked Applications With Incremental Quantile Estimation [arXiv:0708.0302], Comment: Published at http://dx.doi.org/10.1214/088342306000000619 in the Statistical Science (http://www.imstat.org/sts/) by the Institute of Mathematical Statistics (http://www.imstat.org)

Proteins created by combinatorial methods in vitro are an important source of information for understanding sequence-structure-function relationships. Alignments of folded proteins from combinatorial libraries can be analyzed using methods developed for naturally occurring proteins, but this neglects the information contained in the unfolded sequences of the library. We introduce two algorithms, logistic regression and excess information analysis, that use both the folded and unfolded sequences and compare them against contingency table and statistical coupling analysis, which only use the former. The test set for this benchmark study is a library of fictitious proteins that fold according to a hypothetical energy model. Of the four methods studied, only logistic regression is able to correctly recapitulate the energy model from the sequence alignment. The other algorithms predict spurious interactions between alignment positions with strong but individual influences on protein stability. When present in the same protein, stabilizing amino acids tend to lower the energy below the threshold needed for folding. As a result, their frequencies in the alignment can be correlated even if the positions do not interact. We believe any algorithm that neglects the nonlinear relationship between folding and energy is susceptible to this error., Comment: 21 pages, 2 figures

The band structure of semimagnetic Hg_1-yMn_yTe/Hg_1-xCd_xTe type-III quantum wells has been calculated using eight-band kp model in an envelope function approach. Details of the band structure calculations are given for the Mn free case (y=0). A mean field approach is used to take the influence of the sp-d exchange interaction on the band structure of QW's with low Mn concentrations into account. The calculated Landau level fan diagram and the density of states of a Hg_0.98Mn_0.02Te/Hg_0.3Cd_0.7Te QW are in good agreement with recent experimental transport observations. The model can be used to interpret the mutual influence of the two-dimensional confinement and the sp-d exchange interaction on the transport properties of Hg_1-yMn_yTe/Hg_1-xCd_xTe QW's., Comment: 12 pages, 4 figures

An optical method is suggested to determine the concentration of two-dimensional electrons in modulation-doped quantum wells at low and moderate electron densities between 10^{9} and 2x10^{11} cm^{-2}. The method is based on an analysis of magneto-reflectivity spectra of charged excitons (trions). The circular polarization degree and the oscillator strength of the charged excitons contain information about the density and spin polarization of two-dimensional electron gas. The method is applied to CdTe/(Cd,Mg)Te and ZnSe/Zn,Mg)(S,Se) heterostructures.

An approach is proposed to determine parameters of homogeneous and inhomogeneous broadening for reflection lines of quasi-two-dimensional excitons in semiconductor quantum well structures. A phenomenological model is developed taking into account fluctuations of the exciton energy which are expected to cause inhomogeneous broadening of exciton reflectivity lines. This concept is applied to magneto-optical studies of CdTe/(Cd,Mg)Te single quantum well heterostructures containing a two-dimensional electron gas. By the analysis of excitonic reflection spectra in magnetic fields the parameters of homogeneous and inhomogeneous broadening of the exciton as well as their temperature dependencies were obtained., Comment: 13 pages, 4 figures

Using angle-resolved synchrotron-radiation photoemission spectroscopy we have determined the dispersion of the valence bands of BeTe(100) along $\Gamma X$, i.e. the [100] direction. The measurements are analyzed with the aid of a first-principles calculation of the BeTe bulk band structure as well as of the photoemission peaks as given by the momentum conserving bulk transitions. Taking the calculated unoccupied bands as final states of the photoemission process, we obtain an excellent agreement between experimental and calculated spectra and a clear interpretation of almost all measured bands. In contrast, the free electron approximation for the final states fails to describe the BeTe bulk band structure along $\Gamma X$ properly., Comment: 21 pages plus 4 figures

The freshman composition course at Mayville State College (North Dakota) progresses from basic grammar to sentence combining to the development of expository writing skills based on the principles of generative rhetoric. The course begins with a brief review of grammar, emphasizing the phrase, clause, and sentence, and then moves on to the process of sentence combining. The next phase of the course introduces generative rhetoric, including the cumulative sentence, the general idea stated in the base clause, and the more specific details developed in the phrases and clauses of the lower levels, either coordinately or subordinately. Once students have grasped this idea, they begin to work with constructions that authors commonly use, including the noun phrase, the absolute, and the verbal phrase. Constant writing assignments serve to strengthen the skills they have learned. Once they have mastered sentence construction, they then apply the same principles of construction to the development of paragraphs. They learn to take a single word or idea, add several coordinate or subordinate ideas to produce a good sentence, and then to expand this sentence into a paragraph. After learning to write a good paragraph, they are taught how to apply the skills to answering essay test questions from other disciplines. The course concludes with an introduction to reading fiction and poetry, with an emphasis on authors' use of variety in sentence structure. (FL)