• We study the consensus-halving problem of dividing an object into two portions, such that each of $n$ agents has equal valuation for the two portions. The $\epsilon$-approximate consensus-halving problem allows each agent to have an $\epsilon$ discrepancy on the values of the portions. We prove that computing $\epsilon$-approximate consensus-halving solution using $n$ cuts is in PPA, and is PPAD-hard, where $\epsilon$ is some positive constant; the problem remains PPAD-hard when we allow a constant number of additional cuts. It is NP-hard to decide whether a solution with $n-1$ cuts exists for the problem. As a corollary of our results, we obtain that the approximate computational version of the Continuous Necklace Splitting Problem is PPAD-hard when the number of portions $t$ is two.
  • Ultrahigh-power terahertz (THz) radiation sources are essential for many applications, such as nonlinear THz physics, THz-wave based compact accelerators, etc. However, until now none of THz sources reported, whether based upon large-scale accelerators or high power lasers, have produced THz pulses with energies above the millijoule (mJ) barrier. Here we report on the efficient generation of low-frequency (<3 THz) THz pulses with unprecedentedly high energies over 50 mJ. The THz radiation is produced by coherent transition radiation of a picosecond laser-accelerated ultra-bright bunch of relativistic electrons from a solid target. Such high energy THz pulses can not only trigger various nonlinear dynamics in matter, but also open up a new research field of relativistic THz optics.
  • Streaking of photoelectrons with optical lasers has been widely used for temporal characterization of attosecond extreme ultraviolet pulses. Recently, this technique has been adapted to characterize femtosecond x-ray pulses in free-electron lasers with the streaking imprinted by farinfrared and Terahertz (THz) pulses. Here, we report successful implementation of THz streaking for time-stamping of an ultrashort relativistic electron beam of which the energy is several orders of magnitude higher than photoelectrons. Such ability is especially important for MeV ultrafast electron diffraction (UED) applications where electron beams with a few femtosecond pulse width may be obtained with longitudinal compression while the arrival time may fluctuate at a much larger time scale. Using this laser-driven THz streaking technique, the arrival time of an ultrashort electron beam with 6 fs (rms) pulse width has been determined with 1.5 fs (rms) accuracy. Furthermore, we have proposed and demonstrated a non-invasive method for correction of the timing jitter with femtosecond accuracy through measurement of the compressed beam energy, which may allow one to advance UED towards sub-10 fs frontier far beyond the ~100 fs (rms) jitter.
  • Solar forecasting accuracy is affected by weather conditions, and weather awareness forecasting models are expected to improve the performance. However, it may not be available and reliable to classify different forecasting tasks by using only meteorological weather categorization. In this paper, an unsupervised clustering-based (UC-based) solar forecasting methodology is developed for short-term (1-hour-ahead) global horizontal irradiance (GHI) forecasting. This methodology consists of three parts: GHI time series unsupervised clustering, pattern recognition, and UC-based forecasting. The daily GHI time series is first clustered by an Optimized Cross-validated ClUsteRing (OCCUR) method, which determines the optimal number of clusters and best clustering results. Then, support vector machine pattern recognition (SVM-PR) is adopted to recognize the category of a certain day using the first few hours' data in the forecasting stage. GHI forecasts are generated by the most suitable models in different clusters, which are built by a two-layer Machine learning based Multi-Model (M3) forecasting framework. The developed UC-based methodology is validated by using 1-year of data with six solar features. Numerical results show that (i) UC-based models outperform non-UC (all-in-one) models with the same M3 architecture by approximately 20%; (ii) M3-based models also outperform the single-algorithm machine learning (SAML) models by approximately 20%.
  • Energy efficiency and computing flexibility are some of the primary design constraints of heterogeneous computing. In this paper, we present FlashAbacus, a data-processing accelerator that self-governs heterogeneous kernel executions and data storage accesses by integrating many flash modules in lightweight multiprocessors. The proposed accelerator can simultaneously process data from different applications with diverse types of operational functions, and it allows multiple kernels to directly access flash without the assistance of a host-level file system or an I/O runtime library. We prototype FlashAbacus on a multicore-based PCIe platform that connects to FPGA-based flash controllers with a 20 nm node process. The evaluation results show that FlashAbacus can improve the bandwidth of data processing by 127%, while reducing energy consumption by 78.4%, as compared to a conventional method of heterogeneous computing. \blfootnote{This paper is accepted by and will be published at 2018 EuroSys. This document is presented to ensure timely dissemination of scholarly and technical work.
  • Long Term Evolution (LTE)-Wireless Local Area Network (WLAN) Path Aggregation (LWPA) based on Multi-path Transmission Control Protocol (MPTCP) has been under standardization procedure as a promising and cost-efficient solution to boost Downlink (DL) data rate and handle the rapidly increasing data traffic. This paper aims at providing tractable analysis for the DL performance evaluation of large-scale LWPA networks with the help of tools from stochastic geometry. We consider a simple yet practical model to determine under which conditions a native WLAN Access Point (AP) will work under LWPA mode to help increasing the received data rate. Using stochastic spatial models for the distribution of WLAN APs and LTE Base Stations (BSs), we analyze the density of active LWPA-mode WiFi APs in the considered network model, which further leads to closed-form expressions on the DL data rate and area spectral efficiency (ASE) improvement. Our numerical results illustrate the impact of different network parameters on the performance of LWPA networks, which can be useful for further performance optimization.
  • In this paper, we will consider derived equivalences for differential graded endomorphism algebras by Keller's approaches. First we construct derived equivalences of differential graded algebras which are endomorphism algebras of the objects from a triangle in the homotopy category of differential graded algebras. We also obtain derived equivalences of differential graded endomorphism algebras from a standard derived equivalence of finite dimensional algebras. Moreover, under some conditions, the cohomology rings of these differential graded endomorphism algebras are also derived equivalent. Then we give an affirmative answer to a problem of Dugas \cite{Dugas2015} in some special case.
  • We use X-ray tomography to investigate the translational and rotational dynamical heterogeneities of a three dimensional hard ellipsoids granular packing driven by oscillatory shear. We find that particles which translate quickly form clusters with a size distribution given by a power-law with an exponent that is independent of the strain amplitude. Identical behavior is found for particles that are translating slowly, rotating quickly, or rotating slowly. The geometrical properties of these four different types of clusters are the same as those of random clusters. Different cluster types are considerably correlated/anticorrelated, indicating a significant coupling between translational and rotational degrees of freedom. Surprisingly these clusters are formed already at time scales that are much shorter than the $\alpha-$relaxation time, in stark contrast to the behavior found in glass-forming systems.
  • Accelerator-based MeV ultrafast electron microscope (MUEM) has been proposed as a promising tool to study structural dynamics at the nanometer spatial scale and picosecond temporal scale. Here we report experimental tests of a prototype MUEM where high quality images with nanoscale fine structures were recorded with a pulsed 3 MeV picosecond electron beam. The temporal and spatial resolution of the MUEM operating in single-shot mode is about 4 ps (FWHM) and 100 nm (FWHM), corresponding to a temporal-spatial resolution of 4e-19 s*m, about 2 orders of magnitude higher than that achieved with state-of-the-art single-shot keV UEM. Using this instrument we offer the demonstration of visualizing the nanoscale periodic spatial modulation of an electron beam, which may be converted into longitudinal density modulation through emittance exchange to enable production of high-power coherent radiation at short wavelengths. Our results mark a great step towards single-shot nanometer-resolution MUEMs and compact intense x-ray sources that may have wide applications in many areas of science.
  • Coulomb interaction between charged particles is a well-known phenomenon in many areas of researches. In general the Coulomb repulsion force broadens the pulse width of an electron bunch and limits the temporal resolution of many scientific facilities such as ultrafast electron diffraction and x-ray free-electron lasers. Here we demonstrate a scheme that actually makes use of Coulomb force to compress a relativistic electron beam. Furthermore, we show that the Coulomb-driven bunch compression process does not introduce additional timing jitter, which is in sharp contrast to the conventional radio-frequency buncher technique. Our work not only leads to enhanced temporal resolution in electron beam based ultrafast instruments that may provide new opportunities in probing material systems far from equilibrium, but also opens a promising direction for advanced beam manipulation through self-field interactions.
  • With the increasing penetration of solar power into power systems, forecasting becomes critical in power system operations. In this paper, an hourly-similarity (HS) based method is developed for 1-hour-ahead (1HA) global horizontal irradiance (GHI) forecasting. This developed method utilizes diurnal patterns, statistical distinctions between different hours, and hourly similarities in solar data to improve the forecasting accuracy. The HS-based method is built by training multiple two-layer multi-model forecasting framework (MMFF) models independently with the same-hour subsets. The final optimal model is a combination of MMFF models with the best-performed blending algorithm at every hour. At the forecasting stage, the most suitable model is selected to perform the forecasting subtask of a certain hour. The HS-based method is validated by 1-year data with six solar features collected by the National Renewable Energy Laboratory (NREL). Results show that the HS-based method outperforms the non-HS (all-in-one) method significantly with the same MMFF architecture, wherein the optimal HS- based method outperforms the best all-in-one method by 10.94% and 7.74% based on the normalized mean absolute error and normalized root mean square error, respectively.
  • Large-scale solar eruptions have been extensively explored over many years. However, the properties of small-scale events with associated shocks have been rarely investigated. We present the analyses of a small-scale short-duration event originating from a small region. The impulsive phase of the M1.9-class flare lasted only for four minutes. The kinematic evolution of the CME hot channel reveals some exceptional characteristics including a very short duration of the main acceleration phase ($<$ 2 minutes), a rather high maximal acceleration rate ($\sim$50 km s$^{-2}$) and peak velocity ($\sim$1800 km s$^{-1}$). The fast and impulsive kinematics subsequently results in a piston-driven shock related to a metric type II radio burst with a high starting frequency of $\sim$320 MHz of the fundamental band. The type II source is formed at a low height of below $1.1~\mathrm{R_{\odot}}$ less than $\sim2$ minutes after the onset of the main acceleration phase. Through the band split of the type II burst, the shock compression ratio decreases from 2.2 to 1.3, and the magnetic field strength of the shock upstream region decreases from 13 to 0.5 Gauss at heights of 1.1 to 2.3 $~\mathrm{R_{\odot}}$. We find that the CME ($\sim4\times10^{30}\,\mathrm{erg}$) and flare ($\sim1.6\times10^{30}\,\mathrm{erg}$) consume similar amount of magnetic energy. The same conclusion for large-scale eruptions implies that small- and large-scale events possibly share the similar relationship between CMEs and flares. The kinematic particularities of this event are possibly related to the small footpoint-separation distance of the associated magnetic flux rope, as predicted by the Erupting Flux Rope model.
  • We study $d$-variate problem in the average case setting with respect to a zero-mean Gaussian measure. The covariance kernel of this Gaussian measure is a product of univariate kernels and satisfies some special properties. We study $(s, t)$-weak tractability of this multivariate problem, and obtain a necessary and sufficient condition for $s>0$ and $t\in(0,1)$. Our result can apply to the problems with covariance kernels corresponding to Euler and Wiener integrated processes, Korobov kernels, and analytic Korobov kernels.
  • We consider the polytope arising from a marked surface by flips of triangulations. Sleator, Tarjan and Thurston studied in 1988 the diameter of the associahedron, which is the polytope arising from a marked disc by flips of triangulations. They showed that every shortest path between two vertices in a face does not leave that face. We establish that same non-leaving-face property for all unpunctured marked surfaces.
  • Handling bugs is an essential part of software development. The impact of programming language on this task has long been a topic of much debate. For example, some people hold the view that bugs in Python are easy to handle because its code is easy to read and understand, while some others believe the absence of static typing in Python will lead to higher bug-handling effort. This paper presents the first large-scale study to investigate whether the ecosystems of different (categories of) programming language would require different bug-handling effort. The focus is on correlation analysis rather than causal analysis. With 600 most popular projects in 10 languages downloaded from GitHub (summing up to 70,816,938 SLOC and 3,096,009 commits), the experimental results indicate various interesting findings. First, different languages require different bug-handling effort. For example, Java and C# tend to require less time but more line/file modification, Python and PHP tend to require less time and less line/file modification, while Ruby and JavaScript tend to require more time as well as more line/file modification. Second, weak/dynamic languages tend to require more time than strong/static languages, while static languages tend to require more absolute line/file modification. A toy predictive model also provides proof that the inclusion of programming languages could improve the effectiveness when predicting the bug-handling effort of a project.
  • Spreadsheets are the most popular end-user programming software, where formulae act like programs and also have smells. One well recognized common smell of spreadsheet formulae is nest-IF expressions, which have low readability and high cognitive cost for users, and are error-prone during reuse or maintenance. However, end users usually lack essential programming language knowledge and skills to tackle or even realize the problem. The previous research work has made very initial attempts in this aspect, while no effective and automated approach is currently available. This paper firstly proposes an AST-based automated approach to systematically refactoring nest-IF formulae. The general idea is two-fold. First, we detect and remove logic redundancy on the AST. Second, we identify higher-level semantics that have been fragmented and scattered, and reassemble the syntax using concise built-in functions. A comprehensive evaluation has been conducted against a real-world spreadsheet corpus, which is collected in a leading IT company for research purpose. The results with over 68,000 spreadsheets with 27 million nest-IF formulae reveal that our approach is able to relieve the smell of over 99\% of nest-IF formulae. Over 50% of the refactorings have reduced nesting levels of the nest-IFs by more than a half. In addition, a survey involving 49 participants indicates that for most cases the participants prefer the refactored formulae, and agree on that such automated refactoring approach is necessary and helpful.
  • The availability of intense, ultrashort coherent radiation sources in the infrared region of the spectrum is enabling the generation of attosecond X-ray pulses via high harmonic generation, pump-probe experiments in the "molecular fingerprint" region and opening up the area of relativistic-infrared nonlinear optics of plasmas. These applications would benefit from multi-millijoule single-cycle pulses in the mid to long wavelength infrared (LW-IR) region. Here we present a new scheme capable of producing tunable relativistically intense, single-cycle infrared pulses from 5-14$\mu$m with a 1.7% conversion efficiency based on a photon frequency downshifting scheme that uses a tailored plasma density structure. The carrier-envelope phase (CEP) of the LW-IR pulse is locked to that of the drive laser to within a few percent. Such a versatile tunable IR source may meet the demands of many cutting-edge applications in strong-field physics and greatly promote their development.
  • Compact acceleration of a tightly collimated relativistic electron beam with high charge from a laser-plasma interaction has many unique applications. However, currently the well-known schemes, including laser wakefield acceleration from gases and vacuum laser acceleration from solids, often produce electron beams either with low charge or with large divergence angles. In this work, we report the generation of highly collimated electron beams with a divergence angle of a few degrees, quasi-monoenergetic spectra peaked at the MeV level, and extremely high charge ($\sim$100 nC) via a powerful sub-ps laser pulse interacting with a solid target in grazing incidence. Particle-in-cell simulations illustrate a new direct laser acceleration scenario, in which the self-filamentation is triggered in a large-scale near-critical-density plasma and electron bunches are accelerated periodically and collimated by the ultra-intense electromagnetic field. The energy density of such electron beams in high-Z materials reaches to $\sim10^{12} \mathrm{J/m^{3}}$, making it a promising tool to drive warm or even hot dense matter states.
  • Granular materials such as sand, powders, foams etc. are ubiquitous in our daily life, as well as in industrial and geotechnical applications. Although these disordered systems form stable structures if unperturbed, in practice they do relax because of the presence of unavoidable external influences such as tapping or shear. Often it is tacitly assumed that for granular systems this relaxation dynamics is similar to the one of thermal glass-formers, but in fact experimental difficulties have so far prevented to determine the dynamic properties of three dimensional granular systems on the particle level. This lack of experimental data, combined with the fact that in these systems the motion of the particles involves friction, makes it very challenging to come up with an accurate description of their relaxation dynamics. Here we use X-ray tomography to determine the microscopic relaxation dynamics of hard granular ellipsoids that are subject to an oscillatory shear. We find that the distribution function of the particle displacement can be described by a Gumbel law with a shape parameter that is independent of time and the strain amplitude $\gamma$. Despite this universality, the mean squared displacement of a tagged particle shows power-laws as a function of time with an exponent that depends on $\gamma$ and the time interval considered. We argue that these results are directly related to the existence of the microscopic relaxation mechanisms that involve friction and memory effects. These observations demonstrate that on the particle level the dynamical behavior of granular systems is qualitatively different from the one of thermal glass-formers and instead more similar to the one of complex fluids. Thus we conclude that granular materials can relax even when the driving is weak, an insight which impacts our understanding of the nature of granular solids.
  • The Faraday effect, caused by a magnetic-field-induced change in the optical properties, takes place in a vast variety of systems from a single atomic layer of graphenes to huge galaxies. Currently, it plays a pivot role in many applications such as the manipulation of light and the probing of magnetic fields and material's properties. Basically, this effect causes a polarization rotation of light during its propagation along the magnetic field in a medium. Here, we report an extreme case of the Faraday effect where a linearly polarized ultrashort laser pulse splits in time into two circularly polarized pulses of opposite handedness during its propagation in a highly magnetized plasma. This offers a new degree of freedom for manipulating ultrashort and ultrahigh power laser pulses. Together with technologies of ultra-strong magnetic fields, it may pave the way for novel optical devices, such as magnetized plasma polarizers. In addition, it may offer a powerful means to measure strong magnetic fields in laser-produced plasmas.
  • Single-Radio-Frequency (RF) Multiple-Input-Multiple-Output (MIMO) systems such as the spatial modulation (SM) system and the space shift keying (SSK) system have been proposed to pursue a high spectral efficiency while keeping a low cost and complexity transceiver design. Currently, polarization domain resource has been introduced to the single-RF MIMO system to reduce the size of the transmit antenna array and provide 1 bit per channel use (bpcu) multiplexing gain. Nevertheless, the polarization domain resource still has the potential to provide a higher multiplexing gain in the polarized single-RF MIMO system. In this paper, we propose a generalized polarization shift keying (PolarSK) modulation scheme for a SIMO system that uses the polarization states in the dual-polarized transmit antenna as an information-bearing unit to increase the overall spectral efficiency. At the receive end, the maximum likelihood (ML) detector is employed to demodulate the received signal. A closed form union upper bound on the average bit error probability (ABEP) of PolarSK system with the optimum maximum likelihood (ML) receiver is deduced under fading channels. To reduce the computational complexity of the receiver, a linear successive interference cancellation (SIC) detection algorithm and a sphere-decoding (SD) detection algorithm are proposed. On the basis of analytic results and simulations, performances of the proposed PolarSK systems in terms of computational complexity and ABEP are analyzed. Numerical results show that the proposed PolarSK scheme performs better than state of the art dual-polarized/uni-polarized SM schemes.
  • We simultaneously measure photoresistance with electrical transport and plasmon-cyclotron resonance (PCR) using microwave reflection spectroscopy in high mobility GaAs/AlGaAs quantum wells under a perpendicular magnetic field. Multi-photon transitions are revealed as sharp peaks in the resistance and the cyclotron reflection on samples with various carrier densities. Our main finding is that plasmon coupling is relevant in the cyclotron reflection spectrum but has not been observed in the electrical conductivity signal. We discuss possible mechanisms relevant to reflection or dc conductivity signal to explain this discrepancy. We further confirm a trend that higher order multi-photon features can be observed using higher carrier density samples.
  • We report a new scenario of time-of-flight (TOF) technique in which fast neutrons and delayed gamma-ray signals were both recorded in a millisecond time window in harsh environments induced by high-intensity lasers. The delayed gamma signals, arriving far later than the original fast neutron and often being ignored previously, were identified to be the results of radiative captures of thermalized neutrons. The linear correlation between gamma photon number and the fast neutron yield shows that these delayed gamma events can be employed for neutron diagnosis. This method can reduce the detecting efficiency dropping problem caused by prompt high-flux gamma radiation, and provides a new way for neutron diagnosing in high-intensity laser-target interaction experiments.
  • Large-scale systems with arrays of solid state disks (SSDs) have become increasingly common in many computing segments. To make such systems resilient, we can adopt erasure coding such as Reed-Solomon (RS) code as an alternative to replication because erasure coding can offer a significantly lower storage cost than replication. To understand the impact of using erasure coding on system performance and other system aspects such as CPU utilization and network traffic, we build a storage cluster consisting of approximately one hundred processor cores with more than fifty high-performance SSDs, and evaluate the cluster with a popular open-source distributed parallel file system, Ceph. Then we analyze behaviors of systems adopting erasure coding from the following five viewpoints, compared with those of systems using replication: (1) storage system I/O performance; (2) computing and software overheads; (3) I/O amplification; (4) network traffic among storage nodes; (5) the impact of physical data layout on performance of RS-coded SSD arrays. For all these analyses, we examine two representative RS configurations, which are used by Google and Facebook file systems, and compare them with triple replication that a typical parallel file system employs as a default fault tolerance mechanism. Lastly, we collect 54 block-level traces from the cluster and make them available for other researchers.
  • Block traces are widely used for system studies, model verifications, and design analyses in both industry and academia. While such traces include detailed block access patterns, existing trace-driven research unfortunately often fails to find true-north due to a lack of runtime contexts such as user idle periods and system delays, which are fundamentally linked to the characteristics of target storage hardware. In this work, we propose TraceTracker, a novel hardware/software co-evaluation method that allows users to reuse a broad range of the existing block traces by keeping most their execution contexts and user scenarios while adjusting them with new system information. Specifically, our TraceTracker's software evaluation model can infer CPU burst times and user idle periods from old storage traces, whereas its hardware evaluation method remasters the storage traces by interoperating the inferred time information, and updates all inter-arrival times by making them aware of the target storage system. We apply the proposed co-evaluation model to 577 traces, which were collected by servers from different institutions and locations a decade ago, and revive the traces on a high-performance flash-based storage array. The evaluation results reveal that the accuracy of the execution contexts reconstructed by TraceTracker is on average 99% and 96% with regard to the frequency of idle operations and the total idle periods, respectively.