| Publication | Date of Publication | Type |
|---|
| On randomized reductions to the random strings | 2024-07-05 | Paper |
| Simple, deterministic, fast (but weak) approximations to edit distance and Dyck edit distance | 2024-05-14 | Paper |
Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time
Journal of the ACM | 2022-12-08 | Paper |
| Circuit lower bounds from NP-hardness of MCSP under turing reductions | 2022-07-21 | Paper |
On the rational relationships among pseudo-roots of a non-commutative polynomial
Journal of Pure and Applied Algebra | 2021-03-03 | Paper |
Constant factor approximations to edit distance on far input pairs in nearly linear time
Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing | 2021-01-19 | Paper |
An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function
Combinatorica | 2020-10-02 | Paper |
On the discrepancy of random matrices with many columns
Random Structures & Algorithms | 2020-09-16 | Paper |
Lower bounds for combinatorial algorithms for Boolean matrix multiplication
(available as arXiv preprint) | 2020-08-05 | Paper |
On online labeling with large label set
SIAM Journal on Discrete Mathematics | 2019-08-29 | Paper |
Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
| Online labeling: algorithms, lower bounds and open questions | 2018-11-28 | Paper |
| On FKG-type and permanental inequalities | 2018-11-16 | Paper |
Accurate and nearly optimal sublinear approximations to Ulam distance
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
Composition limits and separating examples for some Boolean function complexity measures
Combinatorica | 2018-02-22 | Paper |
A communication game related to the sensitivity conjecture
Theory of Computing | 2017-10-11 | Paper |
A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity
Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms | 2017-10-05 | Paper |
Estimating the longest increasing sequence in polylogarithmic time
SIAM Journal on Computing | 2017-05-30 | Paper |
A New Approach to the Sensitivity Conjecture
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | 2017-05-19 | Paper |
| The power of super-logarithmic number of players | 2017-03-22 | Paper |
On the practically interesting instances of MAXCUT
(available as arXiv preprint) | 2017-01-30 | Paper |
| Towards an algebraic natural proofs barrier via polynomial identity testing | 2017-01-06 | Paper |
Lower bounds for leader election and collective coin-flipping in the perfect information model
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
Efficient indexing of necklaces and irreducible polynomials over finite fields
Theory of Computing | 2016-08-22 | Paper |
Low discrepancy sets yield approximate min-wise independent permutation families
Information Processing Letters | 2016-06-16 | Paper |
Hellinger volume and number-on-the-forehead communication complexity
Journal of Computer and System Sciences | 2016-06-13 | Paper |
Tight lower bounds for the online labeling problem
SIAM Journal on Computing | 2015-12-11 | Paper |
Time-space trade-off lower bounds for randomized computation of decision problems
Journal of the ACM | 2015-12-07 | Paper |
A tail bound for read-\(k\) families of functions
Random Structures & Algorithms | 2015-10-12 | Paper |
Optimal space distributed move-to-front lists
Proceedings of the tenth annual ACM symposium on Principles of distributed computing - PODC '91 | 2015-06-19 | Paper |
Efficient construction of a small hitting set for combinatorial rectangles in high dimension
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
Wait-free k-set agreement is impossible
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
Size-depth trade-offs for threshold circuits
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
| Rounds vs queries trade-off in noisy computation | 2014-10-13 | Paper |
Efficient indexing of necklaces and irreducible polynomials over finite fields
Automata, Languages, and Programming | 2014-07-01 | Paper |
Tight lower bounds for the online labeling problem
Proceedings of the forty-fourth annual ACM symposium on Theory of computing | 2014-05-13 | Paper |
On randomized online labeling with polynomially many labels
Automata, Languages, and Programming | 2013-08-06 | Paper |
On Online Labeling with Polynomially Many Labels
Algorithms – ESA 2012 | 2012-09-25 | Paper |
scientific article; zbMATH DE number 5899292 (Why is no real title available?)
Theory of Computing | 2011-05-24 | Paper |
An online algorithm for a problem in scheduling with set-ups and release times
Algorithmica | 2011-05-10 | Paper |
Local monotonicity reconstruction
SIAM Journal on Computing | 2011-04-04 | Paper |
The dual BKR inequality and Rudich's conjecture
Combinatorics, Probability and Computing | 2011-03-07 | Paper |
Lower bounds on the randomized communication complexity of read-once functions
Computational Complexity | 2011-02-18 | Paper |
Local property reconstruction and monotonicity
Property Testing | 2010-10-12 | Paper |
| scientific article; zbMATH DE number 5764799 (Why is no real title available?) | 2010-08-06 | Paper |
Space lower bounds for distance approximation in the data stream model
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
SIAM Journal on Computing | 2009-03-16 | Paper |
The unlabelled speed of a hereditary graph property
Journal of Combinatorial Theory. Series B | 2009-01-21 | Paper |
Lower Bounds for the Noisy Broadcast Problem
SIAM Journal on Computing | 2008-12-22 | Paper |
An improved exponential-time algorithm for k -SAT
Journal of the ACM | 2008-12-21 | Paper |
Approximation algorithms for problems in scheduling with set-ups
Discrete Applied Mathematics | 2008-03-18 | Paper |
STACS 2004
Lecture Notes in Computer Science | 2007-10-01 | Paper |
Probabilistic strategies for the partition and plurality problems
Random Structures & Algorithms | 2007-02-07 | Paper |
A localization inequality for set functions.
Journal of Combinatorial Theory. Series A | 2006-05-18 | Paper |
The non-crossing graph
The Electronic Journal of Combinatorics | 2006-01-31 | Paper |
The non-crossing graph
The Electronic Journal of Combinatorics | 2006-01-31 | Paper |
STACS 2005
Lecture Notes in Computer Science | 2005-12-02 | Paper |
A parallel search game
Random Structures & Algorithms | 2005-09-22 | Paper |
A lower bound on the integrality gap for minimum multicut in directed networks
Combinatorica | 2005-02-14 | Paper |
Complexity of some arithmetic problems for binary polynomials
Computational Complexity | 2004-12-13 | Paper |
Multicolour Turán problems
Advances in Applied Mathematics | 2004-10-12 | Paper |
A lower bound on the quantum query complexity of read-once functions
Journal of Computer and System Sciences | 2004-10-01 | Paper |
A limit theorem for sets of stochastic matrices.
Linear Algebra and its Applications | 2004-05-27 | Paper |
| scientific article; zbMATH DE number 1775401 (Why is no real title available?) | 2004-02-08 | Paper |
A lower bound for primality
Journal of Computer and System Sciences | 2003-05-19 | Paper |
The Euclidean distortion of complete binary trees
Discrete & Computational Geometry | 2003-03-17 | Paper |
On list update and work function algorithms.
Theoretical Computer Science | 2003-01-21 | Paper |
Kleitman and combinatorics
Discrete Mathematics | 2002-12-02 | Paper |
Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model
SIAM Journal on Computing | 2002-09-29 | Paper |
| scientific article; zbMATH DE number 1775444 (Why is no real title available?) | 2002-08-01 | Paper |
Time-space tradeoffs for branching programs
Journal of Computer and System Sciences | 2002-07-04 | Paper |
The efficiency of resolution and Davis-Putnam procedures
SIAM Journal on Computing | 2002-04-23 | Paper |
Sample spaces with small bias on neighborhoods and error-correcting communication protocols
Algorithmica | 2002-04-21 | Paper |
| scientific article; zbMATH DE number 1263224 (Why is no real title available?) | 2002-01-29 | Paper |
| scientific article; zbMATH DE number 1256655 (Why is no real title available?) | 2002-01-17 | Paper |
A decomposition theorem for task systems and bounds for randomized server problems
SIAM Journal on Computing | 2001-03-19 | Paper |
| scientific article; zbMATH DE number 1559525 (Why is no real title available?) | 2001-02-28 | Paper |
Exponential lower bounds for depth three Boolean circuits
Computational Complexity | 2000-12-19 | Paper |
| scientific article; zbMATH DE number 1418263 (Why is no real title available?) | 2000-12-03 | Paper |
A correction: Orthogonal representations and connectivity of graphs
Linear Algebra and its Applications | 2000-09-14 | Paper |
Low distortion Euclidean embeddings of trees
Israel Journal of Mathematics | 2000-06-05 | Paper |
Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge
SIAM Journal on Computing | 2000-03-19 | Paper |
| scientific article; zbMATH DE number 1306867 (Why is no real title available?) | 1999-08-31 | Paper |
Optimal Space Distributed Order-Preserving Lists
Journal of Algorithms | 1999-05-11 | Paper |
\(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\)
Journal of Computer and System Sciences | 1999-05-11 | Paper |
Products and Help Bits in Decision Trees
SIAM Journal on Computing | 1999-02-22 | Paper |
Explicit OR-dispersers with polylogarithmic degree
Journal of the ACM | 1998-12-10 | Paper |
Efficient construction of a small hitting set for combinatorial rectangles in high dimension
Combinatorica | 1998-03-26 | Paper |
Local management of a global resource in a communication network
Journal of the ACM | 1998-01-19 | Paper |
Size--Depth Tradeoffs for Threshold Circuits
SIAM Journal on Computing | 1997-05-26 | Paper |
| scientific article; zbMATH DE number 871902 (Why is no real title available?) | 1996-10-21 | Paper |
Witness sets for families of binary vectors
Journal of Combinatorial Theory. Series A | 1996-02-26 | Paper |
On the bandwidth of triangulated triangles
Discrete Mathematics | 1995-10-23 | Paper |
Approximating threshold circuits by rational functions
Information and Computation | 1995-08-27 | Paper |
Non-deterministic communication complexity with few witnesses
Journal of Computer and System Sciences | 1994-11-06 | Paper |
An optimal on-line algorithm for metrical task system
Journal of the ACM | 1994-08-21 | Paper |
A Complexity Index for Satisfiability Problems
SIAM Journal on Computing | 1994-08-16 | Paper |
| scientific article; zbMATH DE number 446494 (Why is no real title available?) | 1994-06-22 | Paper |
Low diameter graph decompositions
Combinatorica | 1994-06-22 | Paper |
Correlation inequalities and a conjecture for permanents
Combinatorica | 1994-03-03 | Paper |
Communication complexity and combinatorial lattice theory
Journal of Computer and System Sciences | 1993-12-20 | Paper |
The number of distinct subset sums of a finite set of vectors
Journal of Combinatorial Theory. Series A | 1993-11-17 | Paper |
Combinatorial characterization of read-once formulae
Discrete Mathematics | 1993-10-24 | Paper |
| scientific article; zbMATH DE number 432838 (Why is no real title available?) | 1993-10-20 | Paper |
| scientific article; zbMATH DE number 432834 (Why is no real title available?) | 1993-10-20 | Paper |
Sharpening the LYM inequality
Combinatorica | 1993-01-17 | Paper |
On computing majority by comparisons
Combinatorica | 1992-06-27 | Paper |
A dynamic location problem for graphs
Combinatorica | 1989-01-01 | Paper |
A Robust Noncryptographic Protocol for Collective Coin Flipping
SIAM Journal on Discrete Mathematics | 1989-01-01 | Paper |
An on-line graph coloring algorithm with sublinear performance ratio
Discrete Mathematics | 1989-01-01 | Paper |
Orthogonal representations and connectivity of graphs
Linear Algebra and its Applications | 1989-01-01 | Paper |
On the cover time of random walks on graphs
Journal of Theoretical Probability | 1989-01-01 | Paper |
The periodic balanced sorting network
Journal of the ACM | 1989-01-01 | Paper |
Some extremal problems arising from discrete control processes
Combinatorica | 1989-01-01 | Paper |
Combinatorial representation and convex dimension of convex geometries
Order | 1988-01-01 | Paper |
| scientific article; zbMATH DE number 4106654 (Why is no real title available?) | 1988-01-01 | Paper |
A Limit Theorem for (min, +) Matrix Multiplication
Mathematics of Operations Research | 1988-01-01 | Paper |
An intersection problem for finite automata
Discrete Applied Mathematics | 1988-01-01 | Paper |
On the widths of finite distributive lattices
Discrete Mathematics | 1987-01-01 | Paper |
Subgraphs of large connectivity and chromatic number in graphs of large chromatic number
Journal of Graph Theory | 1987-01-01 | Paper |
| scientific article; zbMATH DE number 4049076 (Why is no real title available?) | 1987-01-01 | Paper |
Every finite distributive lattice is a set of stable matchings for a small stable marriage instance
Journal of Combinatorial Theory. Series A | 1987-01-01 | Paper |
The smallest n-uniform hypergraph with positive discrepancy
Combinatorica | 1987-01-01 | Paper |
Maximum induced trees in graphs
Journal of Combinatorial Theory. Series B | 1986-01-01 | Paper |
Some sequences associated with combinatorial structures
Discrete Mathematics | 1986-01-01 | Paper |
Searching ordered structures
Journal of Algorithms | 1985-01-01 | Paper |
Every poset has a central element
Journal of Combinatorial Theory. Series A | 1985-01-01 | Paper |
| scientific article; zbMATH DE number 3909739 (Why is no real title available?) | 1985-01-01 | Paper |
Largest induced suborders satisfying the chain condition
Order | 1985-01-01 | Paper |
A topological approach to evasiveness
Combinatorica | 1984-01-01 | Paper |
| scientific article; zbMATH DE number 3902685 (Why is no real title available?) | 1984-01-01 | Paper |
A polyomino with no stochastic function
Combinatorica | 1984-01-01 | Paper |
Balancing poset extensions
Order | 1984-01-01 | Paper |
A Statistical Procedure for Cluster Recognition with Application to Atlanta Leukemia-Lymphoma Data
Studies in Applied Mathematics | 1983-01-01 | Paper |
Largest digraphs contained in all n-tournaments
Combinatorica | 1983-01-01 | Paper |
A Class of Perfect Graphs Associated with Planar Rectilinear Regions
SIAM Journal on Algebraic Discrete Methods | 1982-01-01 | Paper |
Covering Regions by Rectangles
SIAM Journal on Algebraic Discrete Methods | 1981-01-01 | Paper |
Set Orderings Requiring Costliest Alphabetic Binary Trees
SIAM Journal on Algebraic Discrete Methods | 1981-01-01 | Paper |
Product partial orders with the Sperner property
Discrete Mathematics | 1980-01-01 | Paper |
Dilworth Numbers, Incidence Maps and Product Partial Orders
SIAM Journal on Algebraic Discrete Methods | 1980-01-01 | Paper |
On chains and Sperner k-families in ranked posets. II
Journal of Combinatorial Theory. Series A | 1980-01-01 | Paper |
Group labelings of graphs
Journal of Graph Theory | 1979-01-01 | Paper |
A short proof of the existence of k-saturated partitions of partially ordered sets
Advances in Mathematics | 1979-01-01 | Paper |
