| Publication | Date of Publication | Type |
|---|
Symmetric encryption algorithms in a polynomial residue number system
Journal of Applied Mathematics | 2024-07-24 | Paper |
Efficient algorithms for Lempel-Ziv encoding
Algorithm Theory — SWAT'96 | 2022-12-09 | Paper |
On-line load balancing for related machines
Lecture Notes in Computer Science | 2022-08-19 | Paper |
On a sublinear time parallel construction of optimal binary search trees
Mathematical Foundations of Computer Science 1994 | 2022-08-18 | Paper |
Noisy polynomial interpolation modulo prime powers
Journal of Complexity | 2021-06-22 | Paper |
Approximate counting of matchings in sparse uniform hypergraphs
2013 Proceedings of the Tenth Workshop on Analytic Algorithmics and Combinatorics (ANALCO) | 2019-09-17 | Paper |
Lower space bounds for randomized computation
Automata, Languages and Programming | 2019-04-29 | Paper |
On randomized versus deterministic computation
Automata, Languages and Programming | 2019-03-29 | Paper |
Lower time bounds for randomized computation
Automata, Languages and Programming | 2019-01-10 | Paper |
Identity testing and interpolation from high powers of polynomials of large degree over finite fields
Journal of Complexity | 2018-10-11 | Paper |
Tropical dominating sets in vertex-coloured graphs
Journal of Discrete Algorithms | 2018-05-09 | Paper |
Polynomial interpolation and identity testing from high powers over finite fields
Algorithmica | 2018-04-06 | Paper |
Effect of Gromov-hyperbolicity parameter on cuts and expansions in graphs and some algorithmic implications
Algorithmica | 2018-04-06 | Paper |
A QPTAS for the base of the number of crossing-free structures on a planar point set
Theoretical Computer Science | 2018-02-16 | Paper |
1.0957-Approximation Algorithm for Random MAX-3SAT
RAIRO - Operations Research | 2018-01-12 | Paper |
Top-\(K\) color queries for document retrieval
| 2017-09-29 | Paper |
Generalized Wong sequences and their applications to Edmonds' problems
| 2017-03-03 | Paper |
Lower bounds on testing membership to a polyhedron by algebraic decision trees
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
Tropical dominating sets in vertex-coloured graphs
Lecture Notes in Computer Science | 2016-05-03 | Paper |
A QPTAS for the Base of the Number of Crossing-Free Structures on a Planar Point Set
Automata, Languages, and Programming | 2015-10-27 | Paper |
Approximation hardness of graphic TSP on cubic graphs
RAIRO - Operations Research | 2015-10-20 | Paper |
Towards better inapproximability bounds for TSP: a challenge of global dependencies
Fundamentals of Computation Theory | 2015-09-29 | Paper |
Explicit Bounds for Nondeterministically Testable Hypergraph Parameters
| 2015-09-10 | Paper |
New inapproximability bounds for TSP
Journal of Computer and System Sciences | 2015-08-31 | Paper |
Nearly tight approximation bounds for vertex cover on dense \(k\)-uniform \( k\)-partite hypergraphs
Journal of Discrete Algorithms | 2015-08-18 | Paper |
Approximation schemes for metric bisection and partitioning
| 2015-08-03 | Paper |
Generalized Wong sequences and their applications to Edmonds' problems
Journal of Computer and System Sciences | 2015-07-13 | Paper |
Counting curves and their projections
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
Simulating threshold circuits by majority circuits
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
On the computational complexity of measuring global stability of banking networks
Algorithmica | 2015-01-19 | Paper |
Inapproximability of dominating set on power law graphs
Theoretical Computer Science | 2014-12-02 | Paper |
Approximate counting of matchings in \((3,3)\)-hypergraphs
Algorithm Theory – SWAT 2014 | 2014-09-02 | Paper |
Complexity of Nondeterministic Graph Parameter Testing
| 2014-08-15 | Paper |
Optimal cuts and partitions in tree metrics in polynomial time
Information Processing Letters | 2014-08-13 | Paper |
Deterministic polynomial factoring and association schemes
LMS Journal of Computation and Mathematics | 2014-07-23 | Paper |
Limits of CSP Problems and Efficient Parameter Testing
| 2014-06-13 | Paper |
New inapproximability bounds for TSP
Algorithms and Computation | 2014-01-14 | Paper |
Approximating subdense instances of covering problems
Electronic Notes in Discrete Mathematics | 2013-07-23 | Paper |
Exact and approximation algorithms for geometric and capacitated set cover problems
Algorithmica | 2012-11-21 | Paper |
Approximating vertex cover in dense hypergraphs
Journal of Discrete Algorithms | 2012-09-13 | Paper |
Schemes for deterministic polynomial factoring
Proceedings of the 2009 international symposium on Symbolic and algebraic computation | 2012-05-13 | Paper |
Trading GRH for algebra: algorithms for factoring polynomials and related structures
Mathematics of Computation | 2012-02-17 | Paper |
Approximation schemes for the betweenness problem in tournaments and related ranking problems
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
Deterministic polynomial time algorithms for matrix completion problems
SIAM Journal on Computing | 2011-04-04 | Paper |
Computational complexity of the perfect matching problem in hypergraphs with subcritical density
International Journal of Foundations of Computer Science | 2011-01-19 | Paper |
Faster algorithms for feedback arc set tournament, Kemeny rank aggregation and betweenness tournament
Algorithms and Computation | 2010-12-09 | Paper |
A 3/2-approximation algorithm for generalized Steiner trees in complete graphs with edge lengths 1 and 2
Algorithms and Computation | 2010-12-09 | Paper |
The mixing time of Glauber dynamics for coloring regular trees
Random Structures \& Algorithms | 2010-11-24 | Paper |
8/7-approximation algorithm for (1,2)-TSP
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Approximation schemes for clustering problems
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Tensor decomposition and approximation schemes for constraint satisfaction problems
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Random sampling and approximation of MAX-CSP problems
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Exact and approximation algorithms for geometric and capacitated set cover problems
Lecture Notes in Computer Science | 2010-07-20 | Paper |
Computational complexity of the Hamiltonian cycle problem in dense hypergraphs
LATIN 2010: Theoretical Informatics | 2010-04-27 | Paper |
Improved approximation algorithms for the quality of service Steiner tree problem.
Lecture Notes in Computer Science | 2010-04-20 | Paper |
The Complexity of Perfect Matching Problems on Dense Hypergraphs
Algorithms and Computation | 2009-12-17 | Paper |
1.25-Approximation Algorithm for Steiner Tree Problem with Distances 1 and 2
Lecture Notes in Computer Science | 2009-10-20 | Paper |
Approximating Transitive Reductions for Directed Networks
Lecture Notes in Computer Science | 2009-10-20 | Paper |
A fast algorithm for adaptive prefix coding
Algorithmica | 2009-07-24 | Paper |
Space Efficient Multi-dimensional Range Reporting
Lecture Notes in Computer Science | 2009-07-23 | Paper |
Stopping Times, Metrics and Approximate Counting
Automata, Languages and Programming | 2009-03-12 | Paper |
Path coupling using stopping times and counting independent sets and colorings in hypergraphs
Random Structures \& Algorithms | 2008-06-05 | Paper |
Approximating Huffman codes in parallel
Journal of Discrete Algorithms | 2008-01-11 | Paper |
EMBEDDING POINT SETS INTO PLANE GRAPHS OF SMALL DILATION
International Journal of Computational Geometry & Applications | 2007-07-13 | Paper |
Computational complexity of some restricted instances of 3-SAT
Discrete Applied Mathematics | 2007-04-13 | Paper |
Optimal trade-off for Merkle tree traversal
Theoretical Computer Science | 2007-03-15 | Paper |
Algorithms and Computation
Lecture Notes in Computer Science | 2006-11-14 | Paper |
Algorithms and Computation
Lecture Notes in Computer Science | 2006-11-14 | Paper |
Fundamentals of Computation Theory
Lecture Notes in Computer Science | 2006-10-20 | Paper |
TSP with bounded metrics
Journal of Computer and System Sciences | 2006-06-30 | Paper |
Algorithms – ESA 2005
Lecture Notes in Computer Science | 2006-06-27 | Paper |
On the computational power of probabilistic and quantum branching program
Information and Computation | 2006-01-10 | Paper |
Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs
SIAM Journal on Computing | 2005-10-28 | Paper |
Improved approximation algorithms for the quality of service multicast tree problem
Algorithmica | 2005-08-02 | Paper |
scientific article; zbMATH DE number 2140434 (Why is no real title available?)
| 2005-03-03 | Paper |
scientific article; zbMATH DE number 2119646 (Why is no real title available?)
| 2004-11-29 | Paper |
scientific article; zbMATH DE number 2119705 (Why is no real title available?)
| 2004-11-29 | Paper |
Random sampling and approximation of MAX-CSPs
Journal of Computer and System Sciences | 2004-11-18 | Paper |
scientific article; zbMATH DE number 2102760 (Why is no real title available?)
| 2004-09-24 | Paper |
Approximability of Dense Instances of Nearest Codeword Problem
Algorithm Theory — SWAT 2002 | 2004-08-12 | Paper |
scientific article; zbMATH DE number 2086657 (Why is no real title available?)
| 2004-08-11 | Paper |
scientific article; zbMATH DE number 2086676 (Why is no real title available?)
| 2004-08-11 | Paper |
scientific article; zbMATH DE number 2077152 (Why is no real title available?)
| 2004-07-01 | Paper |
A lower bound for integer multiplication on randomized ordered read-once branching programs.
Information and Computation | 2004-03-14 | Paper |
Polynomial time approximation schemes for dense instances of minimum constraint satisfaction
Random Structures \& Algorithms | 2003-08-06 | Paper |
scientific article; zbMATH DE number 1947393 (Why is no real title available?)
| 2003-07-08 | Paper |
scientific article; zbMATH DE number 1929926 (Why is no real title available?)
| 2003-06-18 | Paper |
On the complexity of pattern matching for highly compressed two-dimensional texts.
Journal of Computer and System Sciences | 2003-05-14 | Paper |
Approximating volumes and integrals in o-minimal and p-minimal theories
| 2003-01-22 | Paper |
Learning by the process of elimination
Information and Computation | 2003-01-14 | Paper |
scientific article; zbMATH DE number 1839432 (Why is no real title available?)
| 2002-12-02 | Paper |
scientific article; zbMATH DE number 1839429 (Why is no real title available?)
| 2002-12-02 | Paper |
Improved approximation of Max-Cut on graphs of bounded degree
Journal of Algorithms | 2002-09-30 | Paper |
scientific article; zbMATH DE number 1775446 (Why is no real title available?)
| 2002-08-01 | Paper |
On the approximation hardness of dense TSP and other path problems
Information Processing Letters | 2002-07-25 | Paper |
A note on approximating Max-Bisection on regular graphs
Information Processing Letters | 2002-07-14 | Paper |
Randomized splay trees: Theoretical and experimental results.
Information Processing Letters | 2002-07-14 | Paper |
scientific article; zbMATH DE number 1754594 (Why is no real title available?)
| 2002-06-12 | Paper |
Polynomial time approximation schemes for some dense instances of NP-hard optimization problems
Algorithmica | 2002-02-19 | Paper |
scientific article; zbMATH DE number 1263195 (Why is no real title available?)
| 2002-01-30 | Paper |
scientific article; zbMATH DE number 1688377 (Why is no real title available?)
| 2002-01-09 | Paper |
scientific article; zbMATH DE number 1263204 (Why is no real title available?)
| 2001-08-27 | Paper |
On BPP versus \(NP\cup coNP\) for ordered read-once branching programs
Theoretical Computer Science | 2001-08-20 | Paper |
scientific article; zbMATH DE number 1263351 (Why is no real title available?)
| 2001-06-21 | Paper |
Compact cellular algebras and permutation groups
Discrete Mathematics | 2001-03-05 | Paper |
scientific article; zbMATH DE number 1559524 (Why is no real title available?)
| 2001-02-28 | Paper |
On-Line Load Balancing for Related Machines
Journal of Algorithms | 2000-10-04 | Paper |
scientific article; zbMATH DE number 1504692 (Why is no real title available?)
| 2000-09-12 | Paper |
scientific article; zbMATH DE number 1496577 (Why is no real title available?)
| 2000-08-27 | Paper |
Zero testing of \(p\)-adic and modular polynomials
Theoretical Computer Science | 2000-08-23 | Paper |
scientific article; zbMATH DE number 1490003 (Why is no real title available?)
| 2000-08-13 | Paper |
An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
Theoretical Computer Science | 2000-06-15 | Paper |
On a new high dimensional Weisfeiler-Lehman algorithm
Journal of Algebraic Combinatorics | 2000-05-25 | Paper |
scientific article; zbMATH DE number 1306858 (Why is no real title available?)
| 2000-04-26 | Paper |
A generalization of Wilkie's theorem of the complement, and an application to Pfaffian closure
Selecta Mathematica. New Series | 2000-03-23 | Paper |
Polynomial time approximation schemes for dense instances of \( \mathcal{NP}\)-hard problems
Journal of Computer and System Sciences | 2000-02-17 | Paper |
scientific article; zbMATH DE number 1390051 (Why is no real title available?)
| 2000-01-17 | Paper |
scientific article; zbMATH DE number 1256781 (Why is no real title available?)
| 1999-10-04 | Paper |
scientific article; zbMATH DE number 1273635 (Why is no real title available?)
| 1999-09-09 | Paper |
scientific article; zbMATH DE number 1263209 (Why is no real title available?)
| 1999-06-29 | Paper |
scientific article; zbMATH DE number 1253966 (Why is no real title available?)
| 1999-05-30 | Paper |
Counting curves and their projections
Computational Complexity | 1999-05-05 | Paper |
scientific article; zbMATH DE number 1283999 (Why is no real title available?)
| 1999-05-03 | Paper |
scientific article; zbMATH DE number 1283990 (Why is no real title available?)
| 1999-05-03 | Paper |
An exponential lower bound on the size of algebraic decision trees for MAX
Computational Complexity | 1999-02-02 | Paper |
Alphabet-independent optimal parallel search for three-dimensional patterns
Theoretical Computer Science | 1999-01-12 | Paper |
scientific article; zbMATH DE number 1163714 (Why is no real title available?)
| 1998-10-01 | Paper |
Matching and multidimensional matching in chordal and strongly chordal graphs
Discrete Applied Mathematics | 1998-07-28 | Paper |
Correctness of constructing optimal alphabetic trees revisited
Theoretical Computer Science | 1998-07-22 | Paper |
scientific article; zbMATH DE number 1151367 (Why is no real title available?)
| 1998-05-13 | Paper |
A lower bound for randomized algebraic decision trees
Computational Complexity | 1998-05-13 | Paper |
Randomization and the computational power of analytic and algebraic decision trees
Computational Complexity | 1998-05-13 | Paper |
Simulating Threshold Circuits by Majority Circuits
SIAM Journal on Computing | 1998-05-10 | Paper |
Computing the Additive Complexity of Algebraic Circuits with Root Extracting
SIAM Journal on Computing | 1998-05-10 | Paper |
New approximation algorithms for the Steiner tree problems
Journal of Combinatorial Optimization | 1998-04-13 | Paper |
scientific article; zbMATH DE number 1104353 (Why is no real title available?)
| 1998-02-02 | Paper |
scientific article; zbMATH DE number 1086494 (Why is no real title available?)
| 1997-11-13 | Paper |
scientific article; zbMATH DE number 1045405 (Why is no real title available?)
| 1997-09-18 | Paper |
On randomized versus deterministic computation
Theoretical Computer Science | 1997-09-09 | Paper |
scientific article; zbMATH DE number 994059 (Why is no real title available?)
| 1997-07-06 | Paper |
Lower bound on testing membership to a polyhedron by algebraic decision and computation trees
Discrete \& Computational Geometry | 1997-03-23 | Paper |
Polynomial bounds for VC dimension of sigmoidal and general Pfaffian neural networks
Journal of Computer and System Sciences | 1997-03-18 | Paper |
On some approximation problems concerning sparse polynomials over finite fields
Theoretical Computer Science | 1997-02-27 | Paper |
Computability of the additive complexity of algebraic circuits with root extracting
Theoretical Computer Science | 1997-02-27 | Paper |
scientific article; zbMATH DE number 871897 (Why is no real title available?)
| 1996-06-16 | Paper |
Resolution for quantified Boolean formulas
Information and Computation | 1995-05-28 | Paper |
scientific article; zbMATH DE number 421669 (Why is no real title available?)
| 1994-11-29 | Paper |
VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions
SIAM Journal on Computing | 1994-11-13 | Paper |
An algorithm to learn read-once threshold formulas, and transformations between learning models
Computational Complexity | 1994-06-19 | Paper |
Computational Complexity of Sparse Rational Interpolation
SIAM Journal on Computing | 1994-04-27 | Paper |
On the Parallel Complexity of Hamiltonian Cycle and Matching Problem on Dense Graphs
Journal of Algorithms | 1994-03-13 | Paper |
scientific article; zbMATH DE number 503193 (Why is no real title available?)
| 1994-02-17 | Paper |
scientific article; zbMATH DE number 432771 (Why is no real title available?)
| 1994-01-02 | Paper |
scientific article; zbMATH DE number 432831 (Why is no real title available?)
| 1993-10-20 | Paper |
Some computational problems in linear algebra as hard as matrix multiplication
Computational Complexity | 1993-10-10 | Paper |
On randomized semi-algebraic test complexity
Journal of Complexity | 1993-08-24 | Paper |
Learning read-once formulas with queries
Journal of the ACM | 1993-05-16 | Paper |
Approximating the Number of Zeroes of a GF[2 Polynomial]
Journal of Algorithms | 1993-05-16 | Paper |
An efficient parallel algorithm for computing a maximal independent set in a hypergraph of dimension 3
Information Processing Letters | 1993-01-16 | Paper |
scientific article; zbMATH DE number 67616 (Why is no real title available?)
| 1992-09-27 | Paper |
Perfect matching for regular graphs is \(AC^ 0\)-hard for the general matching problem
Journal of Computer and System Sciences | 1992-06-28 | Paper |
On zero-testing and interpolation of \(k\)-sparse multivariate polynomials over finite fields
Theoretical Computer Science | 1992-06-26 | Paper |
scientific article; zbMATH DE number 18636 (Why is no real title available?)
| 1992-06-26 | Paper |
The interpolation problem for \(k\)-sparse sums of eigenfunctions of operators
Advances in Applied Mathematics | 1992-06-25 | Paper |
Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields
SIAM Journal on Computing | 1990-01-01 | Paper |
scientific article; zbMATH DE number 4182832 (Why is no real title available?)
| 1989-01-01 | Paper |
Subtree isomorphism is NC reducible to bipartite perfect matching
Information Processing Letters | 1989-01-01 | Paper |
The computational complexity of graph problems with succinct multigraph representation
Zeitschrift für Operations Research | 1988-01-01 | Paper |
scientific article; zbMATH DE number 4085614 (Why is no real title available?)
| 1988-01-01 | Paper |
scientific article; zbMATH DE number 4072403 (Why is no real title available?)
| 1988-01-01 | Paper |
Parallel construction of perfect matchings and Hamiltonian cycles on dense graphs
Theoretical Computer Science | 1988-01-01 | Paper |
scientific article; zbMATH DE number 4091486 (Why is no real title available?)
| 1987-01-01 | Paper |
On the Monte Carlo space constructible functions and separation results for probabilistic complexity classes
Information and Computation | 1987-01-01 | Paper |
On the power of two-way random generators and the impossibility of deterministic poly-space simulation
Information and Control | 1986-01-01 | Paper |
There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator
Information and Control | 1985-01-01 | Paper |
scientific article; zbMATH DE number 3833306 (Why is no real title available?)
| 1983-01-01 | Paper |
Decidability of Skolem matrix emptiness problem entails constructability of exact regular expression
Theoretical Computer Science | 1982-01-01 | Paper |
scientific article; zbMATH DE number 3800927 (Why is no real title available?)
| 1981-01-01 | Paper |
scientific article; zbMATH DE number 3664406 (Why is no real title available?)
| 1980-01-01 | Paper |
scientific article; zbMATH DE number 3770953 (Why is no real title available?)
| 1980-01-01 | Paper |
scientific article; zbMATH DE number 3780563 (Why is no real title available?)
| 1980-01-01 | Paper |
scientific article; zbMATH DE number 3658972 (Why is no real title available?)
| 1979-01-01 | Paper |
scientific article; zbMATH DE number 3555499 (Why is no real title available?)
| 1977-01-01 | Paper |
scientific article; zbMATH DE number 3557275 (Why is no real title available?)
| 1977-01-01 | Paper |
scientific article; zbMATH DE number 3557276 (Why is no real title available?)
| 1977-01-01 | Paper |
scientific article; zbMATH DE number 3572057 (Why is no real title available?)
| 1977-01-01 | Paper |
scientific article; zbMATH DE number 3536061 (Why is no real title available?)
| 1976-01-01 | Paper |
scientific article; zbMATH DE number 3551918 (Why is no real title available?)
| 1976-01-01 | Paper |
Almost Deterministic ω-Automata with Existential Output Condition
Proceedings of the American Mathematical Society | 1975-01-01 | Paper |
scientific article; zbMATH DE number 3523523 (Why is no real title available?)
| 1975-01-01 | Paper |
scientific article; zbMATH DE number 3525049 (Why is no real title available?)
| 1975-01-01 | Paper |
scientific article; zbMATH DE number 3480109 (Why is no real title available?)
| 1974-01-01 | Paper |
scientific article; zbMATH DE number 3442046 (Why is no real title available?)
| 1974-01-01 | Paper |
scientific article; zbMATH DE number 3442043 (Why is no real title available?)
| 1973-01-01 | Paper |
scientific article; zbMATH DE number 3442044 (Why is no real title available?)
| 1973-01-01 | Paper |
scientific article; zbMATH DE number 3442045 (Why is no real title available?)
| 1973-01-01 | Paper |
