| Publication | Date of Publication | Type |
|---|
| Approximating Edit Distance Within Constant Factor in Truly Sub-quadratic Time | 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 | 2021-03-03 | Paper |
| Constant factor approximations to edit distance on far input pairs in nearly linear time | 2021-01-19 | Paper |
| An asymptotically tight bound on the number of relevant variables in a bounded degree Boolean function | 2020-10-02 | Paper |
| On the discrepancy of random matrices with many columns | 2020-09-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3304119 | 2020-08-05 | Paper |
| On Online Labeling with Large Label Set | 2019-08-29 | Paper |
| Space efficient streaming algorithms for the distance to monotonicity and asymmetric edit distance | 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 | 2018-07-16 | Paper |
| Composition limits and separating examples for some Boolean function complexity measures | 2018-02-22 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5368900 | 2017-10-11 | Paper |
| A polylogarithmic space deterministic streaming algorithm for approximating distance to monotonicity | 2017-10-05 | Paper |
| Estimating the Longest Increasing Sequence in Polylogarithmic Time | 2017-05-30 | Paper |
| A New Approach to the Sensitivity Conjecture | 2017-05-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2969648 | 2017-03-22 | Paper |
| On the practically interesting instances of MAXCUT | 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 | 2016-09-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2816411 | 2016-08-22 | Paper |
| Low discrepancy sets yield approximate min-wise independent permutation families | 2016-06-16 | Paper |
| Hellinger volume and number-on-the-forehead communication complexity | 2016-06-13 | Paper |
| Tight Lower Bounds for the Online Labeling Problem | 2015-12-11 | Paper |
| Time-space trade-off lower bounds for randomized computation of decision problems | 2015-12-07 | Paper |
| A tail bound for read-kfamilies of functions | 2015-10-12 | Paper |
| Optimal space distributed move-to-front lists | 2015-06-19 | Paper |
| Wait-free k-set agreement is impossible | 2015-05-07 | Paper |
| Efficient construction of a small hitting set for combinatorial rectangles in high dimension | 2015-05-07 | Paper |
| Size-depth trade-offs for threshold circuits | 2015-05-07 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2921722 | 2014-10-13 | Paper |
| Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields | 2014-07-01 | Paper |
| Tight lower bounds for the online labeling problem | 2014-05-13 | Paper |
| On Randomized Online Labeling with Polynomially Many Labels | 2013-08-06 | Paper |
| On Online Labeling with Polynomially Many Labels | 2012-09-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3002819 | 2011-05-24 | Paper |
| An online algorithm for a problem in scheduling with set-ups and release times | 2011-05-10 | Paper |
| Local Monotonicity Reconstruction | 2011-04-04 | Paper |
| The Dual BKR Inequality and Rudich's Conjecture | 2011-03-07 | Paper |
| Lower bounds on the randomized communication complexity of read-once functions | 2011-02-18 | Paper |
| Local Property Reconstruction and Monotonicity | 2010-10-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3579388 | 2010-08-06 | Paper |
| Space lower bounds for distance approximation in the data stream model | 2010-08-05 | Paper |
| Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table | 2009-03-16 | Paper |
| The unlabelled speed of a hereditary graph property | 2009-01-21 | Paper |
| Lower Bounds for the Noisy Broadcast Problem | 2008-12-22 | Paper |
| An improved exponential-time algorithm for k -SAT | 2008-12-21 | Paper |
| Approximation algorithms for problems in scheduling with set-ups | 2008-03-18 | Paper |
| STACS 2004 | 2007-10-01 | Paper |
| Probabilistic strategies for the partition and plurality problems | 2007-02-07 | Paper |
| A localization inequality for set functions. | 2006-05-18 | Paper |
| The non-crossing graph | 2006-01-31 | Paper |
| STACS 2005 | 2005-12-02 | Paper |
| A parallel search game | 2005-09-22 | Paper |
| A lower bound on the integrality gap for minimum multicut in directed networks | 2005-02-14 | Paper |
| Complexity of some arithmetic problems for binary polynomials | 2004-12-13 | Paper |
| Multicolour Turán problems | 2004-10-12 | Paper |
| A lower bound on the quantum query complexity of read-once functions | 2004-10-01 | Paper |
| A limit theorem for sets of stochastic matrices. | 2004-05-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4542534 | 2004-02-08 | Paper |
| A lower bound for primality | 2003-05-19 | Paper |
| The Euclidean distortion of complete binary trees | 2003-03-17 | Paper |
| On list update and work function algorithms. | 2003-01-21 | Paper |
| Kleitman and combinatorics | 2002-12-02 | Paper |
| Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model | 2002-09-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4542576 | 2002-08-01 | Paper |
| Time-space tradeoffs for branching programs | 2002-07-04 | Paper |
| The Efficiency of Resolution and Davis--Putnam Procedures | 2002-04-23 | Paper |
| Sample spaces with small bias on neighborhoods and error-correcting communication protocols | 2002-04-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4234096 | 2002-01-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4230341 | 2002-01-17 | Paper |
| A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems | 2001-03-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4526973 | 2001-02-28 | Paper |
| Exponential lower bounds for depth three Boolean circuits | 2000-12-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4941822 | 2000-12-03 | Paper |
| A correction: Orthogonal representations and connectivity of graphs | 2000-09-14 | Paper |
| Low distortion Euclidean embeddings of trees | 2000-06-05 | Paper |
| Wait-Free k-Set Agreement is Impossible: The Topology of Public Knowledge | 2000-03-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4252719 | 1999-08-31 | Paper |
| Optimal Space Distributed Order-Preserving Lists | 1999-05-11 | Paper |
| \(\text{BP}_{\text{H}}\text{SPACE}(S) \subseteq \text{DSPACE}(S^{3/2})\) | 1999-05-11 | Paper |
| Products and Help Bits in Decision Trees | 1999-02-22 | Paper |
| Explicit OR-dispersers with polylogarithmic degree | 1998-12-10 | Paper |
| Efficient construction of a small hitting set for combinatorial rectangles in high dimension | 1998-03-26 | Paper |
| Local management of a global resource in a communication network | 1998-01-19 | Paper |
| Size--Depth Tradeoffs for Threshold Circuits | 1997-05-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4875171 | 1996-10-21 | Paper |
| Witness sets for families of binary vectors | 1996-02-26 | Paper |
| On the bandwidth of triangulated triangles | 1995-10-23 | Paper |
| Approximating threshold circuits by rational functions | 1995-08-27 | Paper |
| Non-deterministic communication complexity with few witnesses | 1994-11-06 | Paper |
| An optimal on-line algorithm for metrical task system | 1994-08-21 | Paper |
| A Complexity Index for Satisfiability Problems | 1994-08-16 | Paper |
| Low diameter graph decompositions | 1994-06-22 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3142416 | 1994-06-22 | Paper |
| Correlation inequalities and a conjecture for permanents | 1994-03-03 | Paper |
| Communication complexity and combinatorial lattice theory | 1993-12-20 | Paper |
| The number of distinct subset sums of a finite set of vectors | 1993-11-17 | Paper |
| Combinatorial characterization of read-once formulae | 1993-10-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3138968 | 1993-10-20 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3138972 | 1993-10-20 | Paper |
| Sharpening the LYM inequality | 1993-01-17 | Paper |
| On computing majority by comparisons | 1992-06-27 | Paper |
| A dynamic location problem for graphs | 1989-01-01 | Paper |
| Some extremal problems arising from discrete control processes | 1989-01-01 | Paper |
| An on-line graph coloring algorithm with sublinear performance ratio | 1989-01-01 | Paper |
| Orthogonal representations and connectivity of graphs | 1989-01-01 | Paper |
| On the cover time of random walks on graphs | 1989-01-01 | Paper |
| The periodic balanced sorting network | 1989-01-01 | Paper |
| A Robust Noncryptographic Protocol for Collective Coin Flipping | 1989-01-01 | Paper |
| Combinatorial representation and convex dimension of convex geometries | 1988-01-01 | Paper |
| An intersection problem for finite automata | 1988-01-01 | Paper |
| A Limit Theorem for (min, +) Matrix Multiplication | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3830840 | 1988-01-01 | Paper |
| The smallest n-uniform hypergraph with positive discrepancy | 1987-01-01 | Paper |
| Every finite distributive lattice is a set of stable matchings for a small stable marriage instance | 1987-01-01 | Paper |
| On the widths of finite distributive lattices | 1987-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3785965 | 1987-01-01 | Paper |
| Subgraphs of large connectivity and chromatic number in graphs of large chromatic number | 1987-01-01 | Paper |
| Some sequences associated with combinatorial structures | 1986-01-01 | Paper |
| Maximum induced trees in graphs | 1986-01-01 | Paper |
| Every poset has a central element | 1985-01-01 | Paper |
| Largest induced suborders satisfying the chain condition | 1985-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3686039 | 1985-01-01 | Paper |
| Searching ordered structures | 1985-01-01 | Paper |
| A polyomino with no stochastic function | 1984-01-01 | Paper |
| A topological approach to evasiveness | 1984-01-01 | Paper |
| Balancing poset extensions | 1984-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3680857 | 1984-01-01 | Paper |
| Largest digraphs contained in all n-tournaments | 1983-01-01 | Paper |
| A Statistical Procedure for Cluster Recognition with Application to Atlanta Leukemia-Lymphoma Data | 1983-01-01 | Paper |
| A Class of Perfect Graphs Associated with Planar Rectilinear Regions | 1982-01-01 | Paper |
| Covering Regions by Rectangles | 1981-01-01 | Paper |
| Set Orderings Requiring Costliest Alphabetic Binary Trees | 1981-01-01 | Paper |
| Product partial orders with the Sperner property | 1980-01-01 | Paper |
| On chains and Sperner k-families in ranked posets. II | 1980-01-01 | Paper |
| Dilworth Numbers, Incidence Maps and Product Partial Orders | 1980-01-01 | Paper |
| A short proof of the existence of k-saturated partitions of partially ordered sets | 1979-01-01 | Paper |
| Group labelings of graphs | 1979-01-01 | Paper |
