Elad Verbin

According to our database, Elad Verbin authored at least 30 papers between 2003 and 2016.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2016

Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy.

Jeff M. Phillips, Elad Verbin, Qin Zhang

SIAM J. Comput., 2016

2013

Pseudorandomness for Width-2 Branching Programs.

Andrej Bogdanov, Zeev Dvir, Elad Verbin, Amir Yehudayoff

Theory Comput., 2013

The Limits of Buffering: A Tight Lower Bound for Dynamic Membership in the External Memory Model.

Elad Verbin, Qin Zhang

SIAM J. Comput., 2013

Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings.

Elad Verbin, Wei Yu

Proceedings of the Combinatorial Pattern Matching, 24th Annual Symposium, 2013

2012

Approximating the minmax value of 3-player games within a constant is as hard as detecting planted cliques.

Kord Eickmeyer, Kristoffer Arnsfelt Hansen, Elad Verbin

Electron. Colloquium Comput. Complex., 2012

Data Structure Lower Bounds on Random Access to Grammar-Compressed Strings

Shiteng Chen, Elad Verbin, Wei Yu

CoRR, 2012

Approximating the Minmax Value of Three-Player Games within a Constant is as Hard as Detecting Planted Cliques.

Kord Eickmeyer, Kristoffer Arnsfelt Hansen, Elad Verbin

Proceedings of the Algorithmic Game Theory - 5th International Symposium, 2012

Rademacher-Sketch: A Dimensionality-Reducing Embedding for Sum-Product Norms, with an Application to Earth-Mover Distance.

Elad Verbin, Qin Zhang

Proceedings of the Automata, Languages, and Programming - 39th International Colloquium, 2012

2011

Sorting and Selection in Posets.

Constantinos Daskalakis, Richard M. Karp, Elchanan Mossel, Samantha J. Riesenfeld, Elad Verbin

SIAM J. Comput., 2011

The Streaming Complexity of Cycle Counting, Sorting by Reversals, and Other Problems.

Elad Verbin, Wei Yu

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

2010

New results in stringology: Burrows-Wheeler compression and sorting by reversals

Elad Verbin

PhD thesis, 2010

Surviving Rates of Graphs with Bounded Treewidth for the Firefighter Problem.

Leizhen Cai, Yongxi Cheng, Elad Verbin, Yuan Zhou

SIAM J. Discret. Math., 2010

The Coin Problem and Pseudorandomness for Branching Programs.

Joshua Brody, Elad Verbin

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Querying DAG-shaped Execution Traces Through Views.

Maya Ben-Ari, Tova Milo, Elad Verbin

Proceedings of the 12th International Workshop on the Web and Databases, 2009

Distance Oracles for Sparse Graphs.

Christian Sommer, Elad Verbin, Wei Yu

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Optimized union of non-disjoint distributed data sets.

Itay Dar, Tova Milo, Elad Verbin

Proceedings of the EDBT 2009, 2009

Network coding is highly non-approximable.

Hongyi Yao, Elad Verbin

Proceedings of the 47th Annual Allerton Conference on Communication, 2009

2008

Efficient Colored Orthogonal Range Counting.

Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin

SIAM J. Comput., 2008

Compact samples for data dissemination.

Tova Milo, Assaf Sagi, Elad Verbin

J. Comput. Syst. Sci., 2008

On agnostic boosting and parity learning.

Adam Tauman Kalai, Yishay Mansour, Elad Verbin

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

Firefighting on Trees: (1-1/e)-Approximation, Fixed Parameter Tractability and a Subexponential Algorithm.

Leizhen Cai, Elad Verbin, Lin Yang

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

2007

A simpler analysis of Burrows-Wheeler-based compression.

Haim Kaplan, Shir Landau, Elad Verbin

Theor. Comput. Sci., 2007

Counting colors in boxes.

Haim Kaplan, Natan Rubin, Micha Sharir, Elad Verbin

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Boosting topic-based publish-subscribe systems with dynamic clustering.

Tova Milo, Tal Zur, Elad Verbin

Proceedings of the ACM SIGMOD International Conference on Management of Data, 2007

Most Burrows-Wheeler Based Compressors Are Not Optimal.

Haim Kaplan, Elad Verbin

Proceedings of the Combinatorial Pattern Matching, 18th Annual Symposium, 2007

2006

Matrix Tightness: A Linear-Algebraic Framework for Sorting by Transpositions.

Tzvika Hartman, Elad Verbin

Proceedings of the String Processing and Information Retrieval, 2006

Colored intersection searching via sparse rectangular matrix multiplication.

Haim Kaplan, Micha Sharir, Elad Verbin

Proceedings of the 22nd ACM Symposium on Computational Geometry, 2006

2005

Sorting signed permutations by reversals, revisited.

Haim Kaplan, Elad Verbin

J. Comput. Syst. Sci., 2005

On the complexity of cell flipping in permutation diagrams and multiprocessor scheduling problems.

Martin Charles Golumbic, Haim Kaplan, Elad Verbin

Discret. Math., 2005

2003

Efficient Data Structures and a New Randomized Approach for Sorting Signed Permutations by Reversals.

Haim Kaplan, Elad Verbin

Proceedings of the Combinatorial Pattern Matching, 14th Annual Symposium, 2003