| Publication | Date of Publication | Type |
|---|
| New partitioning techniques and faster algorithms for approximate interval scheduling | 2024-11-14 | Paper |
| New partitioning techniques and faster algorithms for approximate interval scheduling | 2024-10-07 | Paper |
| Massively parallel algorithms for small subgraph counting | 2024-08-22 | Paper |
| Testing distributional assumptions of learning algorithms | 2024-05-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q6126250 | 2024-04-09 | Paper |
| Sampling Multiple Edges Efficiently | 2023-11-20 | Paper |
| Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time | 2023-11-20 | Paper |
| Approximating the Noise Sensitivity of a Monotone Boolean Function | 2023-02-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5875721 | 2023-02-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5875722 | 2023-02-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5090437 | 2022-07-18 | Paper |
| Fractional Set Cover in the Streaming Model. | 2021-07-28 | Paper |
| Improved Local Computation Algorithm for Set Cover via Sparsification | 2021-02-02 | Paper |
| Local Computation Algorithms | 2021-01-20 | Paper |
| Local algorithms for sparse spanning graphs | 2020-02-28 | Paper |
| Improved Massively Parallel Computation Algorithms for MIS, Matching, and Vertex Cover | 2019-09-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5743463 | 2019-05-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5743464 | 2019-05-10 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4633833 | 2019-05-06 | Paper |
| Sampling Correctors | 2018-08-03 | Paper |
| A Local Algorithm for Constructing Spanners in Minor-Free Graphs | 2018-04-19 | Paper |
| Sublinear-time algorithms for counting star subgraphs via edge sampling | 2018-04-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4608053 | 2018-03-15 | Paper |
| Testing shape restrictions of discrete distributions | 2018-03-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4601877 | 2018-01-24 | Paper |
| Can we locally compute sparse connected subgraphs? | 2017-08-22 | Paper |
| Local computation algorithms for graphs of non-constant degrees | 2017-05-02 | Paper |
| Constructing near spanning trees with few local inspections | 2017-04-18 | Paper |
| Local Algorithms for Sparse Spanning Graphs | 2017-03-22 | Paper |
| Fast approximate PCPs | 2016-09-29 | Paper |
| A self-tester for linear functions over the integers with an elementary proof of correctness | 2016-09-21 | Paper |
| On the learnability of discrete distributions | 2016-09-01 | Paper |
| Sampling correctors | 2016-04-15 | Paper |
| Selective private function evaluation with applications to private statistics | 2016-03-04 | Paper |
| Approximating the Influence of Monotone Boolean Functions in O(√n) Query Complexity | 2015-09-24 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5501239 | 2015-08-03 | Paper |
| Efficient learning of typical finite automata from random walks | 2015-05-07 | Paper |
| Testing Similar Means | 2015-04-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3191576 | 2014-10-06 | Paper |
| Random walks with “back buttons” (extended abstract) | 2014-09-26 | Paper |
| Maintaining a large matching and a small vertex cover | 2014-08-13 | Paper |
| Testing Probability Distributions Underlying Aggregated Data | 2014-07-01 | Paper |
| Testing Closeness of Discrete Distributions | 2014-02-17 | Paper |
| Robust characterizations of \(k\)-wise independence over product spaces and related testing results | 2013-10-29 | Paper |
| Local Reconstructors and Tolerant Testers for Connectivity and Diameter | 2013-10-04 | Paper |
| Testing Similar Means | 2013-08-12 | Paper |
| A local decision test for sparse polynomials | 2012-03-27 | Paper |
| Sublinear Time Algorithms | 2012-03-15 | Paper |
| Approximating the Influence of Monotone Boolean Functions in $O(\sqrt{n})$ Query Complexity | 2011-08-17 | Paper |
| Testing Halfspaces | 2010-11-04 | Paper |
| Dynamic Approximate Vertex Cover and Maximum Matching | 2010-10-12 | Paper |
| Testing (Subclasses of) Halfspaces | 2010-10-12 | Paper |
| Sublinear Algorithms in the External Memory Model | 2010-10-12 | Paper |
| Testing Non-uniform k-Wise Independent Distributions over Product Spaces | 2010-09-07 | Paper |
| A sublinear algorithm for weakly approximating edit distance | 2010-08-16 | Paper |
| Testing monotone high-dimensional distributions | 2010-08-16 | Paper |
| Sublinear algorithms for testing monotone and unimodal distributions | 2010-08-15 | Paper |
| Monotonicity testing over general poset domains | 2010-08-05 | Paper |
| The complexity of approximating entropy | 2010-08-05 | Paper |
| Testing ±1-weight halfspace | 2009-10-28 | Paper |
| External Sampling | 2009-07-14 | Paper |
| Testing monotone high‐dimensional distributions | 2009-03-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3549649 | 2009-01-05 | Paper |
| Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions | 2008-01-18 | Paper |
| Tolerant property testing and distance approximation | 2006-10-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5491026 | 2006-09-26 | Paper |
| The Complexity of Approximating the Entropy | 2005-10-28 | Paper |
| Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time | 2005-10-28 | Paper |
| Approximating the Minimum Spanning Tree Weight in Sublinear Time | 2005-09-16 | Paper |
| Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2005-08-25 | Paper |
| Fast approximate PCPs for multidimensional bin-packing problems | 2005-03-08 | Paper |
| Fast approximate probabilistically checkable proofs | 2004-10-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4471376 | 2004-07-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4542544 | 2004-01-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4440424 | 2003-12-17 | Paper |
| On Testing Convexity and Submodularity | 2003-09-28 | Paper |
| Random walks with ``back buttons | 2003-05-06 | Paper |
| Testing membership in parenthesis languages | 2003-03-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4780800 | 2002-11-21 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4535797 | 2002-06-25 | Paper |
| Checking approximate computations of polynomials and functional equations | 2002-04-23 | Paper |
| Spot-checkers | 2001-05-28 | Paper |
| Learning polynomials with queries: The highly noisy case | 2001-03-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4230375 | 1999-11-08 | Paper |
| On the Robustness of Functional Equations | 1999-10-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4252714 | 1999-08-31 | Paper |
| Reconstructing Algebraic Functions from Mixed Data | 1998-09-21 | Paper |
| Efficient learning of typical finite automata from random walks | 1998-06-02 | Paper |
| Robust Characterizations of Polynomials with Applications to Program Testing | 1996-08-18 | Paper |
| Designing checkers for programs that run in parallel | 1996-08-13 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4847919 | 1996-08-07 | Paper |
| Learning fallible deterministic finite automata | 1995-10-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4763385 | 1995-04-11 | Paper |
| Self-testing/correcting with applications to numerical problems | 1994-09-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4035721 | 1993-05-18 | Paper |
| Batch checking with applications to linear functions | 1993-01-16 | Paper |
| On the time and space complexity of computation using write-once memory or is pen really much worse than pencil? | 1992-09-26 | Paper |
| A competitive 2-server algorithm | 1992-06-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3212297 | 1991-01-01 | Paper |
| The cover time of a regular expander is O(n log n) | 1990-01-01 | Paper |
| Reversing trains: A turn of the century sorting problem | 1989-01-01 | Paper |
