YEYahya H. Ezzeldin

Yahya H. Ezzeldin

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Yahya H. Ezzeldin has a total of 10 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Gomory-Hu Trees Over Wireless

    by Mine Gokce Dogan, Yahya H. Ezzeldin, Christina Fragouli

    The Gomory-Hu tree is a popular optimization algorithm that enables to efficiently find a min-cut (or equivalently, max-flow) for every pair of nodes in a graph. However, graphs cannot capture broadcasting and interference in wireless: over wireless networks we need to resort to the information-theoretical cut-set to bound the max-flow. Leveraging the submodularity of mutual information, we show that the Gomory-Hu algorithm can be used to efficiently find information-theoretic rate characterizations such as the capacity or an approximation to the capacity, over a number of network scenarios including wireless Gaussian networks and deterministic relay networks.

  • Quantization of Distributed Data for Learning

    by Osama A. Hanna, Yahya H. Ezzeldin, Christina Fragouli, Suhas Diggavi

    We consider machine learning applications that train a model by leveraging data distributed over a trusted network, where communication constraints can create a performance bottleneck. A number of recent approaches propose to overcome this bottleneck through compression of gradient updates. However, as models become larger, so does the size of the gradient updates. In this paper, we propose an alternate approach to learn from distributed data that quantizes data instead of gradients, and can support learning over applications where the size of gradient updates is prohibitive. Our approach leverages the dependency of the computed gradient on data samples, which lie in a much smaller space in order to perform the quantization in the smaller dimension data space. At the cost of an extra gradient computation, the gradient estimate can be refined by conveying the difference between the gradient at the quantized data point and the original gradient using a small number of bits. Lastly, in order to save communication, our approach adds a layer that decides whether to transmit a quantized data sample or not based on its importance for learning. We analyze the convergence of the proposed approach for smooth convex and non-convex objective functions and show that we can achieve order optimal convergence rates with communication that mostly depends on the data rather than the model (gradient) dimension. We use our proposed algorithm to train ResNet models on the CIFAR-10 and ImageNet datasets, and show that we can achieve an order of magnitude savings over gradient compression methods. These communication savings come at the cost of increasing computation at the learning agent, and thus our approach is beneficial in scenarios where communication load is the main problem.


  • Efficient Beam Scheduling for Half-Duplex mmWave Relay Networks

    by Xiaoshen Song, Yahya H. Ezzeldin, Giuseppe Caire, Christina Fragouli

    Millimeter wave (mmWave) communication is expected to play a central role in next generation mobile systems (5G) and beyond, by providing multi-Gbps data rates. However, the severe pathloss and sensitivity to blockages at mmWave frequencies significantly challenge practical implementations. One effective way to mitigate these effects and to increase the communication range is beamforming in combination with relaying. In this paper, we study the beam scheduling problem for mmWave half-duplex (HD) relay networks, where the relay topology can be arbitrary. Based on theoretically optimal scheduling results, we first implement a network simplification procedure to reduce the network topology complexity, and then propose two practically relevant beam scheduling schemes: the deterministic edge coloring (EC) scheduler and the adaptive backpressure (BP) scheduler. The former consists of a very simple one-time computation of the sequence of scheduling states, which is then repeated periodically. The one-time computation depends on the underlying network topology, and therefore it must be repeated when such topology changes. As such, this approach is more suited to quasi-static scenarios. The latter is an “online” approach which updates scheduling weights and solves at each time slots a weighted sum rate maximization. Hence, it's computational complexity may be significantly higher than that of EC, but it is better suited to dynamic time-varying scenarios. With the aid of computer simulations, we show that both the proposed schedulers guarantee network stability within the network capacity. Particularly, in comparison with two baseline schemes, the proposed schedulers achieve much smaller queuing backlogs, much smaller backlog fluctuations, and much lower packet end-to-end delays.


  • Gaussian 1-2-1 Networks: Capacity Results for mmWave Communications

    by Yahya H. Ezzeldin, Martina Cardone, Christina Fragouli, Giuseppe Caire

    This paper proposes a new model for wireless relay networks referred to as “1-2-1 network”, where two nodes can communicate only if they point “beams” at each other, otherwise no signal can be exchanged or interference can be generated. This model is motivated by millimeter wave communications where, due to the high path loss, a link between two nodes can exist only if beamforming gain at both sides is established, while in the absence of beamforming gain the signal is received well below the thermal noise floor. The main contributions in this paper include: (a) the development of a constant gap approximation for the unicast and multicast capacities of the proposed network model, i.e., a characterization of the network unicast and multicast capacities to within an additive gap, which only depends on the number of nodes and is independent of the channel coefficients and operating SNR; and (b) the design of algorithms that run in polynomial time in the number of nodes and compute the approximate unicast and multicast capacities, as well as their corresponding optimal beam scheduling strategies. These results are derived both for full-duplex and half-duplex modes of operation at the relays: while in full-duplex the transmit and receive beams at a relay can be simultaneously active, in half-duplex only one can be active at each point in time. The relation between the approximate multicast capacity and minimum unicast capacity is explored in full-duplex 1-2-1 networks and shown to be dependent on the network structure and the number of destinations, unlike in classical wireless (i.e., without 1-2-1 constraints) full-duplex networks. Finally, network simplification results are proved for the 1-2-1 network model by exploiting the structure of the linear program that represents the approximate capacity.


  • Wireless Network Simplification: The Performance of Routing

    by Yahya H. Ezzeldin, Ayan Sengupta, Christina Fragouli

    This paper explores the network simplification problem for Gaussian full-duplex relay networks with arbitrary topology. Particularly, given an $N$ -relay Gaussian full-duplex network, the network simplification problem seeks to find fundamental guarantees on the capacity of the best subnetwork, among a particular class of subnetworks, as a fraction of the full-network capacity. The focus of this work is the case when the selected subnetwork class is a path from the source to the destination. The main result of the paper shows that for an $N$ -relay Gaussian networks with arbitrary topology, the best route can in the worst case guarantee an approximate fraction $\frac {1}{ \lfloor N/2 \rfloor + 1}$ of the capacity of the full network, independently of the channel coefficients and/or operating SNR. Furthermore, this guarantee is shown to be fundamental, i.e., it is the highest worst-case guarantee that can be provided for routing in relay networks. A key step in the proof of the main result lies in the derivation of a simplification result for antenna selection in MIMO channels that may also be of independent interest. To the best of our knowledge, this is the first result that characterizes the performance of routing in comparison to physical layer cooperation techniques that approximately achieve the network capacity for general wireless network topologies. The results in this paper show that routing can, in the worst case, result in an unbounded gap from the network capacity - or reversely, physical layer cooperation can offer unbounded gains over routing.


  • The Approximate Capacity of Half-Duplex Line Networks

    by Yahya H. Ezzeldin, Martina Cardone, Christina Fragouli, Daniela Tuninetti

    This paper investigates the problem of characterizing the capacity of Half-Duplex (HD) line networks , where a source node communicates to a destination node through a multi-hop path of $N$ relays. If the relays operate in Full-Duplex (FD), it is well known that the capacity of the line network equals the minimum among the point-to-point link capacities in the path. In contrast, this paper considers a different case where the relays operate in HD. In the first part of the paper, it is shown that the approximate capacity (optimal up to a constant additive gap that only depends on the number of nodes in the network) of an HD $N$ -relay line network equals half the minimum of the harmonic means of the point-to-point link capacities of each two consecutive links in the path. It is then proved that the $N+1$ listen/transmit states (out of the $2^{N}$ possible ones) sufficient to characterize the approximate capacity can be found in linear time. In the second part of the paper, it is shown that the problem of finding the path that has the largest HD approximate capacity in a network that can be represented as a graph is NP-hard. However, if the number of cycles in the network is polynomial in the number of nodes, then a polynomial-time algorithm can indeed be designed.

  • On Distributed Quantization for Classification

    by Osama A. Hanna, Yahya H. Ezzeldin, Tara Sadjadpour, Christina Fragouli, Suhas Diggavi

    We consider the problem of distributed feature quantization, where the goal is to enable a pretrained classifier at a central node to carry out its classification on features that are gathered from distributed nodes through communication constrained channels. We propose the design of distributed quantization schemes specifically tailored to the classification task: unlike quantization schemes that help the central node reconstruct the original signal as accurately as possible, our focus is not reconstruction accuracy, but instead correct classification. Our work does not make any a priori distributional assumptions on the data, but instead uses training data for the quantizer design. Our main contributions include: we prove NP-hardness of finding optimal quantizers in the general case; we design an optimal scheme for a special case; we propose quantization algorithms, that leverage discrete neural representations and training data, and can be designed in polynomial-time for any number of features, any number of classes, and arbitrary division of features across the distributed nodes. We find that tailoring the quantizers to the classification task can offer significant savings: as compared to alternatives, we can achieve more than a factor of two reduction in terms of the number of bits communicated, for the same classification accuracy.


  • Network Simplification in Half-Duplex: Building on Submodularity

    by Yahya H. Ezzeldin, Martina Cardone, Christina Fragouli, Daniela Tuninetti

    This paper explores the network simplification problem in the context of Gaussian half-duplex diamond networks. Specifically, given an N-relay diamond network, this problem seeks to derive fundamental guarantees on the capacity of the best k-relay subnetwork, as a function of the full network capacity. Simplification guarantees are presented in terms of a particular approximate capacity, termed Independent-Gaussian (IG) approximate capacity, that characterizes the network capacity to within an additive gap, which is independent of the channel coefficients and operating SNR. The main focus of this work is when k=N-1 relays are selected out of N relays in a diamond network. First, a simple algorithm is proposed which selects all relays except the one with the minimum IG approximate half-duplex capacity. It is shown that the selected (N-1)-relay subnetwork has an IG approximate half-duplex capacity that is at least 1/2 of the IG approximate half-duplex capacity of the full network and that for the proposed algorithm, this guarantee is tight. Next, this work proves the following tight fundamental guarantee: there always exists a subnetwork of k=N-1 relays that has an IG approximate half-duplex capacity that is at least equal to (N-1)/N of the IG approximate half-duplex capacity of the full network. Finally, these results are extended to derive lower bounds on the fraction guarantee when k ∈ [1 : N] relays are selected. The key steps in the proofs lie in the derivation of properties of submodular functions, which provide a combinatorial handle on the network simplification problem for Gaussian half-duplex diamond networks.