Publications by Amin Karbasi | EPFL Graph Search

Related publications (23)

Compressed Sensing with Probabilistic Measurements: A Group Testing Solution

Martin Vetterli, Amin Karbasi, Ali Hormati, Mahdi Cheraghchi Bashi Astaneh

Detection of defective members of large populations has been widely studied in the statistics community under the name ``group testing'', a problem which dates back to World War~II when it was suggested for syphilis screening. There the main interest is to ...

2009

Learning Neural Connectivity from Firing Activity: Scalable Algorithms with Provable Guarantees

Martin Vetterli, Amin Karbasi, Amir Hesam Salavati

The connectivity of a neuronal network has a major effect on its functionality and role. It is generally believed that the complex network structure of the brain provides a physiological basis for information processing. Therefore, identifying the network’ ...

Springer New York LLC2018

Compression with Graphical Constraints: An Interactive Browser

Amin Karbasi, Morteza Zadimoghaddam

We study the problem of navigating/searching through a database of objects with potentially different popularities using a membership oracle. The membership oracle, given a subset of objects

A

, and a target object

t

, determines whether

A

contains

t

...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2011

Graph-Constrained Group Testing

Amin Karbasi, Mahdi Cheraghchi Bashi Astaneh, Soheil Mohajerzefreh

Non-adaptive group testing involves grouping arbitrary subsets of

n

items into different pools and identifying defective items based on tests obtained for each pool. Motivated by applications in network tomography, sensor networks and infection propagati ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2010

Comparison-Based Learning with Rank Nets

Amin Karbasi

We consider the problem of search through comparisons, where a user is presented with two candidate objects and reveals which is closer to her intended target. We study adaptive strategies for finding the target, that require knowledge of rank relationship ...

2012

Graph-Based Information Processing : Scaling Laws and Applications

Amin Karbasi

We live in a world characterized by massive information transfer and real-time communication. The demand for efficient yet low-complexity algorithms is widespread across different fields, including machine learning, signal processing and communications. Mo ...

EPFL2012

Asynchronous Decoding of LDPC Codes over BEC

Amin Karbasi, Amir Hesam Salavati, Saeid Haghighatshoar

LDPC codes are typically decoded by running a synchronous message passing algorithm over the corresponding bipartite factor graph (made of variable and check nodes). More specifically, each synchronous round consists of 1) updating all variable nodes based ...

2015

Robust Localization from Incomplete Local Information

Amin Karbasi

We consider the problem of localizing wireless devices in an ad-hoc network embedded in a

d

-dimensional Euclidean space. Obtaining a good estimation of where wireless devices are located is crucial in wireless network applications including environment m ...

Ieee-Inst Electrical Electronics Engineers Inc2013

Low-rank Matrix Approximation Using Point-wise Operators

Amin Karbasi, Arash Amini

Extracting low dimensional structure from high dimensional data arises in many applications such as machine learning, statistical pattern recognition, wireless sensor networks, and data compression. If the data is restricted to a lower dimensional subspace ...

Institute of Electrical and Electronics Engineers2012

Noise-enhanced associative memories

Mohammad Amin Shokrollahi, Amin Karbasi, Amir Hesam Salavati

Recent advances in associative memory design through structured pattern sets and graph-based inference algorithms have allowed reliable learning and recall of an exponential number of patterns. Although these designs correct external errors in recall, they ...

2013

Distributed Sensor Network Localization from Local Connectivity: Performance Analysis for the HOP-TERRAIN Algorithm

Amin Karbasi

This paper addresses the problem of determining the node locations in ad-hoc sensor networks when only connectivity information is available. In previous work, we showed that the localization algorithm MDS-MAP proposed by Y. Shang et al. is able to localiz ...

2010

Multi-Level Error-Resilient Neural Networks

Amin Karbasi, Amir Hesam Salavati

The problem of neural network association is to retrieve a previously memorized pattern from its noisy version using a network of neurons. An ideal neural network should include three components simultaneously: a learning algorithm, a large pattern retriev ...

IEEE2012

Group Testing with Probabilistic Tests: Theory, Design and Application

Martin Vetterli, Amin Karbasi, Ali Hormati, Mahdi Cheraghchi Bashi Astaneh

Identification of defective members of large populations has been widely studied in the statistics community under the name of group testing. It involves grouping subsets of items into different pools and detecting defective members based on the set of tes ...

Institute of Electrical and Electronics Engineers2011

Graph-Constrained Group Testing

Amin Karbasi, Mahdi Cheraghchi Bashi Astaneh, Soheil Mohajerzefreh

Non-adaptive group testing involves grouping arbitrary subsets of

n

items into different pools. Each pool is then tested and defective items are identified. A fundamental question involves minimizing the number of pools required to identify at most

d

d ...

2012

Greedy Scheduling for Distributed Computing Clusters

Milan Vojnovic, Amin Karbasi

Allocating tasks to machines in computing clusters is described. In an embodiment a set of tasks associated with a job are received at a scheduler. In an embodiment an index can be computed for each combination of tasks and processors and stored in a looku ...

2011

Sequential Group Testing with Graph Constraints

Amin Karbasi, Morteza Zadimoghaddam

In conventional group testing, the goal is to detect a small subset of defecting items

\mathcal{D}

in a large population

\mathcal{N}

by grouping \textit{arbitrary} subset of

\mathcal{N}

into different pools. The result of each group test $\mathcal{T} ...

Ieee2012

Coupled neural associative memories

Mohammad Amin Shokrollahi, Amin Karbasi, Amir Hesam Salavati

We propose a novel architecture to design a neural associative memory that is capable of learning a large number of patterns and recalling them later in presence of noise. It is based on dividing the neurons into local clusters and parallel plains, an arch ...

IEEE2013

Constrained Binary Identification Problem

Amin Karbasi, Morteza Zadimoghaddam

We consider the problem of building a binary decision tree, to locate an object within a set by way of the least number of membership queries. This problem is equivalent to the “20 questions game” of information theory and is closely related to lossless so ...

2013

Calibration Using Matrix Completion with Application to Ultrasound Tomography

Martin Vetterli, Amin Karbasi, Reza Parhizkar

We study the calibration process in circular ultrasound tomography devices where the sensor positions deviate from the circumference of a perfect circle. This problem arises in a variety of applications in signal processing ranging from breast imaging to s ...

Institute of Electrical and Electronics Engineers2013

Calibration in Circular Ultrasound Tomography Devices

Martin Vetterli, Amin Karbasi, Reza Parhizkar

We consider the position calibration problem in circular tomography devices, where sensors deviate from a perfect circle. We introduce a new method of calibration based on the time-of-flight measurements between sensors when the enclosed medium is homogene ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2011