Sharif Digital Repository

In the communication problem UR (universal relation), Alice and Bob respectively receive x, y {0,1}^n with the promise that xy. The last player to receive a message must output an index i such that x-iy-i. We prove that the randomized one-way communication complexity of this problem in the public coin model is exactly Θ(min{n,log(1/Δ)log^2(rac n{log(1/Δ)})}) for failure probability Δ. Our lower bound holds even if promised mathop{support}(y)mathop{support}(x). As a corollary, we obtain optimal lower bounds for -p-sampling in strict turnstile streams for 0le p streams for 0 ≤ p © 2017 IEEE  

In this article, we find a lower bound for the blow-up time of solutions to some nonlinear parabolic equations under Robin boundary conditions in bounded domains of Rn  

Let S be a set S of n points on a polyhedral terrain T in R3, and let ϵ > 0 be a fixed constant. We prove that S admits a (2 + ϵ)-spanner with O(n log n) edges with respect to the geodesic distance. This is the first spanner with constant spanning ratio and a near-linear number of edges for points on a terrain. On our way to this result, we prove that any set of n weighted points in Rd admits an additively weighted (2 + ϵ)-spanner with O(n) edges; this improves the previously best known bound on the spanning ratio (which was 5 + ϵ), and almost matches the lower bound. Copyright © by SIAM  

In this paper a lower bounding method for the flowshop sequence dependentgroups scheduling problems by minimization of makespan criterion (Fm|fmls, Sijkprmu|Cmax) is proposed. Theperformance of the proposed lower bound (LB) is compared with the availablelower bounding methods in literature. In order to do this, the performance ofthe proposed LB and the one available in literature are compared with theavailable upper bound in literature based on solving the available testproblems. The results show that the proposed LB has a superior performancecompared to the available ones in literature. The average percentage error ofthe proposed LB for the test problems is 1.1% and 1.4% for three and six... 

This research considers a flexible flowshop sequence-dependent group scheduling problem with minimization of total completion time. A mixed integer linear mathematical model for the research problem is developed. Since the research problem is shown to be strongly NP-hard, a metaheuristic algorithm based on memetic algorithm (MA) is proposed. A lower bounding method based on the Branch and Price algorithm is also proposed to evaluate the quality of the MA. In order to evaluate the performance of the proposed algorithms, random test problems, ranging in size from small, medium, to large are generated and solved by the MA and the lower bounding method. The results show that the average... 

In this paper the Output Statistics of Random Binning (OSRB) framework is used to prove a new inner bound for the problem of secure channel simulation. Our results subsume some recent results on the secure function computation. We also provide an achievability result for the problem of simultaneously simulating a channel and creating a shared secret key. A special case of this result generalizes the lower bound of Gohari and Anantharam on the source model to include constraints on the rates of the public discussion  

We provide upper and lower bounds on the escape rate of the Bhattacharyya process corresponding to polar codes where transmission takes place over the the binary erasure channel. More precisely, we bound the exponent of the number of sub-channels whose Bhattacharyya constant falls in a fixed interval [a, b]. Mathematically this can be stated as bounding the limit limn →∞ 1/n ln ℙ(Zn ∈ [a,b]), where Z n is the Bhattacharyya process. The quantity ℙ (Zn ∈ [a,b]) represents the fraction of sub-channels that are still un-polarized at time n  

The goal of derivative sampling is to reconstruct a signal from the samples of the function and of its first-order derivative. In this paper, we consider this problem over a shift-invariant reconstruction subspace generated by two compact-support functions. We assume that the reconstruction subspace reproduces polynomials up to a certain degree. We then derive a lower bound on the sum of supports of its generators. Finally, we illustrate the tightness of our bound with some examples  

Given a set P of n points in the plane, the all nearest neighbors problem asks for finding the closest point in P for each point in the set. The following folklore algorithm is used for the problem in practice: Pick a line in a random direction, project all points onto the line, and then search for the nearest neighbor of each point in a small vicinity of that point on the line. It is widely believed that the expected number of points needed to be checked by the algorithm in the vicinity of each point is O(pn) on average. We confirm this conjecture in affirmative by providing a careful analysis on the expected number of comparisons made by the algorithm. We also present a matching lower... 

Let S be a set of n points on a polyhedral terrain T in ℝ3, and let ϵ > 0 be a fixed constant. We prove that S admits a (2 + ϵ )-spanner with O(n log n) edges with respect to the geodesic distance. This is the first spanner with constant spanning ratio and a near-linear number of edges for points on a terrain. On our way to this result, we prove that any set of n weighted points in Rd admits an additively weighted (2 + ϵ )-spanner with O(n) edges; this improves the previously best known bound on the spanning ratio (which was 5 + ϵ ) and almost matches the lower bound. © 2019 Society for Industrial and Applied Mathematics Publications. All rights reserved  

Given a set P of n points in the plane, the all nearest neighbors problem asks for finding the closest point in P for each point in the set. The following folklore algorithm is used for the problem in practice: Pick a line in a random direction, project all points onto the line, and then search for the nearest neighbor of each point in a small vicinity of that point on the line. It is widely believed that the expected number of points needed to be checked by the algorithm in the vicinity of each point is O(pn) on average. We confirm this conjecture in affirmative by providing a careful analysis on the expected number of comparisons made by the algorithm. We also present a matching lower... 

Let S be a set of n points on a polyhedral terrain T in ℝ3, and let ϵ > 0 be a fixed constant. We prove that S admits a (2 + ϵ )-spanner with O(n log n) edges with respect to the geodesic distance. This is the first spanner with constant spanning ratio and a near-linear number of edges for points on a terrain. On our way to this result, we prove that any set of n weighted points in Rd admits an additively weighted (2 + ϵ )-spanner with O(n) edges; this improves the previously best known bound on the spanning ratio (which was 5 + ϵ ) and almost matches the lower bound. © 2019 Society for Industrial and Applied Mathematics Publications. All rights reserved  

In this research, the flexible flowshop sequence-dependent group scheduling problem with minimisation of makespan as the criterion (FFm|fmls, shgi|Cmax) is investigated. A mixed integer linear mathematical model for the research problem is developed. Since the research problem is shown to be NP-hard, a meta-heuristic algorithm based on memetic algorithm (MA) is developed to efficiently solve the problem. Also, a lower bounding technique based on the developed mathematical model is proposed to evaluate the quality of the proposed MA. The performance of the proposed MA is compared with the existing algorithm in the literature, i.e. tabu search (TS), by solving the available test problems in... 

Global System for Mobile communications (GSM) is a widely spread, reliable and P2P channel through all over the world. These characteristics make GSM a channel suitable for a variety of applications in different domains especially security applications such as secure voice communication. Performance and usage of GSM applications extremely depends on the transmission data rate. Hence, transmitting data over GSM is still an attractive topic for research. This paper considers the problem of digital data transmission through the GSM voice channel. A lower capacity bound for data transmission through the GSM Adaptive Multi Rate (AMR) voice codec is presented. The GSM channel is modeled in a... 

We study Nash equilibria in the setting of network creation games introduced recently by Fabrikant, Luthra, Maneva, Papadimitriou, and Shenker. In this game we have a set of selfish node players, each creating some incident links, and the goal is to minimize α times the cost of the created links plus sum of the distances to all other players. Fabrikant et al. proved an upper bound O(√α) on the price of anarchy: the relative cost of the lack of coordination. Albers, Eilts, Even-Dar, Mansour, and Roditty show that the price of anarchy is constant for α = O(√n) and for α ≥ 12n[lgn], and that the price of anarchy is 15(1 + (min{α/n, n 2/alpha;}) 1/3) for any α. The latter bound shows the first... 

Recently, there has been a growing interest in estimation of sparse channels as they are observed in underwater acoustic and ultrawideband channels. In this paper we present a new Bayesian sparse channel estimation (SCE) algorithm that, unlike traditional SCE methods, exploits noise statistical information to improve the estimates. The proposed method uses approximate maximum a posteriori probability (MAP) to detect the non-zero channel tap locations while least square estimation is used to determine the values of the channel taps. Computer simulations shows that the proposed algorithm outperforms the existing algorithms in terms of normalized mean squared error (NMSE) and approaches... 

The Cramer-Rao lower bound for source localization based on Time Difference of Arrival and Frequency Difference of Arrival is investigated in this paper. The result is used for theoretical analysis of optimality in sensor placement. An optimal sensor-target geometry including sensors locations and velocities is presented and its properties is studied  

In this letter, we explore blind interference alignment (BIA) for the K-user single-input and single-output interference channel. We show that if we implement the structure of reconfigurable antennas at the receivers, by increasing the number of reception modes, the chance of finding proper channel conditions to align most part of interference signals will increase. Throughout this letter, we use the antenna structure of media-based modulation as reconfigurable antenna structure of the receivers. In this method, the receivers try to find proper channel states to align interference signals in an opportunistic manner. The results of this letter show that our proposed method has higher capacity... 

We propose a scheme for distillation of free bipartite entanglement from bipartite bound entangled states. The crucial element of our scheme is an ancillary system that is coupled to the initial bound entangled state via appropriate weak measurements. We show that in this protocol free entanglement can be always generated with nonzero probability by using a single copy of the bound entangled state. We also derive a lower bound on the entanglement cost of the protocol and conclude that, on average, applying weaker measurements results in relatively higher values of free entanglement as well as lower costs