Dima Grigoriev

Proceedings of the 42nd International Symposium on Theoretical Aspects of Computer Science, 2025

2024

The entropy of the radical ideal of a tropical curve.

[BibT_eX]

[DOI]

Adv. Appl. Math., February, 2024

Semialgebraic Proofs, IPS Lower Bounds, and the $\boldsymbol{\tau}$-Conjecture: Can a Natural Number be Negative?

[BibT_eX]

[DOI]

SIAM J. Comput., 2024

Tropical proof systems.

[BibT_eX]

[DOI]

Yaroslav Alekseev

Electron. Colloquium Comput. Complex., 2024

2023

Tropical Newton-Puiseux polynomials II.

[BibT_eX]

[DOI]

J. Symb. Comput., 2023

BASS: Boolean Automorphisms Signature Scheme.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2023

Tropical cryptography III: digital signatures.

[BibT_eX]

[DOI]

Jiale Chen

IACR Cryptol. ePrint Arch., 2023

Digital signature schemes using non-square matrices or scrap automorphisms.

[BibT_eX]

[DOI]

Jiale Chen

IACR Cryptol. ePrint Arch., 2023

Excitable media store and transfer complicated information via topological defect motion.

[BibT_eX]

[DOI]

Ivan Sudakow

Sergey Vakulenko

Commun. Nonlinear Sci. Numer. Simul., 2023

2022

On a tropical version of the Jacobian conjecture.

[BibT_eX]

[DOI]

Danylo V. Radchenko

J. Symb. Comput., 2022

Entropy of tropical holonomic sequences.

[BibT_eX]

[DOI]

J. Symb. Comput., 2022

2021

Efficiently and Effectively Recognizing Toricity of Steady State Varieties.

[BibT_eX]

[DOI]

Math. Comput. Sci., 2021

RSA and redactable blockchains.

[BibT_eX]

[DOI]

Int. J. Comput. Math. Comput. Syst. Theory, 2021

Probability theory and public-key cryptography.

[BibT_eX]

[DOI]

Mariya Bessonov

Int. J. Comput. Math. Comput. Syst. Theory, 2021

Complexity of deciding whether a tropical linear prevariety is a tropical variety.

[BibT_eX]

[DOI]

Appl. Algebra Eng. Commun. Comput., 2021

2020

Decomposing tropical rational functions.

[BibT_eX]

[DOI]

J. Symb. Comput., 2020

Identifying the parametric occurrence of multiple steady states for some biological networks.

[BibT_eX]

[DOI]

J. Symb. Comput., 2020

Tropical Combinatorial Nullstellensatz and Sparse Polynomials.

[BibT_eX]

[DOI]

Found. Comput. Math., 2020

Tropical recurrent sequences.

[BibT_eX]

[DOI]

Adv. Appl. Math., 2020

Semi-algebraic proofs, IPS lower bounds, and the τ-conjecture: can a natural number be negative?

[BibT_eX]

[DOI]

Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, 2020

2019

Key agreement based on automaton groups.

[BibT_eX]

[DOI]

Rostislav I. Grigorchuk

Groups Complex. Cryptol., 2019

Semi-Algebraic Proofs, IPS Lower Bounds and the $\tau$-Conjecture: Can a Natural Number be Negative?

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2019

2018

Tropical cryptography II: extensions by homomorphisms.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2018

Tropical Effective Primary and Dual Nullstellensätze.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 2018

On semiring complexity of Schur polynomials.

[BibT_eX]

[DOI]

Comput. Complex., 2018

A Framework for Unconditionally Secure Public-Key Encryption (with Possible Decryption Errors).

[BibT_eX]

[DOI]

Mariya Bessonov

Proceedings of the Mathematical Software - ICMS 2018, 2018

Orthogonal Tropical Linear Prevarieties.

[BibT_eX]

[DOI]

Proceedings of the Computer Algebra in Scientific Computing - 20th International Workshop, 2018

Tropical Newton-Puiseux Polynomials.

[BibT_eX]

[DOI]

Proceedings of the Computer Algebra in Scientific Computing - 20th International Workshop, 2018

2017

Yao's Millionaires' Problem and Public-Key Encryption Without Computational Assumptions.

[BibT_eX]

[DOI]

Laszlo B. Kish

Int. J. Found. Comput. Sci., 2017

Probabilistic solution of Yao's millionaires' problem.

[BibT_eX]

[DOI]

Mariya Bessonov

IACR Cryptol. ePrint Arch., 2017

Secure Multiparty Computation without One-way Functions.

[BibT_eX]

[DOI]

FLAP, 2017

Bounds on the Number of Connected Components for Tropical Prevarieties.

[BibT_eX]

[DOI]

Alex Davydow

Discret. Comput. Geom., 2017

Tropical differential equations.

[BibT_eX]

[DOI]

Adv. Appl. Math., 2017

A Case Study on the Parametric Occurrence of Multiple Steady States.

[BibT_eX]

[DOI]

Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, 2017

Tropical Combinatorial Nullstellensatz and Fewnomials Testing.

[BibT_eX]

[DOI]

Proceedings of the Fundamentals of Computation Theory - 21st International Symposium, 2017

Symbolic Versus Numerical Computation and Visualization of Parameter Regions for Multistationarity of Biological Networks.

[BibT_eX]

[DOI]

Proceedings of the Computer Algebra in Scientific Computing - 19th International Workshop, 2017

2016

Complexity of tropical Schur polynomials.

[BibT_eX]

[DOI]

Gleb A. Koshevoy

J. Symb. Comput., 2016

Subtraction-Free Complexity, Cluster Transformations, and Spanning Trees.

[BibT_eX]

[DOI]

Sergey Fomin

Gleb A. Koshevoy

Found. Comput. Math., 2016

Algorithms and Effectivity in Tropical Mathematics and Beyond (Dagstuhl Seminar 16482).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2016

Geometric analysis of pathways dynamics: Application to versatility of TGF-β receptors.

[BibT_eX]

[DOI]

Biosyst., 2016

2015

Detection of Hopf bifurcations in chemical reaction networks using convex coordinates.

[BibT_eX]

[DOI]

J. Comput. Phys., 2015

Complexity of Tropical and Min-plus Linear Prevarieties.

[BibT_eX]

[DOI]

Comput. Complex., 2015

Tropical Effective Primary and Dual Nullstellens"atze.

[BibT_eX]

[DOI]

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

Symbolic Dynamics of Biochemical Pathways as Finite States Machines.

[BibT_eX]

[DOI]

Proceedings of the Computational Methods in Systems Biology, 2015

Analysis of Reaction Network Systems Using Tropical Geometry.

[BibT_eX]

[DOI]

Proceedings of the Computer Algebra in Scientific Computing - 17th International Workshop, 2015

Computing Highest-Order Divisors for a Class of Quasi-Linear Partial Differential Equations.

[BibT_eX]

[DOI]

Proceedings of the Computer Algebra in Scientific Computing - 17th International Workshop, 2015

Polynomial Complexity Recognizing a Tropical Linear Variety.

[BibT_eX]

[DOI]

Proceedings of the Computer Algebra in Scientific Computing - 17th International Workshop, 2015

2014

Yao's Millionaires' Problem and Decoy-Based Public Key Encryption by Classical Physics.

[BibT_eX]

[DOI]

Int. J. Found. Comput. Sci., 2014

Tensor Rank: Matching Polynomials and Schur Rings.

[BibT_eX]

[DOI]

Mikhail E. Muzychuk

Found. Comput. Math., 2014

Punctuated evolution and robustness in morphogenesis.

[BibT_eX]

[DOI]

Biosyst., 2014

2013

Secure information transmission based on physical principles.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2013

Tropical cryptography.

[BibT_eX]

[DOI]

IACR Cryptol. ePrint Arch., 2013

Secrecy without one-way functions.

[BibT_eX]

[DOI]

Groups Complex. Cryptol., 2013

Subtraction-free complexity and cluster transformations.

[BibT_eX]

[DOI]

Sergey Fomin

Gleb A. Koshevoy

CoRR, 2013

Complexity of Solving Tropical Linear Systems.

[BibT_eX]

[DOI]

Comput. Complex., 2013

Computing Divisors and Common Multiples of Quasi-linear Ordinary Differential Equations.

[BibT_eX]

[DOI]

Proceedings of the Computer Algebra in Scientific Computing - 15th International Workshop, 2013

Complexity in Tropical Algebra (Invited Talk).

[BibT_eX]

[DOI]

Proceedings of the Computer Algebra in Scientific Computing - 15th International Workshop, 2013

Polynomial Complexity of Solving Systems of Few Algebraic Equations with Small Degrees.

[BibT_eX]

[DOI]

Proceedings of the Computer Algebra in Scientific Computing - 15th International Workshop, 2013

Efficient Methods to Compute Hopf Bifurcations in Chemical Reaction Networks Using Reaction Coordinates.

[BibT_eX]

[DOI]

Proceedings of the Computer Algebra in Scientific Computing - 15th International Workshop, 2013

2012

No-leak authentication by the Sherlock Holmes method.

[BibT_eX]

[DOI]

Groups Complex. Cryptol., 2012

Continuous hard-to-invert functions and biometric authentication.

[BibT_eX]

[DOI]

Sergey I. Nikolenko

Groups Complex. Cryptol., 2012

Hybrid models of the cell cycle molecular machinery

[BibT_eX]

[DOI]

Proceedings of the Proceedings First International Workshop on Hybrid Systems and Biology, 2012

On a tropical dual Nullstellensatz.

[BibT_eX]

[DOI]

Adv. Appl. Math., 2012

Complexity of Solving Systems with Few Independent Monomials and Applications to Mass-Action Kinetics.

[BibT_eX]

[DOI]

Andreas Weber

Proceedings of the Computer Algebra in Scientific Computing - 14th International Workshop, 2012

2011

Tropical Geometries and Dynamics of Biochemical Networks Application to Hybrid Cell Cycle Models.

[BibT_eX]

[DOI]

Proceedings of the 2nd International Workshop on Static Analysis and Systems Biology, 2011

2010

Preface.

[BibT_eX]

[DOI]

Sergei N. Artëmov

Volker Diekert

Theory Comput. Syst., 2010

A low complexity probabilistic test for integer multiplication.

[BibT_eX]

[DOI]

Gerald Tenenbaum

J. Complex., 2010

Authentication schemes from actions on graphs, groups, or rings.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2010

Absolute factoring of non-holonomic ideals in the plane.

[BibT_eX]

[DOI]

Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2010

2009

Authentication from Matrix Conjugation.

[BibT_eX]

[DOI]

Groups Complex. Cryptol., 2009

A Complete Public-Key Cryptosystem.

[BibT_eX]

[DOI]

Konstantin Pervyshev

Groups Complex. Cryptol., 2009

2008

Foreword.

[BibT_eX]

[DOI]

Sergei N. Artëmov

Volker Diekert

Theory Comput. Syst., 2008

Zero-knowledge authentication schemes from actions on graphs, groups, or rings

[BibT_eX]

[DOI]

CoRR, 2008

Probabilistic Communication Complexity Over The Reals.

[BibT_eX]

[DOI]

Comput. Complex., 2008

Loewy decomposition of third-order linear aPDE's in the plane.

[BibT_eX]

[DOI]

Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2008

2007

Loewy and primary decompositions of D-modules.

[BibT_eX]

[DOI]

Adv. Appl. Math., 2007

2006

Algorithms and complexity in biological pattern formation problems.

[BibT_eX]

[DOI]

Sergei Vakulenko

Ann. Pure Appl. Log., 2006

Homomorphic Public-Key Cryptosystems and Encrypting Boolean Circuits.

[BibT_eX]

[DOI]

Appl. Algebra Eng. Commun. Comput., 2006

2005

Weak Bézout inequality for D-modules.

[BibT_eX]

[DOI]

J. Complex., 2005

Time hierarchies for cryptographic function inversion with advice

[BibT_eX]

[DOI]

Konstantin Pervyshev

Electron. Colloquium Comput. Complex., 2005

Polynomial-time computing over quadratic maps i: sampling in real algebraic sets.

[BibT_eX]

[DOI]

Dmitrii V. Pasechnik

Comput. Complex., 2005

Generalized Loewy-decomposition of d-modules.

[BibT_eX]

[DOI]

Proceedings of the Symbolic and Algebraic Computation, 2005

2004

Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon.

[BibT_eX]

[DOI]

Dima Burago

Anatol Slissenko

Theor. Comput. Sci., 2004

Factoring and Solving Linear Partial Differential Equations.

[BibT_eX]

[DOI]

Computing, 2004

2003

Algebraic proof systems over formulas.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2003

Homomorphic public-key cryptosystems over groups and rings

[BibT_eX]

[DOI]

CoRR, 2003

2002

Approximation and Complexity II: Iterated Integration.

[BibT_eX]

[DOI]

Found. Comput. Math., 2002

Public-key cryptography and invariant theory

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2002

On non-abelian homomorphic public-key cryptosystems

[BibT_eX]

[DOI]

CoRR, 2002

Exponential Lower Bound for Static Semi-algebraic Proofs.

[BibT_eX]

[DOI]

Dmitrii V. Pasechnik

Proceedings of the Automata, Languages and Programming, 29th International Colloquium, 2002

2001

Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 2001

There are No Sparse NP<sub>w</sub>-Hard Sets.

[BibT_eX]

[DOI]

Felipe Cucker

SIAM J. Comput., 2001

Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2001

Approximation and Complexity: Liouvillean-Type Theorems for Linear Differential Equations on an Interval.

[BibT_eX]

[DOI]

Found. Comput. Math., 2001

Complexity of semi-algebraic proofs

[BibT_eX]

[DOI]

Dmitrii V. Pasechnik

Electron. Colloquium Comput. Complex., 2001

Complexity of Positivstellensatz proofs for the knapsack.

[BibT_eX]

[DOI]

Comput. Complex., 2001

Complexity of Null-and Positivstellensatz proofs.

[BibT_eX]

[DOI]

Ann. Pure Appl. Log., 2001

2000

Topological Complexity of the Range Searching.

[BibT_eX]

[DOI]

J. Complex., 2000

Exponential Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions over Finite Fields.

[BibT_eX]

[DOI]

Alexander A. Razborov

Appl. Algebra Eng. Commun. Comput., 2000

Algorithms for Computing Sparse Shifts for Multivariate Polynomials.

[BibT_eX]

[DOI]

Yagati N. Lakshman

Appl. Algebra Eng. Commun. Comput., 2000

Bounds on numers of vectors of multiplicities for polynomials which are easy to compute.

[BibT_eX]

[DOI]

Proceedings of the 2000 International Symposium on Symbolic and Algebraic Computation, 2000

1999

Complexity Lower Bounds for Approximation Algebraic Computation Trees.

[BibT_eX]

[DOI]

Felipe Cucker

J. Complex., 1999

Randomized Complexity Lower Bound for Arrangements and Polyhedra.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 1999

Complexity lower bounds for randomized computation trees over zero characteristic fields.

[BibT_eX]

[DOI]

Comput. Complex., 1999

Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract).

[BibT_eX]

[DOI]

Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999

1998

Computing the Additive Complexity of Algebraic Circuits with Root Extracting.

[BibT_eX]

[DOI]

SIAM J. Comput., 1998

An exponential lower bound on the size of algebraic decision trees for Max.

[BibT_eX]

[DOI]

Andrew Chi-Chih Yao

Comput. Complex., 1998

An Exponential Lower Bound for Depth 3 Arithmetic Circuits.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Randomized Complexity Lower Bounds.

[BibT_eX]

[DOI]

Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, 1998

Polytime Algorithm for the Shortest Path in a Homotopy Class Amidst Semi-Algebraic Obstacles in the Plane.

[BibT_eX]

[DOI]

Anatol Slissenko

Proceedings of the 1998 International Symposium on Symbolic and Algebraic Computation, 1998

Exponential Complexity Lower Bounds for Depth 3 Arithmetic Circuits in Algebras of Functions Over Finite Fields.

[BibT_eX]

[DOI]

Alexander A. Razborov

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

Tseitin's Tautologies and Lower Bounds for Nullstellensatz Proofs.

[BibT_eX]

[DOI]

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997

Testing Shift-Equivalence of Polynomials by Deterministic, Probabilistic and Quantum Machines.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1997

On the Power of Real Turing Machines Over Binary Inputs.

[BibT_eX]

[DOI]

Felipe Cucker

SIAM J. Comput., 1997

Nearly Sharp Complexity Bounds for Multiprocessor Algebraic Computations.

[BibT_eX]

[DOI]

J. Complex., 1997

Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision and Computation Trees.

[BibT_eX]

[DOI]

Discret. Comput. Geom., 1997

Randomization and the Computational Power of Analytic and Algebraic Decision Trees.

[BibT_eX]

[DOI]

Roman Smolensky

Comput. Complex., 1997

A Lower Bound for Randomized Algebraic Decision Trees.

[BibT_eX]

[DOI]

Friedhelm Meyer auf der Heide

Roman Smolensky

Comput. Complex., 1997

Computing Minimum-Link Path in a Homotopy Class amidst Semi-Algebraic Obstacles in the Plane.

[BibT_eX]

[DOI]

Anatol Slissenko

Proceedings of the Applied Algebra, 1997

1996

Complexity Lower Bounds for Computation Trees with Elementary Transcendental Function Gates.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

Computability of the Additive Complexity of Algebraic Circuits with Root Extracting.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

NC Solving of a System of Linear Ordinary Differential Equations in Several Unknowns.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1996

Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann.

[BibT_eX]

[DOI]

Andrew M. Odlyzko

Fundam. Informaticae, 1996

Randomized Omega(n<sup>2</sup>) Lower Bound for Knapsack

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1996

Testing Shift-Equivalence of Polynomials Using Quantum Machines.

[BibT_eX]

[DOI]

Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, 1996

1995

On Computing Algebraic Functions Using Logarithms and Exponentials.

[BibT_eX]

[DOI]

Andrew Chi-Chih Yao

SIAM J. Comput., 1995

Improved Lower Bound on Testing Membership to a Polyhedron by Algebraic Decision Trees.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual Symposium on Foundations of Computer Science, 1995

1994

Deviation Theorems for Solutions of Differential Equations and Applications to Lower Bounds on Parallel Complexity of Sigmoids.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1994

Computational Complexity of Sparse Rational Interpolation.

[BibT_eX]

[DOI]

SIAM J. Comput., 1994

Lower bounds on testing membership to a polyhedron by algebraic decision trees.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 1994

1993

A Zero-Test and an Interpolation Algorithm for the Shifted Sparse Polynominals.

[BibT_eX]

[DOI]

Proceedings of the Applied Algebra, 1993

1992

Existence of Short Proofs for Nondivisibility of Sparse Polynomials under the Extended Riemann Hypothesis.

[BibT_eX]

[DOI]

Andrew M. Odlyzko

Proceedings of the 1992 International Symposium on Symbolic and Algebraic Computation, 1992

1991

Algorithms for Sparse Rational Interpolation.

[BibT_eX]

[DOI]

Proceedings of the 1991 International Symposium on Symbolic and Algebraic Computation, 1991

An Approximation Algorithm for the Number of Zeros of Arbitrary Polynomials over GF[q]

[BibT_eX]

[DOI]

Proceedings of the 32nd Annual Symposium on Foundations of Computer Science, 1991

1990

Fast Parallel Algorithms for Sparse Multivariate Polynomial Interpolation over Finite Fields.

[BibT_eX]

[DOI]

SIAM J. Comput., 1990

Complexity of Factoring and Calculating the GCD of Linear Ordinary Differential Operators.

[BibT_eX]

[DOI]

J. Symb. Comput., 1990

Complexity of Irreducibility Testing for a System of Linear Ordinary Differential Equations.

[BibT_eX]

[DOI]

Proceedings of the International Symposium on Symbolic and Algebraic Computation, 1990

How to Test in Subexponential Time Whether Two Points Can Be Connected by a Curve in a Semialgebraic Set.

[BibT_eX]

[DOI]

Proceedings of the International Symposium on Symbolic and Algebraic Computation, 1990

Interpolation of Sparse Rational Functions Without Knowing Bounds on Exponents

[BibT_eX]

[DOI]

Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990

1988

Solving Systems of Polynomial Inequalities in Subexponential Time.

[BibT_eX]

[DOI]

J. Symb. Comput., 1988

Complexity of Deciding Tarski Algebra.

[BibT_eX]

[DOI]

J. Symb. Comput., 1988

1987

The Matching Problem for Bipartite Graphs with Polynomially Bounded Permanents Is in NC (Extended Abstract)

[BibT_eX]

[DOI]

Proceedings of the 28th Annual Symposium on Foundations of Computer Science, 1987

1984

Complexity of Quantifier Elimination in the Theory of Algebraically Closed Fields.

[BibT_eX]

[DOI]

Alexander L. Chistov

Proceedings of the Mathematical Foundations of Computer Science 1984, 1984

1982

Additive Complexity in Directed Computations.

[BibT_eX]

[DOI]

Theor. Comput. Sci., 1982

1981

Multiplicative Complexity of a Bilinear Form over a Commutative Ring.

[BibT_eX]

[DOI]

Proceedings of the Mathematical Foundations of Computer Science 1981, Strbske Pleso, Czechoslovakia, August 31, 1981

1978

Multiplicative Complexity of a Pair of Bilinear Forms and of the Polynomial Multiplication.

[BibT_eX]

[DOI]