The 1–2–3 Conjecture asserts that, for every connected graph different from K2, its edges can be labeled with 1,2,3 so that, when coloring each vertex with the sum of its incident labels, no two adjacent vertices get the same color. This conjecture takes place in the more general context of distinguishing labelings, where the goal is to label graphs so that some pairs of their elements are distinguishable relatively to some parameter computed from the labeling. In this work, we investigate the consequences of labeling graphs as in the 1–2–3 Conjecture when it is further required to make the maximum resulting color as small as possible. In some sense, we aim at producing a number of colors that is as close as possible to the chromatic number of the graph. We first investigate the hardness of determining the minimum maximum color by a labeling for a given graph, which we show is NP-complete in the class of bipartite graphs but polynomial-time solvable in the class of graphs with bounded treewidth. We then provide bounds on the minimum maximum color that can be generated both in the general context, and for particular classes of graphs. Finally, we study how using larger labels permit to reduce the maximum color.

Web-scale applications can ship code on a daily to weekly cadence. These applications rely on online metrics to monitor the health of new releases. Regressions in metric values need to be detected and diagnosed as early as possible to reduce the disruption to users and product owners. Regressions in metrics can surface due to a variety of reasons: genuine product regressions, changes in user population and bias due to telemetry loss (or processing) are among the common causes. Diagnosing the cause of these metric regressions is costly for engineering teams as they need to invest time in finding the root cause of the issue as soon as possible. We presentLumos, a Python library built using the principles of A/B testing to systematically diagnose metric regressions to automate such analysis.Lumos has been deployed across the component teams in Microsoft's Real-Time Communication (RTC) applications Skype and Microsoft Teams. It has enabled engineering teams to detect 100s of real changes in metrics and reject 1000s of false alarms detected by anomaly detectors. The application ofLumos has resulted in freeing up as much as $95%$ of the time allocated to metric-based investigations. In this work, we open sourceLumos and present our results from applying it to two different components within the RTC group over millions of sessions. This general library can be coupled with any production system to manage the volume of alerting efficiently.

We study methods for finding strict upper bounds on the fractional chromatic number $\chi_f(G)$ of a graph $G$. We illustrate these methods by providing short proofs of known inequalities in connection with Grötzsch's 3-color theorem and the 5-color theorem for planar graphs. We also apply it to $d$-degenerate graphs and conclude that every $K_{d+1}$-free $d$-degenerate graph with $n$ vertices has independence number $ 0$, the fractional chromatic number of any graph embedded on $S$ of sufficiently large width (depending only on $S$ and $\varepsilon$) is at most $4+\varepsilon$. In the same spirit we prove that Eulerian triangulations or triangle-free graphs of large width have $\chi_f\le 3+\varepsilon$, and quadrangulations of large width have $\chi_f\le 2+\varepsilon$. While the $\varepsilon$ is needed in the latter two results, we conjecture that in the first result $4+\varepsilon$ can be replaced by 4. The upper bounds $\chi_f\le 4+\varepsilon$, $\chi_f\le 3+\varepsilon$, $\chi_f\le 2+\varepsilon$, respectively, are already known for graphs on orientable surfaces, but our results are also valid for graphs on nonorientable surfaces. Surprisingly, a strict lower bound on the fractional chromatic number may imply an upper bound on the chromatic number: Grötzsch's theorem implies that every 4-chromatic planar graph $G$ has fractional chromatic number $\chi_f(G)\ge 3$. We conjecture that this inequality is always strict and observe that this implies the 4-color theorem for planar graphs.

Human activity recognition is central to many practical applications, ranging from visual surveillance to gaming interfacing. Most approaches addressing this problem are based on localized spatio-temporal features that can vary significantly when the viewpoint changes. As a result, their performances rapidly deteriorate as the difference between the viewpoints of the training and testing data increases. In this paper, we introduce a new type of feature, the “Hankelet” that captures dynamic properties of short tracklets. While Hankelets do not carry any spatial information, they bring invariant properties to changes in viewpoint that allow for robust cross-view activity recognition, i.e. when actions are recognized using a classifier trained on data from a different viewpoint. Our experiments on the IXMAS dataset show that using Hanklets improves the state of the art performance by over 20%.

Let $G$ be a graph on $n$ vertices. An induced subgraph $H$ of $G$ is called heavy if there exist two nonadjacent vertices in $H$ with degree sum at least $n$ in $G$. We say that $G$ is $H$-heavy if every induced subgraph of $G$ isomorphic to $H$ is heavy. For a family $\mathcal{H}$ of graphs, $G$ is called $\mathcal{H}$-heavy if $G$ is $H$-heavy for every $H\in\mathcal{H}$. In this paper we characterize all connected graphs $R$ and $S$ other than $P_3$ (the path on three vertices) such that every 2-connected $\{R,S\}$-heavy graph is Hamiltonian. This extends several previous results on forbidden subgraph conditions for Hamiltonian graphs.

Cameras are ubiquitous everywhere and hold the promise of significantly changing the way we live and interact with our environment. Human activity recognition is central to understanding dynamic scenes for applications ranging from security surveillance, to assisted living for the elderly, to video gaming without controllers. Most current approaches to solve this problem are based in the use of local temporal-spatial features that limit their ability to recognize long and complex actions. In this paper, we propose a new approach to exploit the temporal information encoded in the data. The main idea is to model activities as the output of unknown dynamic systems evolving from unknown initial conditions. Under this framework, we show that activity videos can be compared by computing the principal angles between subspaces representing activity types which are found by a simple SVD of the experimental data. The proposed approach outperforms state-of-the-art methods classifying activities in the KTH dataset as well as in much more complex scenarios involving interacting actors.

This paper considers the problem of sustained multicamera tracking in the presence of occlusion and changes in the target motion model. The key insight of the proposed method is the fact that, under mild conditions, the 2D trajectories of the target in the image planes of each of the cameras are constrained to evolve in the same subspace. This observation allows for identifying, at each time instant, a single (piecewise) linear model that explains all the available 2D measurements. In turn, this model can be used in the context of a modified particle filter to predict future target locations. In the case where the target is occluded to some of the cameras, the missing measurements can be estimated using the facts that they must lie both in the subspace spanned by previous measurements and satisfy epipolar constraints. Hence, by exploiting both dynamical and geometrical constraints the proposed method can robustly handle substantial occlusion, without the need for performing 3D reconstruction, calibrated cameras or constraints on sensor separation. The performance of the proposed tracker is illustrated with several challenging examples involving targets that substantially change appearance and motion models while occluded to some of the cameras.