• Publicationsclose
• Research dataclose
• Other research productsclose
• Open Access close
• IL close
• AE close
• arXiv.org e-Print Archive close

Real-life parallel machine scheduling problems can be characterized by: (i) limited information about the exact task duration at scheduling time, and (ii) an opportunity to reschedule the remaining tasks each time a task processing is completed and a machine becomes idle. Robust optimization is the natural methodology to cope with the first characteristic of duration uncertainty, yet the existing literature on robust scheduling does not explicitly consider the second characteristic - the possibility to adjust decisions as more information about the tasks' duration becomes available, despite that re-optimizing the schedule every time new information emerges is standard practice. In this paper, we develop a scheduling approach that takes into account, at the beginning of the planning horizon, the possibility that scheduling decisions can be adjusted. We demonstrate that the suggested approach can lead to better here-and-now decisions and better makespan guarantees. To that end, we develop the first mixed integer linear programming model for adjustable robust scheduling, and a scalable two-stage approximation heuristic, where we minimize the worst-case makespan. Using this model, we show via a numerical study that adjustable scheduling leads to solutions with better and more stable makespan realizations compared to static approaches.

Two major challenges in distributed learning and estimation are 1) preserving the privacy of the local samples; and 2) communicating them efficiently to a central server, while achieving high accuracy for the end-to-end task. While there has been significant interest in addressing each of these challenges separately in the recent literature, treatments that simultaneously address both challenges are still largely missing. In this paper, we develop novel encoding and decoding mechanisms that simultaneously achieve optimal privacy and communication efficiency in various canonical settings. In particular, we consider the problems of mean estimation and frequency estimation under $\varepsilon$-local differential privacy and $b$-bit communication constraints. For mean estimation, we propose a scheme based on Kashin's representation and random sampling, with order-optimal estimation error under both constraints. For frequency estimation, we present a mechanism that leverages the recursive structure of Walsh-Hadamard matrices and achieves order-optimal estimation error for all privacy levels and communication budgets. As a by-product, we also construct a distribution estimation mechanism that is rate-optimal for all privacy regimes and communication constraints, extending recent work that is limited to $b=1$ and $\varepsilon=O(1)$. Our results demonstrate that intelligent encoding under joint privacy and communication constraints can yield a performance that matches the optimal accuracy achievable under either constraint alone. 35 pages, 9 figures, submitted to NeurIPS 2020

We study signal processing tasks in which the signal is mapped via some generalized time-frequency transform to a higher dimensional time-frequency space, processed there, and synthesized to an output signal. We show how to approximate such methods using a quasi-Monte Carlo (QMC) approach. We consider cases where the time-frequency representation is redundant, having feature axes in addition to the time and frequency axes. The proposed QMC method allows sampling both efficiently and evenly such redundant time-frequency representations. Indeed, 1) the number of samples required for a certain accuracy is log-linear in the resolution of the signal space, and depends only weakly on the dimension of the redundant time-frequency space, and 2) the quasi-random samples have low discrepancy, so they are spread evenly in the redundant time-frequency space. One example of such redundant representation is the localizing time-frequency transform (LTFT), where the time-frequency plane is enhanced by a third axis. This higher dimensional time-frequency space improves the quality of some time-frequency signal processing tasks, like the phase vocoder (an audio signal processing effect). Since the computational complexity of the QMC is log-linear in the resolution of the signal space, this higher dimensional time-frequency space does not degrade the computation complexity of the proposed QMC method. The proposed QMC method is more efficient than standard Monte Carlo methods, since the deterministic QMC sample points are optimally spread in the time-frequency space, while random samples are not.

Any Lipschitz map $f\colon M \to N$ between metric spaces can be ``linearised'' in such a way that it becomes a bounded linear operator $\widehat{f}\colon \mathcal F(M) \to \mathcal F(N)$ between the Lipschitz-free spaces over $M$ and $N$. The purpose of this note is to explore the connections between the injectivity of $f$ and the injectivity of $\widehat{f}$. While it is obvious that if $\widehat{f}$ is injective then so is $f$, the converse is less clear. Indeed, we pin down some cases where this implication does not hold but we also prove that, for some classes of metric spaces $M$, any injective Lipschitz map $f\colon M \to N$ (for any $N$) admits an injective linearisation. Along our way, we study how Lipschitz maps carry the support of elements in free spaces and also we provide stronger conditions on $f$ which ensure that $\widehat{f}$ is injective.

Abstract We calculate the observed luminosity and spectrum following the emergence of a relativistic shock wave from a stellar edge. Shock waves propagating at 0.6 < Γsh β sh, where Γsh is the shock Lorentz factor, and β sh is its associated reduced velocity, heat the stellar envelope to temperatures exceeding ∼50 keV, allowing for a vigorous production of electron and positron pairs. Pairs significantly increase the electron-scattering optical depth and regulate the temperature through photon generation, producing distinct observational signatures in the escaping emission. Assuming Wien equilibrium, we find analytic expressions for the temperature and pair density profiles in the envelope immediately after shock passage, and compute the emission during the expansion phase. Our analysis shows that, in pair-loaded regions, photons are produced at a roughly uniform rest-frame energy of ∼200 keV, and reinforce previous estimates that the shock breakout signal will be detected as a short burst of energetic γ-ray photons, followed by a longer phase of X-ray emission. We test our model on a sample of low-luminosity gamma-ray bursts using a closure relation between the γ-ray burst duration, the radiation temperature, and the γ-ray isotropic equivalent energy, and find that some of the events are consistent with the relativistic shock breakout model. Finally, we apply our results to explosions in white dwarfs and neutron stars, and find that typical type Ia supernovae emit ∼1041 erg in the form of ∼1 MeV photons.

Abstract Restart has the potential of expediting or impeding the completion times of general random processes. Consequently, the issue of mean-performance takes center stage: quantifying how the application of restart on a process of interest impacts its completion-time’s mean. Going beyond the mean, little is known on how restart affects stochasticity measures of the completion time. This paper is the first in a duo of studies that address this knowledge gap via: a comprehensive analysis that quantifies how sharp restart—a keystone restart protocol—impacts the Shannon entropy of the completion time. The analysis establishes closed-form results for sharp restart with general timers, with fast timers (high-frequency resetting), and with slow timers (low-frequency resetting). These results share a common structure: comparing the completion-time’s hazard rate to a flat benchmark—the constant hazard rate of an exponential distribution whose entropy is equal to the completion-time’s entropy. In addition, using an information-geometric approach based on Kullback–Leibler distances, the analysis establishes results that determine the very existence of timers with which the application of sharp restart decreases or increases the completion-time’s entropy. Our work sheds first light on the intricate interplay between restart and randomness—as gauged by the Shannon entropy.

Reliability is a fundamental requirement in any microprocessor to guarantee correct execution over its lifetime. The design rules related to reliability depend on the process technology being used and the expected operating conditions of the device. To meet reliability requirements, advanced process technologies (28 nm and below) impose highly challenging design rules. Such design-for-reliability rules have become a major burden on the flow of VLSI implementation because of the severe physical constraints they impose. This paper focuses on electromigration (EM), which is one of the major critical factors affecting semiconductor reliability. EM is the aging process of on-die wires and vias and is induced by excessive current flow that can damage wires and may also significantly impact the integrated-circuit clock frequency. EM exerts a comprehensive global effect on devices because it impacts wires that may reside inside the standard or custom logical cells, between logical cells, inside memory elements, and within wires that interconnect functional blocks. The design-implementation flow (synthesis and place-and-route) currently detects violations of EM-reliability rules and attempts to solve them. In contrast, this paper proposes a new approach to enhance these flows by using EM-aware architecture. Our results show that the proposed solution can relax EM design efforts in microprocessors and more than double microprocessor lifetime. This work demonstrates this proposed approach for modern microprocessors, although the principals and ideas can be adapted to other cases as well.

Stateful logic is a digital processing-in-memory technique that could address von Neumann memory bottleneck challenges while maintaining backward compatibility with standard von Neumann architectures. In stateful logic, memory cells are used to perform the logic operations without reading or moving any data outside the memory array. Stateful logic has been previously demonstrated using several resistive memory types, mostly by resistive RAM (RRAM). Here we present a new method to design stateful logic using a different resistive memory - phase change memory (PCM). We propose and experimentally demonstrate four logic gate types (NOR, IMPLY, OR, NIMP) using commonly used PCM materials. Our stateful logic circuits are different than previously proposed circuits due to the different switching mechanism and functionality of PCM compared to RRAM. Since the proposed stateful logic form a functionally complete set, these gates enable sequential execution of any logic function within the memory, paving the way to PCM-based digital processing-in-memory systems.

We propose a 6D RGB-D odometry approach that finds the relative camera pose between consecutive RGB-D frames by keypoint extraction and feature matching both on the RGB and depth image planes. Furthermore, we feed the estimated pose to the highly accurate KinectFusion algorithm, which uses a fast ICP (Iterative Closest Point) to fine-tune the frame-to-frame relative pose and fuse the depth data into a global implicit surface. We evaluate our method on a publicly available RGB-D SLAM benchmark dataset by Sturm et al. The experimental results show that our proposed reconstruction method solely based on visual odometry and KinectFusion outperforms the state-of-the-art RGB-D SLAM system accuracy. Moreover, our algorithm outputs a ready-to-use polygon mesh (highly suitable for creating 3D virtual worlds) without any postprocessing steps.

We initiate a study of a new model of property testing that is a hybrid of testing properties of distributions and testing properties of strings. Specifically, the new model refers to testing properties of distributions, but these are distributions over huge objects (i.e., very long strings). Accordingly, the model accounts for the total number of local probes into these objects (resp., queries to the strings) as well as for the distance between objects (resp., strings). Specifically, the distance between distributions is defined as the earth mover���s distance with respect to the relative Hamming distance between strings. We study the query complexity of testing in this new model, focusing on three directions. First, we try to relate the query complexity of testing properties in the new model to the sample complexity of testing these properties in the standard distribution testing model. Second, we consider the complexity of testing properties that arise naturally in the new model (e.g., distributions that capture random variations of fixed strings). Third, we consider the complexity of testing properties that were extensively studied in the standard distribution testing model: Two such cases are uniform distributions and pairs of identical distributions, where we obtain the following results. - Testing whether a distribution over n-bit long strings is uniform on some set of size m can be done with query complexity ��(m/����), where �� > (log���m)/n is the proximity parameter. - Testing whether two distribution over n-bit long strings that have support size at most m are identical can be done with query complexity ��(m^{2/3}/����). Both upper bounds are quite tight; that is, for �� = ��(1), the first task requires ��(m^c) queries for any c < 1 and n = ��(log m), whereas the second task requires ��(m^{2/3}) queries. Note that the query complexity of the first task is higher than the sample complexity of the corresponding task in the standard distribution testing model, whereas in the case of the second task the bounds almost match. LIPIcs, Vol. 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), pages 78:1-78:19