**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Person# Javad Ebrahimi Boroojeni

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related units

Loading

Courses taught by this person

Loading

Related research domains

Loading

Related publications

Loading

People doing similar research

Loading

Courses taught by this person

No results

Related research domains (8)

Algorithm

In mathematics and computer science, an algorithm (ˈælɡərɪðəm) is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algo

Algebraic geometry

Algebraic geometry is a branch of mathematics which classically studies zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly fro

Vector quantization

Vector quantization (VQ) is a classical quantization technique from signal processing that allows the modeling of probability density functions by the distribution of prototype vectors. It was origina

Related publications (12)

Loading

Loading

Loading

People doing similar research (99)

Related units (3)

Ahlswede et al. in the seminal paper [1] have shown that in data transfer over networks, processing the data at the nodes can significantly improve the throughput. As proved by Li et al. in [2], even with a simple type of operation, namely linear operation, the throughput can still be vastly improved. In [3], it is shown that the multicasting problem over networks can be translated to an algebraic question about a polynomial associated to the network called network polynomial. In this thesis, we start from the algorithm of [3] and extend it in several directions. First, we generalize the framework of [3] to include the case where the messages can also be vectors over some fixed finite field. We also show that in contrast to the original algorithm, ours can be used to reduce the field size for the case of sending finite field elements. In both vector network code algorithm and finite field minimization, we translate the network code design problems into an algebraic problem about network polynomials. Because of the importance of the network polynomials, we investigate more properties of them and we study the relationship between these objects and the topological properties of the network. Then, we extend the result of [3] to the deterministic models for wireless relay networks, a very important class of networks that has been introduced in [4] by Avestimehr, Diggavi and Tse. Finally, for another class of networks, called broadcast networks, we introduce the transfer matrix and using its properties, we show that in the absence of public messages, processing the information at the nodes will not improve the throughput.

Javad Ebrahimi Boroojeni, Damian Mateusz Straszak, Nisheeth Vishnoi

Several fundamental problems that arise in optimization and computer science can be cast as follows: Given vectors v(1), ..., v(m) is an element of R-d and a constraint family B subset of 2([m]), find a set S. B that maximizes the squared volume of the simplex spanned by the vectors in S. A motivating example is the ubiquitous data-summarization problem in machine learning and information retrieval where one is given a collection of feature vectors that represent data such as documents or images. The volume of a collection of vectors is used as a measure of their diversity, and partition or matroid constraints over [m] are imposed in order to ensure resource or fairness constraints. Even with a simple cardinality constraint (B = (([m])(r))), the problem becomes NP-hard and has received much attention starting with a result by Khachiyan [1] who gave an r(O(r)) approximation algorithm for this problem. Recently, Nikolov and Singh [2] presented a convex program and showed how it can be used to estimate the value of the most diverse set when there are multiple cardinality constraints (i.e., when B corresponds to a partition matroid). Their proof of the integrality gap of the convex program relied on an inequality by Gurvits [3], and was recently extended to regular matroids [4], [5]. The question of whether these estimation algorithms can be converted into the more useful approximation algorithms - that also output a set - remained open. The main contribution of this paper is to give the first approximation algorithms for both partition and regular matroids. We present novel formulations for the subdeterminant maximization problem for these matroids; this reduces them to the problem of finding a point that maximizes the absolute value of a nonconvex function over a Cartesian product of probability simplices. The technical core of our results is a new anti-concentration inequality for dependent random variables that arise from these functions which allows us to relate the optimal value of these nonconvex functions to their value at a random point. Unlike prior work on the constrained subdeterminant maximization problem, our proofs do not rely on real-stability or convexity and could be of independent interest both in algorithms and complexity where anti-concentration phenomena has recently been deployed.

Determining the size of a maximum independent set of a graph G, denoted by alpha(G), is an NP-hard problem. Therefore many attempts are made to find upper and lower bounds, or exact values of alpha(G) for special classes of graphs. This paper is aimed toward studying this problem for the class of generalized Petersen graphs. We find new upper and lower bounds and some exact values for alpha(P(n, k)). With a computer program we have obtained exact values for each n < 78. In [2] it is conjectured that the size of the minimum vertex cover, beta(P(n, k)), is less than or equal to n + inverted right perpendicular n/5 inverted left perpendicular, for all n and k with n > 2k. We prove this conjecture for some cases. In particular, we show that if n > 3k, the conjecture is valid. We checked the conjecture with our table for n < 78 and it had no inconsistency. Finally, we show that for every fixed k, alpha(P(n,k)) can be computed using an algorithm with running time O(n).