| Publication | Date of Publication | Type |
|---|
| Efficient algorithms for Lempel-Ziv encoding | 2022-12-09 | Paper |
| On-line load balancing for related machines | 2022-08-19 | Paper |
| On a sublinear time parallel construction of optimal binary search trees | 2022-08-18 | Paper |
| Noisy polynomial interpolation modulo prime powers | 2021-06-22 | Paper |
| Approximate Counting of Matchings in Sparse Uniform Hypergraphs | 2019-09-17 | Paper |
| Lower space bounds for randomized computation | 2019-04-29 | Paper |
| On randomized versus deterministic computation | 2019-03-29 | Paper |
| Lower time bounds for randomized computation | 2019-01-10 | Paper |
| Identity testing and interpolation from high powers of polynomials of large degree over finite fields | 2018-10-11 | Paper |
| Tropical dominating sets in vertex-coloured graphs | 2018-05-09 | Paper |
| Polynomial interpolation and identity testing from high powers over finite fields | 2018-04-06 | Paper |
| Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications | 2018-04-06 | Paper |
| A QPTAS for the base of the number of crossing-free structures on a planar point set | 2018-02-16 | Paper |
| 1.0957-Approximation Algorithm for Random MAX-3SAT | 2018-01-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5365051 | 2017-09-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2965501 | 2017-03-03 | Paper |
| Lower bounds on testing membership to a polyhedron by algebraic decision trees | 2016-09-01 | Paper |
| Tropical dominating sets in vertex-coloured graphs | 2016-05-03 | Paper |
| A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set | 2015-10-27 | Paper |
| Approximation hardness of graphic TSP on cubic graphs | 2015-10-20 | Paper |
| Towards Better Inapproximability Bounds for TSP: A Challenge of Global Dependencies | 2015-09-29 | Paper |
| Explicit Bounds for Nondeterministically Testable Hypergraph Parameters | 2015-09-10 | Paper |
| New inapproximability bounds for TSP | 2015-08-31 | Paper |
| Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs | 2015-08-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5501299 | 2015-08-03 | Paper |
| Generalized Wong sequences and their applications to Edmonds' problems | 2015-07-13 | Paper |
| Simulating threshold circuits by majority circuits | 2015-05-07 | Paper |
| Counting curves and their projections | 2015-05-07 | Paper |
| Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems | 2015-02-04 | Paper |
| On the computational complexity of measuring global stability of banking networks | 2015-01-19 | Paper |
| Inapproximability of dominating set on power law graphs | 2014-12-02 | Paper |
| Approximate Counting of Matchings in (3,3)-Hypergraphs | 2014-09-02 | Paper |
| Complexity of Nondeterministic Graph Parameter Testing | 2014-08-15 | Paper |
| Optimal cuts and partitions in tree metrics in polynomial time | 2014-08-13 | Paper |
| Deterministic polynomial factoring and association schemes | 2014-07-23 | Paper |
| Limits of CSP Problems and Efficient Parameter Testing | 2014-06-13 | Paper |
| New Inapproximability Bounds for TSP | 2014-01-14 | Paper |
| Approximating Subdense Instances of Covering Problems | 2013-07-23 | Paper |
| Exact and approximation algorithms for geometric and capacitated set cover problems | 2012-11-21 | Paper |
| Approximating vertex cover in dense hypergraphs | 2012-09-13 | Paper |
| Schemes for deterministic polynomial factoring | 2012-05-13 | Paper |
| Trading GRH for algebra: Algorithms for factoring polynomials and related structures | 2012-02-17 | Paper |
| Approximation Schemes for the Betweenness Problem in Tournaments and Related Ranking Problems | 2011-08-17 | Paper |
| Deterministic Polynomial Time Algorithms for Matrix Completion Problems | 2011-04-04 | Paper |
| COMPUTATIONAL COMPLEXITY OF THE PERFECT MATCHING PROBLEM IN HYPERGRAPHS WITH SUBCRITICAL DENSITY | 2011-01-19 | Paper |
| Faster Algorithms for Feedback Arc Set Tournament, Kemeny Rank Aggregation and Betweenness Tournament | 2010-12-09 | Paper |
| A 3/2-Approximation Algorithm for Generalized Steiner Trees in Complete Graphs with Edge Lengths 1 and 2 | 2010-12-09 | Paper |
| The mixing time of Glauber dynamics for coloring regular trees | 2010-11-24 | Paper |
| Approximation schemes for clustering problems | 2010-08-16 | Paper |
| Tensor decomposition and approximation schemes for constraint satisfaction problems | 2010-08-16 | Paper |
| 8/7-approximation algorithm for (1,2)-TSP | 2010-08-16 | Paper |
| Random sampling and approximation of MAX-CSP problems | 2010-08-05 | Paper |
| Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems | 2010-07-20 | Paper |
| Computational Complexity of the Hamiltonian Cycle Problem in Dense Hypergraphs | 2010-04-27 | Paper |
| Algorithms and Data Structures | 2010-04-20 | Paper |
| The Complexity of Perfect Matching Problems on Dense Hypergraphs | 2009-12-17 | Paper |
| Approximating Transitive Reductions for Directed Networks | 2009-10-20 | Paper |
| 1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2 | 2009-10-20 | Paper |
| A fast algorithm for adaptive prefix coding | 2009-07-24 | Paper |
| Space Efficient Multi-dimensional Range Reporting | 2009-07-23 | Paper |
| Stopping Times, Metrics and Approximate Counting | 2009-03-12 | Paper |
| Path coupling using stopping times and counting independent sets and colorings in hypergraphs | 2008-06-05 | Paper |
| Approximating Huffman codes in parallel | 2008-01-11 | Paper |
| EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION | 2007-07-13 | Paper |
| Computational complexity of some restricted instances of 3-SAT | 2007-04-13 | Paper |
| Optimal trade-off for Merkle tree traversal | 2007-03-15 | Paper |
| Algorithms and Computation | 2006-11-14 | Paper |
| Algorithms and Computation | 2006-11-14 | Paper |
| Fundamentals of Computation Theory | 2006-10-20 | Paper |
| TSP with bounded metrics | 2006-06-30 | Paper |
| Algorithms – ESA 2005 | 2006-06-27 | Paper |
| On the computational power of probabilistic and quantum branching program | 2006-01-10 | Paper |
| Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs | 2005-10-28 | Paper |
| Improved approximation algorithms for the quality of service multicast tree problem | 2005-08-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4654270 | 2005-03-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4828917 | 2004-11-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4828976 | 2004-11-29 | Paper |
| Random sampling and approximation of MAX-CSPs | 2004-11-18 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4818848 | 2004-09-24 | Paper |
| Approximability of Dense Instances of Nearest Codeword Problem | 2004-08-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4737194 | 2004-08-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4737213 | 2004-08-11 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4470539 | 2004-07-01 | Paper |
| A lower bound for integer multiplication on randomized ordered read-once branching programs. | 2004-03-14 | Paper |
| Polynomial time approximation schemes for dense instances of minimum constraint satisfaction | 2003-08-06 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4411359 | 2003-07-08 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4708558 | 2003-06-18 | Paper |
| On the complexity of pattern matching for highly compressed two-dimensional texts. | 2003-05-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2758399 | 2003-01-22 | Paper |
| Learning by the process of elimination | 2003-01-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4782694 | 2002-12-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4782697 | 2002-12-02 | Paper |
| Improved approximation of Max-Cut on graphs of bounded degree | 2002-09-30 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4542578 | 2002-08-01 | Paper |
| On the approximation hardness of dense TSP and other path problems | 2002-07-25 | Paper |
| A note on approximating Max-Bisection on regular graphs | 2002-07-14 | Paper |
| Randomized splay trees: Theoretical and experimental results. | 2002-07-14 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4535019 | 2002-06-12 | Paper |
| Polynomial time approximation schemes for some dense instances of NP-hard optimization problems | 2002-02-19 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4234066 | 2002-01-30 | Paper |
| https://portal.mardi4nfdi.de/entity/Q2762518 | 2002-01-09 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4234075 | 2001-08-27 | Paper |
| On BPP versus \(NP\cup coNP\) for ordered read-once branching programs | 2001-08-20 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4234231 | 2001-06-21 | Paper |
| Compact cellular algebras and permutation groups | 2001-03-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4526972 | 2001-02-28 | Paper |
| On-Line Load Balancing for Related Machines | 2000-10-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4502656 | 2000-09-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4500688 | 2000-08-27 | Paper |
| Zero testing of \(p\)-adic and modular polynomials | 2000-08-23 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4496246 | 2000-08-13 | Paper |
| An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph | 2000-06-15 | Paper |
| On a new high dimensional Weisfeiler-Lehman algorithm | 2000-05-25 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4252710 | 2000-04-26 | Paper |
| A generalization of Wilkie's theorem of the complement, and an application to Pfaffian closure | 2000-03-23 | Paper |
| Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems | 2000-02-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4934316 | 2000-01-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4228517 | 1999-10-04 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4237365 | 1999-09-09 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4234080 | 1999-06-29 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4226940 | 1999-05-30 | Paper |
| Counting curves and their projections | 1999-05-05 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4240332 | 1999-05-03 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4240341 | 1999-05-03 | Paper |
| An exponential lower bound on the size of algebraic decision trees for MAX | 1999-02-02 | Paper |
| Alphabet-independent optimal parallel search for three-dimensional patterns | 1999-01-12 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4395327 | 1998-10-01 | Paper |
| Matching and multidimensional matching in chordal and strongly chordal graphs | 1998-07-28 | Paper |
| Correctness of constructing optimal alphabetic trees revisited | 1998-07-22 | Paper |
| A lower bound for randomized algebraic decision trees | 1998-05-13 | Paper |
| Randomization and the computational power of analytic and algebraic decision trees | 1998-05-13 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4389326 | 1998-05-13 | Paper |
| Simulating Threshold Circuits by Majority Circuits | 1998-05-10 | Paper |
| Computing the Additive Complexity of Algebraic Circuits with Root Extracting | 1998-05-10 | Paper |
| New approximation algorithms for the Steiner tree problems | 1998-04-13 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4370228 | 1998-02-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4362732 | 1997-11-13 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4347161 | 1997-09-18 | Paper |
| On randomized versus deterministic computation | 1997-09-09 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3126174 | 1997-07-06 | Paper |
| Lower bound on testing membership to a polyhedron by algebraic decision and computation trees | 1997-03-23 | Paper |
| Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks | 1997-03-18 | Paper |
| On some approximation problems concerning sparse polynomials over finite fields | 1997-02-27 | Paper |
| Computability of the additive complexity of algebraic circuits with root extracting | 1997-02-27 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4875166 | 1996-06-16 | Paper |
| Resolution for quantified Boolean formulas | 1995-05-28 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3135191 | 1994-11-29 | Paper |
| VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions | 1994-11-13 | Paper |
| An algorithm to learn read-once threshold formulas, and transformations between learning models | 1994-06-19 | Paper |
| Computational Complexity of Sparse Rational Interpolation | 1994-04-27 | Paper |
| On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs | 1994-03-13 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4279514 | 1994-02-17 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3138901 | 1994-01-02 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3138965 | 1993-10-20 | Paper |
| Some computational problems in linear algebra as hard as matrix multiplication | 1993-10-10 | Paper |
| On randomized semi-algebraic test complexity | 1993-08-24 | Paper |
| Approximating the Number of Zeroes of a GF[2 Polynomial] | 1993-05-16 | Paper |
| Learning read-once formulas with queries | 1993-05-16 | Paper |
| An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3 | 1993-01-16 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4013534 | 1992-09-27 | Paper |
| Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem | 1992-06-28 | Paper |
| On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields | 1992-06-26 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3976040 | 1992-06-26 | Paper |
| The interpolation problem for \(k\)-sparse sums of eigenfunctions of operators | 1992-06-25 | Paper |
| Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields | 1990-01-01 | Paper |
| Subtree isomorphism is NC reducible to bipartite perfect matching | 1989-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q5748889 | 1989-01-01 | Paper |
| Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs | 1988-01-01 | Paper |
| The computational complexity of graph problems with succinct multigraph representation | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3804207 | 1988-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3815282 | 1988-01-01 | Paper |
| On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes | 1987-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3819053 | 1987-01-01 | Paper |
| On the power of two-way random generators and the impossibility of deterministic poly-space simulation | 1986-01-01 | Paper |
| There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator | 1985-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3038625 | 1983-01-01 | Paper |
| Decidability of Skolem matrix emptiness problem entails constructability of exact regular expression | 1982-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4745261 | 1981-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3862449 | 1980-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3951544 | 1980-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3959430 | 1980-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q3857705 | 1979-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4128033 | 1977-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4133166 | 1977-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4133167 | 1977-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4143208 | 1977-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4111542 | 1976-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4125797 | 1976-01-01 | Paper |
| Almost Deterministic ω-Automata with Existential Output Condition | 1975-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4101799 | 1975-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4103041 | 1975-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4062658 | 1974-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4766969 | 1974-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4766966 | 1973-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4766967 | 1973-01-01 | Paper |
| https://portal.mardi4nfdi.de/entity/Q4766968 | 1973-01-01 | Paper |
