| Publication | Date of Publication | Type |
|---|
| Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states | 2026-05-29 | Paper |
| A lower bound for the bounded round quantum communication complexity of set disjointness | 2026-05-29 | Paper |
| Subspace polynomials and list decoding of Reed-Solomon codes | 2026-05-29 | Paper |
| Tight bounds for depth-two superconcentrators | 2026-05-21 | Paper |
| The quantum complexity of set membership | 2026-05-08 | Paper |
| Improved bounds and algorithms for hypergraph two-coloring | 2025-10-29 | Paper |
| Parametric shortest paths in planar graphs | 2025-08-12 | Paper |
| Topology matters in communication | 2025-08-05 | Paper |
| Split and join: strong partitions and universal Steiner trees for graphs | 2025-05-05 | Paper |
| scientific article; zbMATH DE number 7799609 (Why is no real title available?) | 2024-02-05 | Paper |
The randomized complexity of maintaining the minimum
Algorithm Theory — SWAT'96 | 2022-12-09 | Paper |
Improved approximations of independent sets in bounded-degree graphs
Algorithm Theory — SWAT '94 | 2022-12-09 | Paper |
| Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes | 2022-07-18 | Paper |
Bounds on the Zero-Error List-Decoding Capacity of the <i>q</i>/(<i>q</i> – 1) Channel
IEEE Transactions on Information Theory | 2022-02-17 | Paper |
Distance-preserving subgraphs of interval graphs
(available as arXiv preprint) | 2020-05-27 | Paper |
An Improved Bound on the Zero-Error List-Decoding Capacity of the 4/3 Channel
IEEE Transactions on Information Theory | 2020-01-28 | Paper |
Minimizing branching vertices in distance-preserving subgraphs
(available as arXiv preprint) | 2019-10-22 | Paper |
| Finding duplicates in a data stream | 2019-05-06 | Paper |
Separation between deterministic and randomized query complexity
SIAM Journal on Computing | 2018-09-18 | Paper |
The Zero-Error Randomized Query Complexity of the Pointer Function
(available as arXiv preprint) | 2018-04-19 | Paper |
Set membership with non-adaptive bit probes
(available as arXiv preprint) | 2018-04-19 | Paper |
Partition bound is quadratically tight for product distributions
(available as arXiv preprint) | 2017-12-19 | Paper |
| Tight bounds for communication-assisted agreement distillation | 2017-10-10 | Paper |
Set membership with a few bit probes
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
The Communication Complexity of Correlation
IEEE Transactions on Information Theory | 2017-07-27 | Paper |
Subspace Polynomials and Limits to List Decoding of Reed–Solomon Codes
IEEE Transactions on Information Theory | 2017-07-27 | Paper |
The communication complexity of pointer chasing: applications of entropy and sampling
1345.68133 | 2016-09-29 | Paper |
Greed is good: approximating independent sets in sparse and bounded-degree graphs
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
A property of quantum relative entropy with an application to privacy in quantum communication
Journal of the ACM | 2015-11-11 | Paper |
Online set packing and competitive scheduling of multi-part tasks
Proceedings of the 29th ACM SIGACT-SIGOPS symposium on Principles of distributed computing | 2015-03-02 | Paper |
| Complete partitions of graphs | 2014-10-13 | Paper |
Expansion properties of (secure) wireless networks
ACM Transactions on Algorithms | 2014-09-09 | Paper |
More on a problem of Zarankiewicz
Algorithms and Computation | 2013-03-21 | Paper |
Online set packing
SIAM Journal on Computing | 2012-11-29 | Paper |
Streaming algorithms for 2-coloring uniform hypergraphs
Lecture Notes in Computer Science | 2011-08-12 | Paper |
Data structures for storing small sets in the bitprobe model
Algorithms – ESA 2010 | 2010-09-06 | Paper |
| scientific article; zbMATH DE number 5764909 (Why is no real title available?) | 2010-08-06 | Paper |
| scientific article; zbMATH DE number 5764851 (Why is no real title available?) | 2010-08-06 | Paper |
Random measurement bases, quantum state distinction and applications to the hidden subgroup problem
Algorithmica | 2009-08-31 | Paper |
Gap Amplification in PCPs Using Lazy Random Walks
Automata, Languages and Programming | 2009-03-12 | Paper |
Complete partitions of graphs
Combinatorica | 2008-10-21 | Paper |
Zero Error List-Decoding Capacity of the q/(q–1) Channel
FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science | 2008-04-17 | Paper |
Tradeoffs in Depth-Two Superconcentrators
STACS 2006 | 2008-03-19 | Paper |
Mathematical Foundations of Computer Science 2003
Lecture Notes in Computer Science | 2007-12-07 | Paper |
On Dinur’s proof of the PCP theorem
Bulletin of the American Mathematical Society | 2007-03-21 | Paper |
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2006-07-07 | Paper |
Automata, Languages and Programming
Lecture Notes in Computer Science | 2006-01-10 | Paper |
On converting CNF to DNF
Theoretical Computer Science | 2005-12-29 | Paper |
Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons
Journal of Computer and System Sciences | 2005-12-07 | Paper |
Lower bounds for adaptive locally decodable codes
Random Structures & Algorithms | 2005-11-15 | Paper |
Essential covers of the cube by hyperplanes
Journal of Combinatorial Theory. Series A | 2005-04-06 | Paper |
| Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem | 2004-08-04 | Paper |
Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem
(available as arXiv preprint) | 2004-08-04 | Paper |
| scientific article; zbMATH DE number 2079403 (Why is no real title available?) | 2004-07-28 | Paper |
| scientific article; zbMATH DE number 2038719 (Why is no real title available?) | 2004-02-08 | Paper |
A note on scrambling permutations
Random Structures & Algorithms | 2003-07-31 | Paper |
| scientific article; zbMATH DE number 1954386 (Why is no real title available?) | 2003-07-28 | Paper |
| scientific article; zbMATH DE number 1875423 (Why is no real title available?) | 2003-03-02 | Paper |
A tradeoff between search and update in dictionaries
Information Processing Letters | 2002-07-25 | Paper |
The communication complexity of pointer chasing
Journal of Computer and System Sciences | 2002-07-10 | Paper |
Bounds for Dispersers, Extractors, and Depth-Two Superconcentrators
SIAM Journal on Discrete Mathematics | 2000-03-19 | Paper |
| scientific article; zbMATH DE number 1354144 (Why is no real title available?) | 1999-10-31 | Paper |
| scientific article; zbMATH DE number 1256702 (Why is no real title available?) | 1999-08-08 | Paper |
| scientific article; zbMATH DE number 1256716 (Why is no real title available?) | 1999-05-18 | Paper |
The complexity of parallel prefix problems on small domains
Information and Computation | 1998-06-02 | Paper |
Greed is good: Approximating independent sets in sparse and bounded-degree graphs
Algorithmica | 1997-07-20 | Paper |
Better lower bounds for monotone threshold formulas
Journal of Computer and System Sciences | 1997-06-16 | Paper |
| scientific article; zbMATH DE number 1002203 (Why is no real title available?) | 1997-04-22 | Paper |
Pi-sigma-pi threshold formulas
Mathematical Systems Theory | 1996-12-12 | Paper |
| scientific article; zbMATH DE number 753971 (Why is no real title available?) | 1995-08-06 | Paper |
\(\Sigma\Pi\Sigma\) threshold formulas
Combinatorica | 1994-12-11 | Paper |
Directed monotone contact networks for threshold functions
Information Processing Letters | 1994-06-15 | Paper |
Improved bounds for covering complete uniform hypergraphs
Information Processing Letters | 1992-09-26 | Paper |
