Saeid Sahraei
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
Research Subjects
Research Interests
Saeid Sahraei has a total of 8 co-authors. Here are the top co-authors by number of shared publications:
Michael Gastpar
EPFL IPG - IC, Lausanne, CH-1015, Switzerland
4 shared publications- Michael Gastpar
School of Computer and Communication Sciences, EPFL, Lausanne, Switzerland
2 shared publications A. Salman Avestimehr
1 shared publicationF. Ashtiani
1 shared publicationMohammad Ali Maddah-Ali
Department of Electrical Engineering, Sharif University of Technology, Tehran 11365, Iran
1 shared publication- Pierre Quinton
School of Computer and Communication Sciences, École Polytechnique Fédérale de Lausanne (EPFL), Lausanne, Vaud 1015, Switzerland
1 shared publication
Latest Publications
- 18 April 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Forensics and Security
- Vol. 17 (15566013) , 1698-1708
Info-Commit: Information-Theoretic Polynomial Commitment
We introduce Info-Commit , an information-theoretic protocol for polynomial commitment and verification. With the help of a trusted initializer, a succinct commitment to a private polynomial $f$ is provided to the user. The user then queries the server to obtain evaluations of $f$ at several inputs chosen by the user. The server provides the evaluations along with proofs of correctness which the user can verify against the initial commitment. Info-Commit has four main features. Firstly, the user is able to detect, with high probability, if the server has responded with evaluations of the same polynomial initially committed to. Secondly, Info-Commit provides rigorous privacy guarantees for the server: upon observing the initial commitment and the response provided by the server to $m$ evaluation queries, the user only learns $O(m^{2})$ symbols about the coefficients of $f$ . Thirdly, the verifiability and the privacy guarantees are unconditional regardless of the computational power of the two parties. Lastly, Info-Commit is doubly-efficient in the sense that in the evaluation phase, the user runs in $O(\sqrt {d})$ time and the server runs in $O(d)$ time, where $d-1$ is the degree of the polynomial $f$ .
- 18 April 2022
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Forensics and Security
- Vol. 17 (15566013) , 1698-1708
Info-Commit: Information-Theoretic Polynomial Commitment
We introduce Info-Commit , an information-theoretic protocol for polynomial commitment and verification. With the help of a trusted initializer, a succinct commitment to a private polynomial $f$ is provided to the user. The user then queries the server to obtain evaluations of $f$ at several inputs chosen by the user. The server provides the evaluations along with proofs of correctness which the user can verify against the initial commitment. Info-Commit has four main features. Firstly, the user is able to detect, with high probability, if the server has responded with evaluations of the same polynomial initially committed to. Secondly, Info-Commit provides rigorous privacy guarantees for the server: upon observing the initial commitment and the response provided by the server to $m$ evaluation queries, the user only learns $O(m^{2})$ symbols about the coefficients of $f$ . Thirdly, the verifiability and the privacy guarantees are unconditional regardless of the computational power of the two parties. Lastly, Info-Commit is doubly-efficient in the sense that in the evaluation phase, the user runs in $O(\sqrt {d})$ time and the server runs in $O(d)$ time, where $d-1$ is the degree of the polynomial $f$ .
- 29 January 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Information Theory
- Vol. 2 (1) , 317-325
Interactive Verifiable Polynomial Evaluation
Cloud computing platforms have created the possibility for computationally limited users to delegate demanding tasks to strong but untrusted servers. Verifiable computing algorithms help build trust in such interactions by enabling the server to provide a proof of correctness of his results which the user can check very efficiently. In this paper, we present a doubly-efficient interactive algorithm for verifiable polynomial evaluation. Unlike the mainstream literature on verifiable computing, the soundness of our algorithm is information-theoretic and cannot be broken by a computationally unbounded server. By relying on basic properties of error correcting codes, our algorithm enforces a dishonest server to provide false results to problems which become progressively easier to verify. After roughly logd rounds, the user can verify the response of the server against a look-up table that has been pre-computed during an initialization phase. For a polynomial of degree d, we achieve a user complexity of O(d), a server complexity of O(d1+), a round complexity of O(logd) and an initialization complexity of O(d1+).
- 29 January 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Journal on Selected Areas in Information Theory
- Vol. 2 (1) , 317-325
Interactive Verifiable Polynomial Evaluation
Cloud computing platforms have created the possibility for computationally limited users to delegate demanding tasks to strong but untrusted servers. Verifiable computing algorithms help build trust in such interactions by enabling the server to provide a proof of correctness of his results which the user can check very efficiently. In this paper, we present a doubly-efficient interactive algorithm for verifiable polynomial evaluation. Unlike the mainstream literature on verifiable computing, the soundness of our algorithm is information-theoretic and cannot be broken by a computationally unbounded server. By relying on basic properties of error correcting codes, our algorithm enforces a dishonest server to provide false results to problems which become progressively easier to verify. After roughly logd rounds, the user can verify the response of the server against a look-up table that has been pre-computed during an initialization phase. For a polynomial of degree d, we achieve a user complexity of O(d), a server complexity of O(d1+), a round complexity of O(logd) and an initialization complexity of O(d1+).
- 23 July 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 65 (12) , 7756-7770
The Optimal Memory-Rate Trade-Off for the Non-Uniform Centralized Caching Problem With Two Files Under Uncoded Placement
A new scheme for the problem of centralized coded caching with non-uniform demands is proposed. The distinguishing feature of the proposed placement strategy is that it admits equal sub-packetization for all files while allowing the users to allocate more cache to the files which are more popular. This creates natural broadcasting opportunities in the delivery phase which are simultaneously helpful for the users who have requested files of different popularities. For the case of two files, we propose a new delivery strategy based on interference alignment which enables each user to decode his desired file following a two-layer peeling decoder. Furthermore, we extend the existing converse bounds for uniform demands under uncoded placement to the nonuniform case. To accomplish this, we construct N! auxiliary users, corresponding to all permutations of the N files, each caching carefully selected sub-packets of the files. Each auxiliary user provides a different converse bound. The overall converse bound is the maximum of all these N! bounds. We prove that our achievable delivery rate for the case of two files meets this converse, thereby establishing the optimal expected memory-rate trade-off for the case of K users and two files with arbitrary popularities under uncoded placement.
- 23 July 2019
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 65 (12) , 7756-7770
The Optimal Memory-Rate Trade-Off for the Non-Uniform Centralized Caching Problem With Two Files Under Uncoded Placement
A new scheme for the problem of centralized coded caching with non-uniform demands is proposed. The distinguishing feature of the proposed placement strategy is that it admits equal sub-packetization for all files while allowing the users to allocate more cache to the files which are more popular. This creates natural broadcasting opportunities in the delivery phase which are simultaneously helpful for the users who have requested files of different popularities. For the case of two files, we propose a new delivery strategy based on interference alignment which enables each user to decode his desired file following a two-layer peeling decoder. Furthermore, we extend the existing converse bounds for uniform demands under uncoded placement to the nonuniform case. To accomplish this, we construct N! auxiliary users, corresponding to all permutations of the N files, each caching carefully selected sub-packets of the files. Each auxiliary user provides a different converse bound. The overall converse bound is the maximum of all these N! bounds. We prove that our achievable delivery rate for the case of two files meets this converse, thereby establishing the optimal expected memory-rate trade-off for the case of K users and two files with arbitrary popularities under uncoded placement.
- 1 June 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1705-1709
Increasing Availability in Distributed Storage Systems via Clustering
We introduce the Fixed Cluster Repair System (FCRS) as a novel architecture for Distributed Storage Systems (DSS) that achieves a small repair bandwidth while guaranteeing a high availability. Specifically, we partition the set of servers in a DSS into s clusters and allow a failed server to choose any cluster other than its own as its repair group. Thereby, we guarantee an availability of s-1. We characterize the repair bandwidth vs. storage trade-off for the FCRS under functional repair and show that the minimum repair bandwidth can be improved by an asymptotic multiplicative factor of 2/3 compared to the state of the art coding techniques that guarantee the same availability. Furthermore, we introduce cubic codes designed to minimize the repair bandwidth of the FCRS under the exact repair model. We prove an asymptotic multiplicative improvement of 0.79 in the minimum repair bandwidth compared to the existing exact repair coding techniques that achieve the same availability. We show that cubic codes are information-theoretically optimal for the FCRS with 2 and 3 complete clusters. A full version of this paper is accessible at: https://arxiv.org/pdf/1710.02653.pdf.
- 1 June 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1705-1709
Increasing Availability in Distributed Storage Systems via Clustering
We introduce the Fixed Cluster Repair System (FCRS) as a novel architecture for Distributed Storage Systems (DSS) that achieves a small repair bandwidth while guaranteeing a high availability. Specifically, we partition the set of servers in a DSS into s clusters and allow a failed server to choose any cluster other than its own as its repair group. Thereby, we guarantee an availability of s-1. We characterize the repair bandwidth vs. storage trade-off for the FCRS under functional repair and show that the minimum repair bandwidth can be improved by an asymptotic multiplicative factor of 2/3 compared to the state of the art coding techniques that guarantee the same availability. Furthermore, we introduce cubic codes designed to minimize the repair bandwidth of the FCRS under the exact repair model. We prove an asymptotic multiplicative improvement of 0.79 in the minimum repair bandwidth compared to the existing exact repair coding techniques that achieve the same availability. We show that cubic codes are information-theoretically optimal for the FCRS with 2 and 3 complete clusters. A full version of this paper is accessible at: https://arxiv.org/pdf/1710.02653.pdf.
- Open Access
- 4 October 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 63 (12) , 7780-7792
Polynomially Solvable Instances of the Shortest and Closest Vector Problems With Applications to Compute-and-Forward
A particular instance of the shortest vector problem (SVP) appears in the context of compute-and-forward. Despite the NP-hardness of the SVP, we will show that this certain instance can be solved in complexity order O(nψ log(nψ)), where ψ = √P∥h∥ 2 + 1 depends on the transmission power and the norm of the channel vector. We will then extend our results to integer-forcing and finally introduce a more general class of lattices for which the SVP and the closest vector problem can be approximated within a constant factor.
- 4 October 2017
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 63 (12) , 7780-7792
Open AccessPolynomially Solvable Instances of the Shortest and Closest Vector Problems With Applications to Compute-and-Forward
A particular instance of the shortest vector problem (SVP) appears in the context of compute-and-forward. Despite the NP-hardness of the SVP, we will show that this certain instance can be solved in complexity order O(nψ log(nψ)), where ψ = √P∥h∥ 2 + 1 depends on the transmission power and the norm of the channel vector. We will then extend our results to integer-forcing and finally introduce a more general class of lattices for which the SVP and the closest vector problem can be approximated within a constant factor.
- 1 September 2016
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1012-1017
Multi-library coded caching
We study the problem of coded caching when the server has access to several libraries and each user makes independent requests from every library. The single-library scenario has been well studied and it has been proved that coded caching can significantly improve the delivery rate compared to uncoded caching. In this work we show that when all the libraries have the same number of files, memory-sharing is optimal and the delivery rate cannot be improved via coding across files from different libraries. In this setting, the optimal memory-sharing strategy is one that divides the cache of each user proportional to the size of the files in different libraries. As for the general case, when the number of files in different libraries are arbitrary, we propose an inner-bound based on memory-sharing and an outer-bound based on concatenation of files from different libraries.
- 1 September 2016
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1012-1017
Multi-library coded caching
We study the problem of coded caching when the server has access to several libraries and each user makes independent requests from every library. The single-library scenario has been well studied and it has been proved that coded caching can significantly improve the delivery rate compared to uncoded caching. In this work we show that when all the libraries have the same number of files, memory-sharing is optimal and the delivery rate cannot be improved via coding across files from different libraries. In this setting, the optimal memory-sharing strategy is one that divides the cache of each user proportional to the size of the files in different libraries. As for the general case, when the number of files in different libraries are arbitrary, we propose an inner-bound based on memory-sharing and an outer-bound based on concatenation of files from different libraries.
- 1 March 2016
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 620-624
K users caching two files: An improved achievable rate
Caching is an approach to smoothen the variability of traffic over time. Recently it has been proved that the local memories at the users can be exploited for reducing the peak traffic in a much more efficient way than previously believed. In this work we improve upon the existing results and introduce a novel caching strategy that takes advantage of simultaneous coded placement and coded delivery in order to decrease the worst case achievable rate with 2 files and K users. We will show that for any cache size 1/K <; M <; 1 our scheme outperforms the state of the art.
- 1 March 2016
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 620-624
K users caching two files: An improved achievable rate
Caching is an approach to smoothen the variability of traffic over time. Recently it has been proved that the local memories at the users can be exploited for reducing the peak traffic in a much more efficient way than previously believed. In this work we improve upon the existing results and introduce a novel caching strategy that takes advantage of simultaneous coded placement and coded delivery in order to decrease the worst case achievable rate with 2 files and K users. We will show that for any cache size 1/K <; M <; 1 our scheme outperforms the state of the art.
- 1 September 2014
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 290, 227-233
Compute-and-Forward: Finding the best equation
Compute-and-Forward is an emerging technique to deal with interference. It allows the receiver to decode a suitably chosen integer linear combination of the transmitted messages. The integer coefficients should be adapted to the channel fading state. Optimizing these coefficients is a Shortest Lattice Vector (SLV) problem. In general, the SLV problem is known to be prohibitively complex. In this paper, we show that the particular SLV instance resulting from the Compute-and-Forward problem can be solved in low polynomial complexity and give an explicit deterministic algorithm that is guaranteed to find the optimal solution.
- 1 September 2014
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 290, 227-233
Compute-and-Forward: Finding the best equation
Compute-and-Forward is an emerging technique to deal with interference. It allows the receiver to decode a suitably chosen integer linear combination of the transmitted messages. The integer coefficients should be adapted to the channel fading state. Optimizing these coefficients is a Shortest Lattice Vector (SLV) problem. In general, the SLV problem is known to be prohibitively complex. In this paper, we show that the particular SLV instance resulting from the Compute-and-Forward problem can be solved in low polynomial complexity and give an explicit deterministic algorithm that is guaranteed to find the optimal solution.
- 1 May 2010
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15503607,p. 1-5
Effect of Power Randomization on Saturation Throughput of IEEE 802.11 WLAN
In this paper, we evaluate the saturation throughput for an IEEE 802.11 based wireless network considering capture effect at the receiver, while nodes transmit with random powers. In this respect, we consider a scenario consisting of a specific number of wireless nodes. Then, we derive the transmission as well as collision probabilities with respect to the perfect capture effect. In order to maximize the saturation throughput we set up an optimization problem and obtain how to compute optimum values for the probabilities corresponding to different power levels. By providing the numerical results, we deduce that power randomization may lead to a significant improvement in saturation throughput.
- 1 May 2010
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15503607,p. 1-5
Effect of Power Randomization on Saturation Throughput of IEEE 802.11 WLAN
In this paper, we evaluate the saturation throughput for an IEEE 802.11 based wireless network considering capture effect at the receiver, while nodes transmit with random powers. In this respect, we consider a scenario consisting of a specific number of wireless nodes. Then, we derive the transmission as well as collision probabilities with respect to the perfect capture effect. In order to maximize the saturation throughput we set up an optimization problem and obtain how to compute optimum values for the probabilities corresponding to different power levels. By providing the numerical results, we deduce that power randomization may lead to a significant improvement in saturation throughput.