Showing 1–34 of 34 results for author: Bazzi, A

Sum Secrecy Rate Maximization for Full Duplex ISAC Systems

Authors: Aleksandar Boljević, Ahmad Bazzi, Marwa Chafii

Abstract: In integrated sensing and communication (ISAC) systems, the target of interest may \textit{intentionally disguise itself as an eavesdropper}, enabling it to intercept and tap into the communication data embedded in the ISAC waveform. The following paper considers a full duplex (FD)-ISAC system, which involves multiple malicious targets attempting to intercept both uplink (UL) and downlink (DL) com… ▽ More In integrated sensing and communication (ISAC) systems, the target of interest may \textit{intentionally disguise itself as an eavesdropper}, enabling it to intercept and tap into the communication data embedded in the ISAC waveform. The following paper considers a full duplex (FD)-ISAC system, which involves multiple malicious targets attempting to intercept both uplink (UL) and downlink (DL) communications between the dual-functional radar and communication (DFRC) base station (BS) and legitimate UL/DL communication users (CUs). For this, we formulate an optimization framework that allows maximization of both UL and DL sum secrecy rates, under various power budget constraints for sensing and communications. As the proposed optimization problem is non-convex, we develop a method called Iterative Joint Taylor-Block cyclic coordinate descent (IJTB) by proving essential lemmas that transform the original problem into a more manageable form. In essence, IJTB alternates between two sub-problems: one yields UL beamformers in closed-form, while the other approximates the solution for UL power allocation, artificial noise covariance, and DL beamforming vectors. This is achieved through a series of Taylor approximations that effectively \textit{"convexify"} the problem, enabling efficient optimization. Simulation results demonstrate the effectiveness of the proposed solver when compared with benchmarking ones. Our findings reveal that the IJTB algorithm shows fast convergence, reaching stability within approximately $10$ iterations. In addition, all benchmarks reveal a substantial decline in the sum secrecy rate, approaching zero as the eavesdropper distance reaches $17$ meters, underscoring their vulnerability in comparison to IJTB. △ Less

Submitted 16 October, 2024; originally announced October 2024.

DRIP: A Versatile Family of Space-Time ISAC Waveforms

Authors: Dexin Wang, Ahmad Bazzi, Marwa Chafii

Abstract: The following paper introduces Dual beam-similarity awaRe Integrated sensing and communications (ISAC) with controlled Peak-to-average power ratio (DRIP) waveforms. DRIP is a novel family of space-time ISAC waveforms designed for dynamic peak-to-average power ratio (PAPR) adjustment. The proposed DRIP waveforms are designed to conform to specified PAPR levels while exhibiting beampattern propertie… ▽ More The following paper introduces Dual beam-similarity awaRe Integrated sensing and communications (ISAC) with controlled Peak-to-average power ratio (DRIP) waveforms. DRIP is a novel family of space-time ISAC waveforms designed for dynamic peak-to-average power ratio (PAPR) adjustment. The proposed DRIP waveforms are designed to conform to specified PAPR levels while exhibiting beampattern properties, effectively targeting multiple desired directions and suppressing interference for multi-target sensing applications, while closely resembling radar chirps. For communication purposes, the proposed DRIP waveforms aim to minimize multi-user interference across various constellations. Addressing the non-convexity of the optimization framework required for generating DRIP waveforms, we introduce a block cyclic coordinate descent algorithm. This iterative approach ensures convergence to an optimal ISAC waveform solution. Simulation results validate the DRIP waveforms' superior performance, versatility, and favorable ISAC trade-offs, highlighting their potential in advanced multi-target sensing and communication systems. △ Less

Submitted 16 October, 2024; originally announced October 2024.

Multi-Functional RIS for a Multi-Functional System: Integrating Sensing, Communication, and Wireless Power Transfer

Authors: Ahmed Magbool, Vaibhav Kumar, Ahmad Bazzi, Mark F. Flanagan, Marwa Chafii

Abstract: Communication networks are evolving from solely emphasizing communication to facilitating multiple functionalities. In this regard, integrated sensing, communication, and powering (ISCAP) provides an efficient way of enabling data transmission, radar sensing, and wireless power transfer simultaneously. Such a multi-functional network requires a multi-functional architectural solution. Toward this… ▽ More Communication networks are evolving from solely emphasizing communication to facilitating multiple functionalities. In this regard, integrated sensing, communication, and powering (ISCAP) provides an efficient way of enabling data transmission, radar sensing, and wireless power transfer simultaneously. Such a multi-functional network requires a multi-functional architectural solution. Toward this end, sensor-aided zero-energy reconfigurable intelligent surfaces (SAZE-RISs) offer an energy-efficient solution for ISCAP by meeting the requirements of the end users as well as supplying power for the RIS. This paper explores the use of SAZE-RIS within the ISCAP framework. First, we present the general system architecture, operational protocols, and main application scenarios for employing SAZE-RIS in ISCAP. Next, we discuss methods for managing the conflicting requirements of communication, sensing, and powering within ISCAP and the role of SAZE-RIS in this process. We then provide a detailed case study complete with simulation results, offering valuable insights into the design choices and tradeoffs that come into play when adopting this technology. Furthermore, we discuss the related challenges and open research avenues, highlighting areas that require further exploration to fully realize the potential of SAZE-RIS within this ISCAP framework. △ Less

Submitted 11 October, 2024; originally announced October 2024.

Comments: Accepted for publication in IEEE Network

Layered Chirp Spread Spectrum Modulations for LPWANs

Authors: Ali Waqar Azim, Ahmad Bazzi, Roberto Bomfin, Raed Shubair, Marwa Chafii

Abstract: This article examines two chirp spread spectrum techniques specifically devised for low-power wide-area networks (LPWANs) to optimize energy and spectral efficiency (SE). These methods referred to as layered CSS (LCSS) and layered dual-mode CSS (LDMCSS), involves utilizing multiple layers for multiplexing symbols with varying chirp rates. These waveform designs exemplify a high degree of SE compar… ▽ More This article examines two chirp spread spectrum techniques specifically devised for low-power wide-area networks (LPWANs) to optimize energy and spectral efficiency (SE). These methods referred to as layered CSS (LCSS) and layered dual-mode CSS (LDMCSS), involves utilizing multiple layers for multiplexing symbols with varying chirp rates. These waveform designs exemplify a high degree of SE compared to existing schemes. Additionally, LDMCSS necessitates a lesser number of layers than LCSS to attain comparable SE, thereby reducing computational complexity. These proposed techniques can employ coherent and non-coherent detection and can be adjusted to achieve various spectral efficiencies by altering the number of multiplexed layers. Unlike our proposed LCSS and LDMCSS, other CSS alternatives for LPWANs cannot provide the same level of flexibility and SE. The performance of these techniques is evaluated in terms of bit error rate under different channel conditions, as well as with phase and frequency offsets. △ Less

Submitted 29 May, 2024; originally announced May 2024.

Journal ref: IEEE Transactions on Communications, Vol 72, Issue 3, March 2024

Complex Neural Network based Joint AoA and AoD Estimation for Bistatic ISAC

Authors: Salmane Naoumi, Ahmad Bazzi, Roberto Bomfin, Marwa Chafii

Abstract: Integrated sensing and communication (ISAC) in wireless systems has emerged as a promising paradigm, offering the potential for improved performance, efficient resource utilization, and mutually beneficial interactions between radar sensing and wireless communications, thereby shaping the future of wireless technologies. In this work, we present two novel methods to address the joint angle of arri… ▽ More Integrated sensing and communication (ISAC) in wireless systems has emerged as a promising paradigm, offering the potential for improved performance, efficient resource utilization, and mutually beneficial interactions between radar sensing and wireless communications, thereby shaping the future of wireless technologies. In this work, we present two novel methods to address the joint angle of arrival and angle of departure estimation problem for bistatic ISAC systems. Our proposed methods consist of a deep learning (DL) solution leveraging complex neural networks, in addition to a parameterized algorithm. By exploiting the estimated channel matrix and incorporating a preprocessing step consisting of a coarse timing estimation, we are able to notably reduce the input size and improve the computational efficiency. In our findings, we emphasize the remarkable potential of our DL-based approach, which demonstrates comparable performance to the parameterized method that explicitly exploits the multiple-input multiple-output (MIMO) model, while exhibiting significantly lower computational complexity. △ Less

Submitted 31 March, 2024; originally announced April 2024.

Comments: IEEE Journal of Selected Topics in Signal Processing

RIS-Enabled Integrated Sensing and Communication for 6G Systems

Authors: Dexin Wang, Ahmad Bazzi, Marwa Chafii

Abstract: The following paper proposes a new target localization system design using an architecture based on reconfigurable intelligent surfaces (RISs) and passive radars (PRs) for integrated sensing and communications systems. The preamble of the communication signal is exploited in order to perform target sensing tasks, which involve detection and localization. The RIS in this case can aid the PR in sens… ▽ More The following paper proposes a new target localization system design using an architecture based on reconfigurable intelligent surfaces (RISs) and passive radars (PRs) for integrated sensing and communications systems. The preamble of the communication signal is exploited in order to perform target sensing tasks, which involve detection and localization. The RIS in this case can aid the PR in sensing targets that are otherwise not seen by the PR itself, due to the many obstacles encountered within the propagation channel. Therefore, this work proposes a localization algorithm tailored for the integrated sensing and communications RIS-aided architecture, which is capable of uniquely positioning targets within the scene. The algorithm is capable of detecting the number of targets along with estimating the position of targets via angles and times of arrival. Our simulation results demonstrate the performance of the localization method in terms of different localization and detection metrics and for increasing RIS sizes. △ Less

Submitted 31 December, 2023; originally announced January 2024.

Journal ref: IEEE Wireless Communications and Networking Conference, 2024

Secure Full Duplex Integrated Sensing and Communications

Authors: Ahmad Bazzi, Marwa Chafii

Abstract: The following paper models a secure full duplex (FD) integrated sensing and communication (ISAC) scenario, where malicious eavesdroppers aim at intercepting the downlink (DL) as well as the uplink (UL) information exchanged between the dual functional radar and communication (DFRC) base station (BS) and a set of communication users. The DFRC BS, on the other hand, aims at illuminating radar beams… ▽ More The following paper models a secure full duplex (FD) integrated sensing and communication (ISAC) scenario, where malicious eavesdroppers aim at intercepting the downlink (DL) as well as the uplink (UL) information exchanged between the dual functional radar and communication (DFRC) base station (BS) and a set of communication users. The DFRC BS, on the other hand, aims at illuminating radar beams at the eavesdroppers in order to sense their physical parameters, while maintaining high UL/DL secrecy rates. Based on the proposed model, we formulate a power efficient secure ISAC optimization framework design, which is intended to guarantee both UL and DL secrecy rates requirements, while illuminating radar beams towards eavesdroppers. The framework exploits artificial noise (AN) generation at the DFRC BS, along with UL/DL beamforming design and UL power allocation. We propose a beamforming design solution to the secure ISAC optimization problem. Finally, we corroborate our findings via simulation results and demonstrate the feasibility, as well as the superiority of the proposed algorithm, under different situations. We also reveal insightful trade-offs achieved by our approach. △ Less

Submitted 18 December, 2023; originally announced December 2023.

Analytical Investigation of Two Benchmark Resource Allocation Algorithms for LTE-V2V

Authors: A. Bazzi, A. Zanella, G. Cecchini, B. M. Masini

Abstract: Short-range wireless technologies will enable vehicles to communicate and coordinate their actions, thus improving people's safety and traffic efficiency. Whereas IEEE 802.11p (and related standards) had been the only practical solution for years, in 2016 a new option was introduced with Release 14 of long term evolution (LTE), which includes new features to enable direct vehicle-to-vehicle (V2V)… ▽ More Short-range wireless technologies will enable vehicles to communicate and coordinate their actions, thus improving people's safety and traffic efficiency. Whereas IEEE 802.11p (and related standards) had been the only practical solution for years, in 2016 a new option was introduced with Release 14 of long term evolution (LTE), which includes new features to enable direct vehicle-to-vehicle (V2V) communications. LTE-V2V promises a more efficient use of the channel compared to IEEE 802.11p thanks to an improved PHY layer and the use of orthogonal resources at the MAC layer. In LTE-V2V, a key role is played by the resource allocation algorithm and increasing efforts are being made to design new solutions to optimize the spatial reuse.In this context, an important aspect still little studied, is therefore that of identifying references that allow: 1) to have a perception of the space in which the resource allocation algorithms move; and 2) to verify the performance of new proposals. In this work, we focus on a highway scenario and identify two algorithms to be used as a minimum and maximum reference in terms of the packet reception probability (PRP). The PRP is derived as a function of various parameters that describe the scenario and settings, from the application to the physical layer. Results, obtained both in a simplified Poisson point process scenario and with realistic traffic traces, show that the PRP varies considerably with different algorithms and that there is room for the improvement of current solutions. △ Less

Submitted 14 July, 2023; originally announced July 2023.

Mutual Information Based Pilot Design for ISAC

Authors: Ahmad Bazzi, Marwa Chafii

Abstract: The following paper presents a novel orthogonal pilot design dedicated for dual-functional radar and communication (DFRC) systems performing multi-user communications and target detection. After careful characterization of both sensing and communication metrics based on mutual information (MI), we propose a multi-objective optimization problem (MOOP) tailored for pilot design, dedicated for simult… ▽ More The following paper presents a novel orthogonal pilot design dedicated for dual-functional radar and communication (DFRC) systems performing multi-user communications and target detection. After careful characterization of both sensing and communication metrics based on mutual information (MI), we propose a multi-objective optimization problem (MOOP) tailored for pilot design, dedicated for simultaneously maximizing both sensing and communication MIs. Moreover, the MOOP is further simplified to a single-objective optimization problem, which characterizes trade-offs between sensing and communication performances. Due to the non-convex nature of the optimization problem, we propose to solve it via the projected gradient descent method on the Stiefel manifold. Closed-form gradient expressions are derived, which enable execution of the projected gradient descent algorithm. Furthermore, we prove convergence to a fixed orthogonal pilot matrix. Finally, we demonstrate the capabilities and superiority of the proposed pilot design, and corroborate relevant trade-offs between sensing MI and communication MI. In particular, significant signal-to-noise ratio (SNR) gains for communication are reported, while re-using the same pilots for target detection with significant gains in terms of probability of detection for fixed false-alarm probability. Other interesting findings are reported through simulations, such as an \textit{information overlap} phenomenon, whereby the fruitful ISAC integration can be fully exploited. △ Less

Submitted 22 June, 2023; originally announced June 2023.

Multi-Channel Operation for the Release 2 of ETSI Cooperative Intelligent Transport Systems

Authors: Alessandro Bazzi, Miguel Sepulcre, Quentin Delooz, Andreas Festag, Jonas Vogt, Horst Wieker, Friedbert Berens, Paul Spaanderman

Abstract: Vehicles and road infrastructure are starting to be equipped with vehicle-to-everything (V2X) communication solutions to increase road safety and provide new services to drivers and passengers. In Europe, the deployment is based on a set of Release 1 standards developed by ETSI to support basic use cases for cooperative intelligent transport systems (C-ITS). For them, the capacity of a single 10 M… ▽ More Vehicles and road infrastructure are starting to be equipped with vehicle-to-everything (V2X) communication solutions to increase road safety and provide new services to drivers and passengers. In Europe, the deployment is based on a set of Release 1 standards developed by ETSI to support basic use cases for cooperative intelligent transport systems (C-ITS). For them, the capacity of a single 10 MHz channel in the ITS band at 5.9 GHz is considered sufficient. At the same time, the ITS stakeholders are working towards several advanced use cases, which imply a significant increment of data traffic and the need for multiple channels. To address this issue, ETSI has recently standardized a new multi-channel operation (MCO) concept for flexible, efficient, and future-proof use of multiple channels. This new concept is defined in a set of new specifications that represent the foundation for the future releases of C-ITS standards. The present paper provides a comprehensive review of the new set of specifications, describing the main entities extending the C-ITS architecture at the different layers of the protocol stack, In addition, the paper provides representative examples that describe how these MCO standards will be used in the future and discusses some of the main open issues arising. The review and analysis of this paper facilitate the understanding and motivation of the new set of Release 2 ETSI specifications for MCO and the identification of new research opportunities. △ Less

Submitted 31 May, 2023; originally announced May 2023.

Deep Learning-based Estimation for Multitarget Radar Detection

Authors: Mamady Delamou, Ahmad Bazzi, Marwa Chafii, El Mehdi Amhoud

Abstract: Target detection and recognition is a very challenging task in a wireless environment where a multitude of objects are located, whether to effectively determine their positions or to identify them and predict their moves. In this work, we propose a new method based on a convolutional neural network (CNN) to estimate the range and velocity of moving targets directly from the range-Doppler map of th… ▽ More Target detection and recognition is a very challenging task in a wireless environment where a multitude of objects are located, whether to effectively determine their positions or to identify them and predict their moves. In this work, we propose a new method based on a convolutional neural network (CNN) to estimate the range and velocity of moving targets directly from the range-Doppler map of the detected signals. We compare the obtained results to the two dimensional (2D) periodogram, and to the similar state of the art methods, 2DResFreq and VGG-19 network and show that the estimation process performed with our model provides better estimation accuracy of range and velocity index in different signal to noise ratio (SNR) regimes along with a reduced prediction time. Afterwards, we assess the performance of our proposed algorithm using the peak signal to noise ratio (PSNR) which is a relevant metric to analyse the quality of an output image obtained from compression or noise reduction. Compared to the 2D-periodogram, 2DResFreq and VGG-19, we gain 33 dB, 21 dB and 10 dB, respectively, in terms of PSNR when SNR = 30 dB. △ Less

Submitted 5 May, 2023; originally announced May 2023.

Comments: 5 pages , 4 figures

Robust Integrated Sensing and Communication Beamforming for Dual-functional Radar and Communications: Method and Insights

Authors: Ahmad Bazzi, Marwa Chafii

Abstract: This work presents a novel robust beamforming design dedicated for dual-functional radar and communication (DFRC) base stations (BSs) in the context of integrated sensing and communications (ISAC). The architecture is intended for circumstances with imperfect channel state information (CSI). Our suggested approach demonstrates several tradeoffs for joint radar-communication deployment. Due to the… ▽ More This work presents a novel robust beamforming design dedicated for dual-functional radar and communication (DFRC) base stations (BSs) in the context of integrated sensing and communications (ISAC). The architecture is intended for circumstances with imperfect channel state information (CSI). Our suggested approach demonstrates several tradeoffs for joint radar-communication deployment. Due to the DFRC nature of the design, the beamformer can simultaneously point towards an intended target, while optimizing communication quality of service. We unveil several insights regarding closed form expressions, as well as optimality of the proposed beamformer. Lastly, simulation results demonstrate the effectiveness of the proposed ISAC beamformer. △ Less

Submitted 14 March, 2023; originally announced March 2023.

Comments: arXiv admin note: text overlap with arXiv:2207.04921

On Hybrid Radar Fusion for Integrated Sensing and Communication

Authors: Akhileswar Chowdary, Ahmad Bazzi, Marwa Chafii

Abstract: The following paper introduces a novel integrated sensing and communication (ISAC) scenario termed hybrid radar fusion. In this setting, the dual-functional radar and communications (DFRC) base station (BS) acts as a mono-static radar in the downlink (DL), for sensing purposes, while performing its DL communication tasks. Meanwhile, the communication users act as distributed bi-static radar nodes… ▽ More The following paper introduces a novel integrated sensing and communication (ISAC) scenario termed hybrid radar fusion. In this setting, the dual-functional radar and communications (DFRC) base station (BS) acts as a mono-static radar in the downlink (DL), for sensing purposes, while performing its DL communication tasks. Meanwhile, the communication users act as distributed bi-static radar nodes in the uplink (UL) following a frequency-division duplex protocol. The DFRC BS fuses the information available at different DL and UL resource bands to estimate the angles-of-arrival (AoAs) of the multiple targets existing in the scene. In this work, we derive the maximum likelihood (ML) criterion for the hybrid radar fusion problem at hand. Additionally, we design efficient estimators; the first algorithm is based on an alternating optimization approach to solve the ML criterion, while the second one designs an optimization framework that leads to an alternating subspace approach to estimate AoAs for both the target and users. Finally, we demonstrate the superior performance of both algorithms in different scenarios, and the gains offered by these proposed methods through numerical simulations. △ Less

Submitted 18 January, 2024; v1 submitted 10 March, 2023; originally announced March 2023.

Breaking the $f+1$ Barrier: Executing Payment Transactions in Parallel with Less than $f+1$ Validations

Authors: Rida A. Bazzi, Sara Tucci-Piergiovanni

Abstract: We consider the problem of supporting payment transactions in an asynchronous system in which up to $f$ validators are subject to Byzantine failures under the control of an adaptive adversary. It was shown that this problem can be solved without consensus by using byzantine quorum systems (requiring at least $2f+1$ validations per transaction in asynchronous systems). We show that it is possible t… ▽ More We consider the problem of supporting payment transactions in an asynchronous system in which up to $f$ validators are subject to Byzantine failures under the control of an adaptive adversary. It was shown that this problem can be solved without consensus by using byzantine quorum systems (requiring at least $2f+1$ validations per transaction in asynchronous systems). We show that it is possible to validate transactions in parallel with less than $f$ validations per transaction if each transaction spends no more that a small fraction of a balance. Our solution relies on a novel quorum system that we introduce in this paper and that we call $(k_1,k_2)$-quorum systems. In the presence of a non-adaptive adversary, these systems can be used to allow up to $k_1$ transactions to be validated concurrently and asynchronously but prevent more than $k_2$ transactions from being validated. If the adversary is adaptive, these systems can be used to allow $k_1$ transaction to be validated and prevent more than $k'_2 > k_2$ transactions from being validated, the difference $k'_2-k_2$ being dependent on the quorum system's {\em validation slack}, which we define in this paper. Using $(k_1,k_2)$-quorum systems, a payer can execute multiple partial spending transactions to spend a portion of its initial balance with less than full quorum validation (less than $f$ validations per transaction) then reclaim any remaining funds using one fully validated transaction, which we call a {\em settlement} transaction. △ Less

Submitted 24 January, 2023; originally announced January 2023.

Comments: 26 pages, 2 figures

RIS-Enabled Passive Radar towards Target Localization

Authors: Ahmad Bazzi, Marwa Chafii

Abstract: In this paper, we study a communication-centric integrated sensing and communication (ISAC) approach, where an access point (AP) communicates with users, while a passive radar (PR) is present in the environment. We investigate the deployment of a reconfigurable intelligent surface (RIS) to enable the PR to localize a target. We derive an optimization problem for updating the phase shifters of the… ▽ More In this paper, we study a communication-centric integrated sensing and communication (ISAC) approach, where an access point (AP) communicates with users, while a passive radar (PR) is present in the environment. We investigate the deployment of a reconfigurable intelligent surface (RIS) to enable the PR to localize a target. We derive an optimization problem for updating the phase shifters of the RIS per epoch. Due to the limited information at the PR, such as unknown payload information and unknown number of targets in the scene, we propose two methods capable of performing joint angle of arrival estimation and detection of the targets. We demonstrate the superior performance of the methods onto the proposed setting through numerical simulations, in comparison to a no-RIS baseline scheme. △ Less

Submitted 21 October, 2022; originally announced October 2022.

Dual-Mode Time Domain Multiplexed Chirp Spread Spectrum

Authors: Ali Waqar Azim, Ahmad Bazzi, Mahrukh Fatima, Raed Shubair, Marwa Chafii

Abstract: We propose a dual-mode (DM) time domain multiplexed (TDM) chirp spread spectrum (CSS) modulation for spectral and energy-efficient low-power wide-area networks (LPWANs). DM-CSS modulation that uses both the even and odd cyclic time shifts has been proposed for LPWANs to achieve noteworthy performance improvement over classical counterparts. However, its spectral efficiency (SE) is half of the in-p… ▽ More We propose a dual-mode (DM) time domain multiplexed (TDM) chirp spread spectrum (CSS) modulation for spectral and energy-efficient low-power wide-area networks (LPWANs). DM-CSS modulation that uses both the even and odd cyclic time shifts has been proposed for LPWANs to achieve noteworthy performance improvement over classical counterparts. However, its spectral efficiency (SE) is half of the in-phase and quadrature (IQ)-TDM-CSS scheme that employs IQ components with both up and down chirps, resulting in a SE that is four times relative to Long Range (LoRa) modulation. Nevertheless, the IQ-TDM-CSS scheme only allows coherent detection. Furthermore, it is also sensitive to carrier frequency and phase offsets, making it less practical for low-cost battery-powered LPWANs for Internet-of-Things (IoT) applications. DM-CSS uses either an up-chirp or a down-chirp. DM-TDM-CSS consists of two chirped symbols that are multiplexed in the time domain. One of these symbols consisting of even and odd frequency shifts (FSs) is chirped using an up-chirp. The second chirped symbol also consists of even and odd FSs, but they are chirped using a down-chirp. It shall be demonstrated that DM-TDM-CSS attains a maximum achievable SE close to IQ-TDM-CSS while also allowing both coherent and non-coherent detection. Additionally, unlike IQ-TDM-CSS, DM-TDM-CSS is robust against carrier frequency and phase offsets. △ Less

Submitted 8 October, 2022; originally announced October 2022.

On Integrated Sensing and Communication Waveforms with Tunable PAPR

Authors: Ahmad Bazzi, Marwa Chafii

Abstract: We present a novel approach to the problem of dual-functional radar and communication (DFRC) waveform design with adjustable peak-to-average power ratio (PAPR), while minimizing the multi-user communication interference and maintaining a similarity constraint towards a radar chirp signal. The approach is applicable to generic radar chirp signals and for different constellation sizes. We formulate… ▽ More We present a novel approach to the problem of dual-functional radar and communication (DFRC) waveform design with adjustable peak-to-average power ratio (PAPR), while minimizing the multi-user communication interference and maintaining a similarity constraint towards a radar chirp signal. The approach is applicable to generic radar chirp signals and for different constellation sizes. We formulate the waveform design problem as a non convex optimization problem. As a solution, we adopt the alternating direction method of multipliers (ADMM), hence iterating towards a stable waveform for both radar and communication purposes. Additionally, we prove convergence of the proposed method and analyze its computational complexity. Moreover, we offer an extended version of the method to cope with imperfect channel state information (CSI). Finally, we demonstrate its superior performance through simulations, in comparison to state-of-the-art radar-communication waveform designs. △ Less

Submitted 25 February, 2023; v1 submitted 6 October, 2022; originally announced October 2022.

Chirp Spread Spectrum-based Waveform Design and Detection Mechanisms for LPWAN-based IoT -- A Survey

Authors: Ali Waqar Azim, Ahmad Bazzi, Raed Shubair, Marwa Chafii

Abstract: LoRa is a widely adopted method of utilizing chirp spread spectrum (CSS) techniques at the physical (PHY) layer to facilitate low-power wide-area network (LPWAN) connectivity. By tailoring the spreading factors, LoRa can achieve a diverse spectral and energy efficiency (EE) levels, making it amenable to a plethora of Internet-of-Things (IoT) applications that rely on LPWANs. However, a primary dra… ▽ More LoRa is a widely adopted method of utilizing chirp spread spectrum (CSS) techniques at the physical (PHY) layer to facilitate low-power wide-area network (LPWAN) connectivity. By tailoring the spreading factors, LoRa can achieve a diverse spectral and energy efficiency (EE) levels, making it amenable to a plethora of Internet-of-Things (IoT) applications that rely on LPWANs. However, a primary drawback of LoRa is its relatively low data data rate. Despite this, there has been a dearth of research dedicated to enhancing the data transfer capabilities of LoRa until recently, when a plethora of CSS-based PHY layer alternatives to LoRa for LPWANs was proposed. This survey, for the first time, presents a comprehensive examination of the waveform design of these CSS-based PHY layer alternatives, proposed between \(2019\) and \(2022\). A total of fifteen alternatives to LoRa are analyzed. This study delves deeply into the waveform design of alternatives to LoRa. The CSS schemes studied in this study are classified into three categories: single chirp, multiple chirps, and multiple chirps with index modulation, based on the number of activated frequency shifts activated for un-chirped symbols. The transceiver architecture of these schemes is thoroughly explicated. Additionally, we propose coherent/non-coherent detection mechanisms for specific schemes that have not been previously documented in the literature. We also provide some key insights and recommendations based on the performance of the schemes. The performance of the schemes is evaluated based on metrics such as EE, spectral efficiency, the bit-error-rate (BER) in additive white Gaussian noise, and BER in the presence of phase and frequency offsets. Finally, we highlight some open research issues and future research directions in this field. △ Less

Submitted 3 April, 2023; v1 submitted 22 August, 2022; originally announced August 2022.

Adaptive Repetitions Strategies in IEEE 802.11bd

Authors: Wu Zhuofei, Stefania Bartoletti, Vincent Martinez, Alessandro Bazzi

Abstract: A new backward compatible WiFi amendment is under development by the IEEE bd Task Group towards the so-called IEEE 802.11bd, which includes the possibility to transmit up to three repetitions of the same packet. This feature increases time diversity and enables the use of maximum ratio combining (MRC) at the receiver to improve the probability of correct decoding. In this work, we first investigat… ▽ More A new backward compatible WiFi amendment is under development by the IEEE bd Task Group towards the so-called IEEE 802.11bd, which includes the possibility to transmit up to three repetitions of the same packet. This feature increases time diversity and enables the use of maximum ratio combining (MRC) at the receiver to improve the probability of correct decoding. In this work, we first investigate the packet repetition feature and analyze how it looses its efficacy increasing the traffic as an higher number of transmissions may augment the channel load and collision probability. Then, we propose two strategies for adaptively selecting the number of transmissions leveraging on an adapted version of the channel busy ratio (CBR), which is measured at the transmitter and is an indicator of the channel load. The proposed strategies are validated through network-level simulations that account for both the acquisition and decoding processes. Results show that the proposed strategies ensure that devices use optimal settings under variable traffic conditions. △ Less

Submitted 14 July, 2022; originally announced July 2022.

Journal ref: IEEE Transactions on Vehicular Technology, 2023

On Outage-based Beamforming Design for Dual-Functional Radar-Communication 6G Systems

Authors: Ahmad Bazzi, Marwa Chafii

Abstract: This article studies and derives beamforming design in a dual-functional radar-communication (DFRC) multiple-input-multiple-output system. We focus on a scenario, where the DFRC base station communicates with downlink communication users, with imperfect channel state information knowledge, and performs target detection, all via the same transmit signal. Through careful relaxation procedures, we ar… ▽ More This article studies and derives beamforming design in a dual-functional radar-communication (DFRC) multiple-input-multiple-output system. We focus on a scenario, where the DFRC base station communicates with downlink communication users, with imperfect channel state information knowledge, and performs target detection, all via the same transmit signal. Through careful relaxation procedures, we arrive at a suitable and novel optimization problem, which maximizes the radar output power in the Bartlett sense, under probabilistic outage signal-to-interference-and-noise ratio constraints. Theoretical analysis proves optimality of the solution given by the relaxed version of the problem, as well as closed-form solutions in certain scenarios. Finally, the achieved performances and trade-offs of the proposed beamforming design are demonstrated through numerical simulations. △ Less

Submitted 5 January, 2023; v1 submitted 11 July, 2022; originally announced July 2022.

Comments: to appear in IEEE Transactions on Wireless Communications, 2023

Dual-Mode Chirp Spread Spectrum Modulation

Authors: Ali Waqar Azim, Ahmad Bazzi, Raed Shubair, Marwa Chafii

Abstract: In this letter, we propose dual-mode chirp spread spectrum (DM-CSS) modulation for low-power wide-area networks. DM-CSS is capable of achieving a higher spectral efficiency (SE) relative to its counterparts, such as Long Range (LoRa) modulation. Considering the same symbol period, the SE in DM-CSS are augmented by: (i) simultaneously multiplexing even and odd chirp signals; (ii) using phase shifts… ▽ More In this letter, we propose dual-mode chirp spread spectrum (DM-CSS) modulation for low-power wide-area networks. DM-CSS is capable of achieving a higher spectral efficiency (SE) relative to its counterparts, such as Long Range (LoRa) modulation. Considering the same symbol period, the SE in DM-CSS are augmented by: (i) simultaneously multiplexing even and odd chirp signals; (ii) using phase shifts of \(0\) and \(π\) radians for both even and odd chirp signals; and (iii) using either up-chirp or down-chirp signal. The SE increases by up to \(116.66\%\) for the same bandwidth and spreading factor relative to LoRa. We present a complete transceiver architecture along with non-coherent detection process. Simulation results reveal that DM-CSS is not only more spectral efficient but also more energy efficient than most classical counterparts. It is also demonstrated that DM-CSS is robust to phase and frequency offsets. △ Less

Submitted 11 July, 2022; v1 submitted 19 May, 2022; originally announced May 2022.

Comments: Accept

Journal ref: IEEE Wireless Communications Letters, 2022

A Methodology for Abstracting the Physical Layer of Direct V2X Communications Technologies

Authors: Wu Zhuofei, Stefania Bartoletti, Vincent Martinez, Alessandro Bazzi

Abstract: Recent advancements in V2X communications have greatly increased the flexibility of the physical and medium access control (MAC) layers. This increases the complexity when investigating the system from a network perspective to evaluate the performance of the supported applications. Such flexibility needs in fact to be taken into account through a cross-layer approach, which might lead to challengi… ▽ More Recent advancements in V2X communications have greatly increased the flexibility of the physical and medium access control (MAC) layers. This increases the complexity when investigating the system from a network perspective to evaluate the performance of the supported applications. Such flexibility needs in fact to be taken into account through a cross-layer approach, which might lead to challenging evaluation processes. As an accurate simulation of the signals appears unfeasible, a typical solution is to rely on simple models for incorporating the physical layer of the supported technologies, based on off-line measurements or accurate link-level simulations. Such data is however limited to a subset of possible configurations and extending them to others is costly when not even impossible. The goal of this paper is to develop a new approach for modelling the physical layer of vehicle-to-everything (V2X) communications that can be extended to a wide range of configurations without leading to extensive measurement or simulation campaign at the link layer. In particular, given a scenario and starting from results in terms of packet error rate (PER) vs. signal-to-interference-plus-noise ratio (SINR) related to a subset of possible configurations, we derive one parameter, called implementation loss, that is then used to evaluate the network performance under any configuration in the same scenario. The proposed methodology, leading to a good trade-off among complexity, generality, and accuracy of the performance evaluation process, has been validated through extensive simulations with both IEEE 802.11p and LTE-V2X sidelink technologies in various scenarios. △ Less

Submitted 24 October, 2022; v1 submitted 31 March, 2022; originally announced March 2022.

Performance Analysis of IEEE 802.11p Preamble Insertion in C-V2X Sidelink Signals for Co-Channel Coexistence

Authors: Alessandro Bazzi, Stefania Bartoletti, Alberto Zanella, Vincent Martinez

Abstract: Spectrum scarcity is one of the main challenges of future wireless technologies. When looking at vehicle-to-everything (V2X), this is amplified as spectrum sharing could impact road safety and traffic efficiency. It is therefore of particular importance to study solutions that allow the coexistence, in the same geographical area and in the same channels, of what are today the main V2X access techn… ▽ More Spectrum scarcity is one of the main challenges of future wireless technologies. When looking at vehicle-to-everything (V2X), this is amplified as spectrum sharing could impact road safety and traffic efficiency. It is therefore of particular importance to study solutions that allow the coexistence, in the same geographical area and in the same channels, of what are today the main V2X access technologies, namely IEEE 802.11p and sidelink LTE-V2X Mode 4. In this work, in addition to investigating the impact of the reciprocal interference, which we demonstrate to have a strong impact especially on the first and in congested channel conditions, a mitigation solution is extensively studied, which is based on the insertion of the IEEE 802.11p preamble at the beginning of the LTE-V2X sidelink transmission. The proposal, which is also under discussion within the standardization bodies, requires no modifications to the IEEE 802.11p protocol stack and minor changes to LTE-V2X sidelink. This solution is directly applicable to upcoming IEEE 802.11bd and extendable to NR-V2X sidelink. The paper shows, through analysis and simulations in free-flow and dense scenarios, that the proposal allows for a mitigation of collisions caused by co-channel coexistence under low to high-load channel conditions and that the improvement is also granted in congested cases when combined with additional countermeasures. Regarding the latter aspect, in particular, different approaches are compared, demonstrating that acting on the congestion control mechanisms is a simple but effective solution. △ Less

Submitted 6 April, 2022; v1 submitted 18 January, 2022; originally announced January 2022.

Optimizations for Hardware-in-the-Loop-Based V2X Validation Platforms

Authors: Babak Mafakheri, Pierpaolo Gonnella, Alessandro Bazzi, Barbara Mavi Masini, Michele Caggiano, Roberto Verdone

Abstract: Connectivity and automation are increasingly getting importance in the automotive industry, which is observing a radical change from vehicles driven by humans to fully automated and remotely controlled ones. The test and validation of all the related devices and applications is thus becoming a crucial aspect; this is raising the interest on hardware-in-the-loop (HiL) platforms which reduce the nee… ▽ More Connectivity and automation are increasingly getting importance in the automotive industry, which is observing a radical change from vehicles driven by humans to fully automated and remotely controlled ones. The test and validation of all the related devices and applications is thus becoming a crucial aspect; this is raising the interest on hardware-in-the-loop (HiL) platforms which reduce the need for complicated field trials, thus limiting the costs and delay added to the process. With reference to the test and validation of vehicle-to-everything (V2X) communications aspects, and assuming either sidelink LTE/5GV2X or IEEE 802.11p/bd technologies, in this work we focus on the real-time HiL simulation of the information exchanged by one vehicle under test and the surrounding, simulated, objects. Such exchange must be reproduced in a time-efficient manner, with elaborations done fast enough to allow testing the applications in real-time. More precisely, we discuss the simulation of nonideal positioning and channel propagation taking into account current impairments. We also provide details on optimization solutions that allowed us to trade-off minor loss in accuracy with a significant reduction of the computation time burden, reaching up to more than one order of magnitude speed increase in our experiments. △ Less

Submitted 26 April, 2021; originally announced May 2021.

Comments: The 2021 IEEE 93rd Vehicular Technology Conference: VTC2021-Spring

Fundamental Performance Limits of mm-Wave Cooperative Localization in Linear Topologies

Authors: V. A. Reddy, A. Bazzi, G. L. Stuber, S. Al-Dharrab, W. Mesbah, A. H. Muqaibel

Abstract: In applications such as seismic acquisition, the position information of sensor nodes, that are deployed in a linear topology, is desired with sub-meter accuracy in the presence of a limited number of anchor nodes. This can be achieved with antenna arrays via mm-wave cooperative localization, whose performance limits are derived in this letter. The number of anchor nodes is seen to have a stronger… ▽ More In applications such as seismic acquisition, the position information of sensor nodes, that are deployed in a linear topology, is desired with sub-meter accuracy in the presence of a limited number of anchor nodes. This can be achieved with antenna arrays via mm-wave cooperative localization, whose performance limits are derived in this letter. The number of anchor nodes is seen to have a stronger impact than the number of antenna elements in the anchor nodes. Succinct closed-form expressions for the position error bound are also obtained for 1-hop and 2-hop cooperative localization, where sub-meter accuracy is perceived over several hundred nodes. △ Less

Submitted 10 July, 2020; originally announced July 2020.

Co-channel Coexistence: Let ITS-G5 and Sidelink C-V2X Make Peace

Authors: Alessandro Bazzi, Alberto Zanella, Ioannis Sarris, Vincent Martinez

Abstract: In the last few years, two technologies have been developed to enable direct exchange of information between vehicles. These technologies, currently seen as alternatives, are ITS-G5, as commonly referred in Europe, and sidelink LTE-vehicle-to-everything (LTE-V2X) (one of the solutions of the so-called cellular-V2X, C-V2X). For this reason, the attention has been mostly concentrated on comparing th… ▽ More In the last few years, two technologies have been developed to enable direct exchange of information between vehicles. These technologies, currently seen as alternatives, are ITS-G5, as commonly referred in Europe, and sidelink LTE-vehicle-to-everything (LTE-V2X) (one of the solutions of the so-called cellular-V2X, C-V2X). For this reason, the attention has been mostly concentrated on comparing them and remarking their strengths and weaknesses to motivate a choice. Differently, in this work we focus on a scenario where both are used in the same area and using the same frequency channels, without the assistance from any infrastructure. Our results show that under co-channel coexistence the range of ITS-G5 is severely degraded, while impact on LTE-V2X is marginal. Additionally, a mitigation method where the CAM data generation is constrained to periodical intervals is shown to reduce the impact of co-channel coexistence, with less degradation on ITS-G5 performance and even improvement for LTE-V2X. △ Less

Submitted 20 March, 2020; originally announced March 2020.

Congestion Control Mechanisms in IEEE 802.11p and Sidelink C-V2X

Authors: Alessandro Bazzi

Abstract: Connected vehicles are expected to play a major role in the next future to improve safety and traffic efficiency on the road and short-range technologies have been defined to enable the direct exchange of information. To this aim, two solutions are currently the subject of a debate that goes beyond the technician, i.e., IEEE 802.11p and sidelink cellular-vehicle-to-anything (C-V2X). Tested and mat… ▽ More Connected vehicles are expected to play a major role in the next future to improve safety and traffic efficiency on the road and short-range technologies have been defined to enable the direct exchange of information. To this aim, two solutions are currently the subject of a debate that goes beyond the technician, i.e., IEEE 802.11p and sidelink cellular-vehicle-to-anything (C-V2X). Tested and mature for deployment the first, possibly more efficient the second. In both cases, one of the main aspects is the management of channel congestions, which can cause serious packet losses and have a critical impact on the reliability of applications. Congestions can be managed through different approaches, including the control of transmission power, packet generation frequency, and the adopted modulation and coding scheme. Congestion management has been well studied in IEEE 802.11p, with consolidated algorithms included in the standards, whereas it appears somehow as a new topic looking at C-V2X. In this work, a review of the main congestion control mechanisms and a discussion of their applicability and efficiency in the two technologies is provided. This topic is addressed without focusing on specific algorithms and with the aim to provide general guidelines as a starting point for new proposals. △ Less

Submitted 23 January, 2020; originally announced January 2020.

A Hardware-in-the-Loop Evaluation of the Impact of the V2X Channel on the Traffic-Safety Versus Efficiency Trade-offs

Authors: Alessandro Bazzi, Thomas Blazek, Michele Menarini, Barbara M. Masini, Alberto Zanella, Christoph Mecklenbrauker, Golsa Ghiaasi

Abstract: Vehicles are increasingly becoming connected and short-range wireless communications promise to introduce a radical change in the drivers' behaviors. Among the main use cases, the intersection management is surely one of those that could mostly impact on both traffic safety and efficiency. In this work, we consider an intersection collision warning application and exploit an hardware-in-the-loop (… ▽ More Vehicles are increasingly becoming connected and short-range wireless communications promise to introduce a radical change in the drivers' behaviors. Among the main use cases, the intersection management is surely one of those that could mostly impact on both traffic safety and efficiency. In this work, we consider an intersection collision warning application and exploit an hardware-in-the-loop (HIL) platform to verify the impact on the risk of accidents as well as the average time to travel a given distance. Besides including real ITS-G5 compliant message exchanges, the platform also includes a channel emulator with real signals. Results show that the risk of collisions can be drastically reduced, with an overall trade-off between safety and traffic efficiency. At the same time, it is shown that the presence of real channel conditions cannot guarantee the same condition of zero-risk as with ideal channel propagation, remarking the importance of channel conditions and signal processing. △ Less

Submitted 22 January, 2020; originally announced January 2020.

Study of the Impact of PHY and MAC Parameters in 3GPP C-V2V Mode 4

Authors: Alessandro Bazzi, Giammarco Cecchini, Barbara M. Masini, Alberto Zanella

Abstract: In the latest years, 3GPP has added short range cellular-vehicle-to-anything (C-V2X) to the features of LTE and 5G in order to make vehicles, roadside devices, and vulnerable users directly exchange information using the same chipset as for classical long range connections. C-V2X is based on the use of advanced physical layer techniques and orthogonal resources, and one of the main aspects affecti… ▽ More In the latest years, 3GPP has added short range cellular-vehicle-to-anything (C-V2X) to the features of LTE and 5G in order to make vehicles, roadside devices, and vulnerable users directly exchange information using the same chipset as for classical long range connections. C-V2X is based on the use of advanced physical layer techniques and orthogonal resources, and one of the main aspects affecting its performance is the way resources are allocated. Allocations can be either managed by the network or in a distributed way, directly by the nodes. The latter case, called Mode 4, is defined to manage those situations where the network cannot be involved in the scheduling process, for example due to a lack of coverage, but could also be adopted in order to reduce the processing burden of eNodeB. An algorithm, defined in the standards, makes nodes sense the medium and identify the best time-frequency combination to allocate their messages. Focusing on C-V2V Mode 4, in this work we analyze the parameters of the algorithm designed by 3GPP and their impact on the system performance. Through simulations in different large scale scenarios, we show that modifying some parameters have negligible effect, that the proper choice of others can indeed improve the quality of service, and that a group of parameters allows to trade-off reliability with update delay. The provided results can also be exploited to guide future work. △ Less

Submitted 28 November, 2018; v1 submitted 27 July, 2018; originally announced July 2018.

Journal ref: IEEE Access, vol. 6, pp. 71685-71698, 2018

An Efficient Streaming Algorithm for the Submodular Cover Problem

Authors: Ashkan Norouzi-Fard, Abbas Bazzi, Marwa El Halabi, Ilija Bogunovic, Ya-Ping Hsieh, Volkan Cevher

Abstract: We initiate the study of the classical Submodular Cover (SC) problem in the data streaming model which we refer to as the Streaming Submodular Cover (SSC). We show that any single pass streaming algorithm using sublinear memory in the size of the stream will fail to provide any non-trivial approximation guarantees for SSC. Hence, we consider a relaxed version of SSC, where we only seek to find a p… ▽ More We initiate the study of the classical Submodular Cover (SC) problem in the data streaming model which we refer to as the Streaming Submodular Cover (SSC). We show that any single pass streaming algorithm using sublinear memory in the size of the stream will fail to provide any non-trivial approximation guarantees for SSC. Hence, we consider a relaxed version of SSC, where we only seek to find a partial cover. We design the first Efficient bicriteria Submodular Cover Streaming (ESC-Streaming) algorithm for this problem, and provide theoretical guarantees for its performance supported by numerical evidence. Our algorithm finds solutions that are competitive with the near-optimal offline greedy algorithm despite requiring only a single pass over the data stream. In our numerical experiments, we evaluate the performance of ESC-Streaming on active set selection and large-scale graph cover problems. △ Less

Submitted 25 November, 2016; originally announced November 2016.

Comments: To appear in NIPS'16

Small Extended Formulation for Knapsack Cover Inequalities from Monotone Circuits

Authors: Abbas Bazzi, Samuel Fiorini, Sangxia Huang, Ola Svensson

Abstract: Initially developed for the min-knapsack problem, the knapsack cover inequalities are used in the current best relaxations for numerous combinatorial optimization problems of covering type. In spite of their widespread use, these inequalities yield linear programming (LP) relaxations of exponential size, over which it is not known how to optimize exactly in polynomial time. In this paper we addres… ▽ More Initially developed for the min-knapsack problem, the knapsack cover inequalities are used in the current best relaxations for numerous combinatorial optimization problems of covering type. In spite of their widespread use, these inequalities yield linear programming (LP) relaxations of exponential size, over which it is not known how to optimize exactly in polynomial time. In this paper we address this issue and obtain LP relaxations of quasi-polynomial size that are at least as strong as that given by the knapsack cover inequalities. For the min-knapsack cover problem, our main result can be stated formally as follows: for any $\varepsilon >0$, there is a $(1/\varepsilon)^{O(1)}n^{O(\log n)}$-size LP relaxation with an integrality gap of at most $2+\varepsilon$, where $n$ is the number of items. Prior to this work, there was no known relaxation of subexponential size with a constant upper bound on the integrality gap. Our construction is inspired by a connection between extended formulations and monotone circuit complexity via Karchmer-Wigderson games. In particular, our LP is based on $O(\log^2 n)$-depth monotone circuits with fan-in~$2$ for evaluating weighted threshold functions with $n$ inputs, as constructed by Beimel and Weinreb. We believe that a further understanding of this connection may lead to more positive results complementing the numerous lower bounds recently proved for extended formulations. △ Less

Submitted 18 November, 2016; v1 submitted 13 September, 2016; originally announced September 2016.

Comments: 21 pages

Towards Tight Lower Bounds for Scheduling Problems

Authors: Abbas Bazzi, Ashkan Norouzi-Fard

Abstract: We show a close connection between structural hardness for $k$-partite graphs and tight inapproximability results for scheduling problems with precedence constraints. Assuming a natural but nontrivial generalisation of the bipartite structural hardness result of Bansal and Khot, we obtain a hardness of $2-ε$ for the problem of minimising the makespan for scheduling precedence-constrained jobs with… ▽ More We show a close connection between structural hardness for $k$-partite graphs and tight inapproximability results for scheduling problems with precedence constraints. Assuming a natural but nontrivial generalisation of the bipartite structural hardness result of Bansal and Khot, we obtain a hardness of $2-ε$ for the problem of minimising the makespan for scheduling precedence-constrained jobs with preemption on identical parallel machines. This matches the best approximation guarantee for this problem. Assuming the same hypothesis, we also obtain a super constant inapproximability result for the problem of scheduling precedence-constrained jobs on related parallel machines, making progress towards settling an open question in both lists of ten open questions by Williamson and Shmoys, and by Schuurman and Woeginger. The study of structural hardness of $k$-partite graphs is of independent interest, as it captures the intrinsic hardness for a large family of scheduling problems. Other than the ones already mentioned, this generalisation also implies tight inapproximability to the problem of minimising the weighted completion time for precedence-constrained jobs on a single machine, and the problem of minimising the makespan of precedence-constrained jobs on identical parallel machine, and hence unifying the results of Bansal and Khot, and Svensson, respectively. △ Less

Submitted 7 July, 2015; originally announced July 2015.

Comments: 25 pages, 3 figures, To appear in the Proceedings of the 23rd Annual European Symposium on Algorithms 2015

A Formal Study on Backward Compatible Dynamic Software Updates

Authors: Jun Shen, Rida A. Bazzi

Abstract: We study the dynamic software update problem for programs interacting with an environment that is not necessarily updated. We argue that such updates should be backward compatible. We propose a general definition of backward compatibility and cases of backward compatible program update. Based on our detailed study of real world program evolution, we propose classes of backward compatible update fo… ▽ More We study the dynamic software update problem for programs interacting with an environment that is not necessarily updated. We argue that such updates should be backward compatible. We propose a general definition of backward compatibility and cases of backward compatible program update. Based on our detailed study of real world program evolution, we propose classes of backward compatible update for interactive programs, which are included at an average of 32% of all studied program changes. The definitions of update classes are parameterized by our novel framework of program equivalence, which generalizes existing results on program equivalence to non-terminating executions. Our study of backward compatible updates is based on a typed extension of W language. △ Less

Submitted 10 September, 2015; v1 submitted 24 March, 2015; originally announced March 2015.

No Small Linear Program Approximates Vertex Cover within a Factor $2 - ε$

Authors: Abbas Bazzi, Samuel Fiorini, Sebastian Pokutta, Ola Svensson

Abstract: The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev (2003) proved that the problem is NP-hard to approximate within a factor $2 - ε$, assuming the Unique Games Conjecture (UGC). This is tight because the problem has an easy 2-approximation algorithm. Without resorting to the UGC, the best inapproximability result for the… ▽ More The vertex cover problem is one of the most important and intensively studied combinatorial optimization problems. Khot and Regev (2003) proved that the problem is NP-hard to approximate within a factor $2 - ε$, assuming the Unique Games Conjecture (UGC). This is tight because the problem has an easy 2-approximation algorithm. Without resorting to the UGC, the best inapproximability result for the problem is due to Dinur and Safra (2002): vertex cover is NP-hard to approximate within a factor 1.3606. We prove the following unconditional result about linear programming (LP) relaxations of the problem: every LP relaxation that approximates vertex cover within a factor $2-ε$ has super-polynomially many inequalities. As a direct consequence of our methods, we also establish that LP relaxations (as well as SDP relaxations) that approximate the independent set problem within any constant factor have super-polynomial size. △ Less

Submitted 26 November, 2015; v1 submitted 2 March, 2015; originally announced March 2015.