pith. sign in

arxiv: 2607.00742 · v1 · pith:PGEX3E4Ynew · submitted 2026-07-01 · 💻 cs.FL

Algorithms and fine-grained complexity for nondeterministic and symmetric difference automata

Dmitry Chistikov , Rados{\l}aw Pi\'orkowski , Neha Rino , Brink van der Merwe This is my paper

Pith reviewed 2026-07-02 01:51 UTC · model grok-4.3

classification 💻 cs.FL
keywords nondeterministic finite automatasymmetric difference automatafine-grained complexityambiguityacceptance problememptinessequivalenceweighted automata
0
0 comments X

The pith

Under polynomial ambiguity, NFA acceptance reduces randomly to XNFA acceptance, with faster algorithms for bounded ambiguity cases.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows that symmetric difference automata, which accept an input when the number of accepting runs is odd, admit improved fine-grained complexity bounds when ambiguity is limited. A randomized reduction maps the acceptance problem for nondeterministic finite automata to the corresponding problem for symmetric difference automata, provided the automata have polynomial ambiguity. When ambiguity is bounded, both models allow faster decision procedures for acceptance than the general case permits. Faster verification algorithms are also given for certificates of emptiness and equivalence of symmetric difference automata, without needing ambiguity restrictions, and several results carry over to weighted automata over other semirings and fields.

Core claim

Under the assumption of polynomial ambiguity, there is a randomised reduction from NFA acceptance to XNFA acceptance; for bounded ambiguity, acceptance for both NFA and XNFA can be decided faster than in the general case; without ambiguity assumptions, faster algorithms exist for verifying suitable certificates for (non)emptiness and (non)equivalence of XNFA.

What carries the argument

The randomized reduction from NFA acceptance to XNFA acceptance that works when the automata have only polynomially many accepting runs per word.

If this is right

  • Acceptance time bounds for NFAs transfer to XNFAs via the reduction when ambiguity is polynomial.
  • Bounded ambiguity yields strictly improved running times for the acceptance problem in both models.
  • Certificate-based checks for emptiness and equivalence of XNFAs run faster than brute-force enumeration of runs.
  • The same speed-ups and reductions apply to weighted automata over arbitrary semirings and fields.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Ambiguity degree may serve as a natural parameter for obtaining subquadratic or sub-cubic algorithms on automata problems that are hard in the unrestricted case.
  • The reduction technique could be adapted to obtain conditional lower bounds showing that certain XNFA problems are at least as hard as their NFA counterparts.
  • Similar ambiguity-sensitive speed-ups might exist for related decision problems such as universality or inclusion.

Load-bearing premise

The automata have at most polynomially many accepting runs per input word.

What would settle it

A concrete family of polynomially ambiguous automata for which no randomized polynomial-time reduction from NFA acceptance to XNFA acceptance exists, or for which no faster-than-general acceptance algorithm works when ambiguity is bounded.

read the original abstract

Symmetric difference automata (XNFA) are a variant of standard finite automata in which an input word is accepted iff the number of accepting runs is odd. Equivalently, these are weighted automata over the two-element field. We study the fine-grained complexity of the basic decision problems for XNFA: acceptance, emptiness, and equivalence, aiming to optimise the degree of the polynomial in their running-time bounds. Under the assumption of polynomial ambiguity, we provide a randomised reduction of NFA acceptance to XNFA acceptance. For automata of bounded ambiguity (e.g., unambiguous automata), we show that acceptance for both NFA and XNFA can be decided faster than in the general case. Without ambiguity assumptions, we give faster algorithms for the verification of suitable certificates for (non)emptiness and (non)equivalence of XNFA. Several of our results extend to weighted automata over other semirings and fields.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper studies fine-grained complexity of acceptance, emptiness, and equivalence for nondeterministic finite automata (NFAs) and symmetric difference automata (XNFAs, equivalently weighted automata over GF(2)). Under polynomial ambiguity it gives a randomised reduction from NFA acceptance to XNFA acceptance; for bounded ambiguity it gives faster acceptance algorithms for both models; without ambiguity assumptions it gives faster certificate verification for (non)emptiness and (non)equivalence of XNFAs. Several results extend to weighted automata over other semirings and fields.

Significance. If the conditional claims hold, the work improves the polynomial degree in running-time bounds for core automata problems when ambiguity is polynomially or constantly bounded, and supplies a reduction that may transfer fine-grained lower bounds between NFA and XNFA variants. The explicit conditioning on ambiguity assumptions and the extension to other algebraic structures are strengths.

minor comments (2)
  1. [Abstract] Abstract: the statement that acceptance 'can be decided faster than in the general case' for bounded ambiguity would be clearer if it named the new exponent or the precise improvement over the O(n^3) or O(n^ω) baseline used elsewhere in the paper.
  2. The extension paragraph mentions 'other semirings and fields' but does not list which ones receive the full set of results versus which receive only the certificate-verification algorithms; a short table or sentence would remove ambiguity.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation of minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents algorithmic reductions and complexity bounds for NFA and XNFA acceptance, emptiness, and equivalence problems, explicitly conditioned on polynomial or bounded ambiguity assumptions. These are standard complexity-theoretic results derived from reductions and algorithmic techniques rather than any self-referential definitions, fitted parameters renamed as predictions, or load-bearing self-citations that reduce the central claims to their own inputs. The derivation chain consists of independent algorithmic constructions with no equations or steps that equate outputs to inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard definitions from automata theory and complexity theory; no free parameters or invented entities are introduced in the abstract.

axioms (1)
  • standard math Standard definitions of nondeterministic finite automata, weighted automata over fields, and the notion of ambiguity.
    Background for defining XNFA and stating the decision problems.

pith-pipeline@v0.9.1-grok · 5702 in / 1134 out tokens · 28729 ms · 2026-07-02T01:51:55.493721+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

44 extracted references · 40 canonical work pages

  1. [1]

    On the fine-grained complexity of parity problems

    Amir Abboud, Shon Feller, and Oren Weimann. On the fine-grained complexity of parity problems. In 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020 , volume 168 of LIPIcs , pages 5:1--5:19. https://doi.org/10.4230/LIPICS.ICALP.2020.5 doi:10.4230/LIPICS.ICALP.2020.5

    work page doi:10.4230/lipics.icalp.2020.5 2020

  2. [2]

    What's decidable about weighted automata? Inf

    Shaull Almagor, Udi Boker, and Orna Kupferman. What's decidable about weighted automata? Inf. Comput. , 282:104651, 2022. https://doi.org/10.1016/J.IC.2020.104651 doi:10.1016/J.IC.2020.104651

    work page doi:10.1016/j.ic.2020.104651 2022

  3. [3]

    Representing regular languages of infinite words using mod 2 multiplicity automata

    Dana Angluin, Timos Antonopoulos, Dana Fisman, and Nevin George. Representing regular languages of infinite words using mod 2 multiplicity automata. In Foundations of Software Science and Computation Structures - 25th International Conference, FOSSACS 2022 , volume 13242 of Lecture Notes in Computer Science , pages 1--20. https://doi.org/10.1007/978-3-030...

    work page doi:10.1007/978-3-030-99253-8_1 2022

  4. [4]

    Trading group theory for randomness

    L \' a szl \' o Babai. Trading group theory for randomness. In Proceedings of the 17th Annual ACM Symposium on Theory of Computing, 1985 , pages 421--429. https://doi.org/10.1145/22145.22192 doi:10.1145/22145.22192

    work page doi:10.1145/22145.22192 1985

  5. [5]

    Improving Viterbi is hard: Better runtimes imply faster clique algorithms

    Arturs Backurs and Christos Tzamos. Improving Viterbi is hard: Better runtimes imply faster clique algorithms. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017 , volume 70 of Proceedings of Machine Learning Research , pages 311--321. URL: http://proceedings.mlr.press/v70/backurs17a.html

    2017

  6. [6]

    Matrix multiplication verification using coding theory

    Huck Bennett, Karthik Gajulapalli, Alexander Golovnev, and Evelyn Warton. Matrix multiplication verification using coding theory. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2024 , volume 317 of LIPIcs , pages 42:1--42:13. https://doi.org/10.4230/LIPICS.APPROX/RANDOM.2024.42 doi:10.4230/LIPICS....

    work page doi:10.4230/lipics.approx/random.2024.42 2024

  7. [7]

    The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds

    Karl Bringmann, Allan Gr nlund, Marvin K\" u nnemann, and Kasper Green Larsen. The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds . In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024) , volume 287 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 22:1--22:25. https://doi.org/10.4230/LIPIcs.I...

    work page doi:10.4230/lipics.itcs.2024.22 2024

  8. [8]

    Cardon and Maxime Crochemore

    A. Cardon and Maxime Crochemore. D \' e termination de la repr \' e sentation standard d'une s \' e rie reconnaissable. RAIRO Theor. Informatics Appl. , 14(4):371--379, 1980. https://doi.org/10.1051/ITA/1980140403711 doi:10.1051/ITA/1980140403711

    work page doi:10.1051/ita/1980140403711 1980

  9. [9]

    12 Timothy M

    Marco L. Carmosino, Jiawei Gao, Russell Impagliazzo, Ivan Mihajlin, Ramamohan Paturi, and Stefan Schneider. Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science , page 261–270. https://doi.org/10.1145/2840728.284...

    work page doi:10.1145/2840728.2840746 2016

  10. [10]

    Homomorphism indistinguishability, multiplicity automata equivalence, and polynomial identity testing

    Marek Cern \' y and Tim Seppelt. Homomorphism indistinguishability, multiplicity automata equivalence, and polynomial identity testing. In 43rd International Symposium on Theoretical Aspects of Computer Science, STACS 2026 , pages 25:1--25:20. https://doi.org/10.4230/LIPICS.STACS.2026.25 doi:10.4230/LIPICS.STACS.2026.25

    work page doi:10.4230/lipics.stacs.2026.25 2026

  11. [11]

    Pumping lemmas for weighted automata

    Agnishom Chattopadhyay, Filip Mazowiecki, Anca Muscholl, and Cristian Riveros. Pumping lemmas for weighted automata. Log. Methods Comput. Sci. , 17(3), 2021. https://doi.org/10.46298/LMCS-17(3:7)2021 doi:10.46298/LMCS-17(3:7)2021

    work page doi:10.46298/lmcs-17(3:7)2021 2021

  12. [12]

    Unambiguity in automata theory

    Thomas Colcombet. Unambiguity in automata theory. In Descriptional Complexity of Formal Systems - 17th International Workshop, DCFS 2015 , volume 9118 of Lecture Notes in Computer Science , pages 3--18. Springer, 2015. https://doi.org/10.1007/978-3-319-19225-3_1 doi:10.1007/978-3-319-19225-3_1

    work page doi:10.1007/978-3-319-19225-3_1 2015

  13. [13]

    Problems complete for L

    Carsten Damm. Problems complete for L . Information Processing Letters , 36(5):247--250, 1990. https://doi.org/10.1016/0020-0190(90)90150-V doi:10.1016/0020-0190(90)90150-V

    work page doi:10.1016/0020-0190(90)90150-v 1990

  14. [14]

    Containment and equivalence of weighted automata: Probabilistic and max-plus cases

    Laure Daviaud. Containment and equivalence of weighted automata: Probabilistic and max-plus cases. In Language and Automata Theory and Applications - 14th International Conference, LATA 2020 , volume 12038 of Lecture Notes in Computer Science , pages 17--32. Springer, 2020. https://doi.org/10.1007/978-3-030-40608-0_2 doi:10.1007/978-3-030-40608-0_2

    work page doi:10.1007/978-3-030-40608-0_2 2020

  15. [15]

    P \' e rez, and James Worrell

    Laure Daviaud, Marcin Jurdzinski, Ranko Lazic, Filip Mazowiecki, Guillermo A. P \' e rez, and James Worrell. When are emptiness and containment decidable for probabilistic automata? J. Comput. Syst. Sci. , 119:78--96, 2021. https://doi.org/10.1016/J.JCSS.2021.01.006 doi:10.1016/J.JCSS.2021.01.006

    work page doi:10.1016/j.jcss.2021.01.006 2021

  16. [16]

    Fine-grained complexity of ambiguity problems on automata and directed graphs

    Karolina Drabik, Anita D \" u rr, Fabian Frei, Filip Mazowiecki, and Karol Wegrzycki. Fine-grained complexity of ambiguity problems on automata and directed graphs. CoRR , abs/2501.14725, 2025. https://arxiv.org/abs/2501.14725 arXiv:2501.14725 , https://doi.org/10.48550/ARXIV.2501.14725 doi:10.48550/ARXIV.2501.14725

    work page doi:10.48550/arxiv.2501.14725 2025

  17. [17]

    Probabilistic automata of bounded ambiguity

    Nathana \" e l Fijalkow, Cristian Riveros, and James Worrell. Probabilistic automata of bounded ambiguity. Inf. Comput. , 282:104648, 2022. https://doi.org/10.1016/J.IC.2020.104648 doi:10.1016/J.IC.2020.104648

    work page doi:10.1016/j.ic.2020.104648 2022

  18. [18]

    Fast probabilistic algorithms

    Rusins Freivalds. Fast probabilistic algorithms. In Mathematical Foundations of Computer Science 1979 , volume 74 of Lecture Notes in Computer Science , pages 57--69. Springer, 1979. https://doi.org/10.1007/3-540-09526-8_5 doi:10.1007/3-540-09526-8_5

    work page doi:10.1007/3-540-09526-8_5 1979

  19. [19]

    The complexity of iterated multiplication

    Neil Immerman and Susan Landau. The complexity of iterated multiplication. Inf. Comput. , 116(1):103--116, 1995. https://doi.org/10.1006/INCO.1995.1007 doi:10.1006/INCO.1995.1007

    work page doi:10.1006/inco.1995.1007 1995

  20. [20]

    Complexity of k-sat

    Russell Impagliazzo and Ramamohan Paturi. Complexity of k-sat. In Proceedings of the 14th Annual IEEE Conference on Computational Complexity, 1999 , pages 237--240. https://doi.org/10.1109/CCC.1999.766282 doi:10.1109/CCC.1999.766282

    work page doi:10.1109/ccc.1999.766282 1999

  21. [21]

    Minimal NFA problems are hard

    Tao Jiang and Bala Ravikumar. Minimal NFA problems are hard. SIAM J. Comput. , 22(6):1117--1141, 1993. https://doi.org/10.1137/0222067 doi:10.1137/0222067

    work page doi:10.1137/0222067 1993

  22. [22]

    Lipton, and Anastasios Viglas

    George Karakostas, Richard J. Lipton, and Anastasios Viglas. On the complexity of intersecting finite state automata and NL versus NP . Theor. Comput. Sci. , 302(1-3):257--274, 2003. https://doi.org/10.1016/S0304-3975(02)00830-7 doi:10.1016/S0304-3975(02)00830-7

    work page doi:10.1016/s0304-3975(02)00830-7 2003

  23. [23]

    Weighted automata are compact and actively learnable

    Artem Kaznatcheev and Prakash Panangaden. Weighted automata are compact and actively learnable. Inf. Process. Lett. , 171:106133, 2021. https://doi.org/10.1016/J.IPL.2021.106133 doi:10.1016/J.IPL.2021.106133

    work page doi:10.1016/j.ipl.2021.106133 2021

  24. [24]

    Notes on equivalence and minimization of weighted automata

    Stefan Kiefer. Notes on equivalence and minimization of weighted automata. CoRR , abs/2009.01217, 2020. URL: https://arxiv.org/abs/2009.01217, https://arxiv.org/abs/2009.01217 arXiv:2009.01217

    work page arXiv 2009

  25. [25]

    e l Ouaknine, Bj \

    Stefan Kiefer, Andrzej S. Murawski, Jo \" e l Ouaknine, Bj \" o rn Wachter, and James Worrell. On the Complexity of Equivalence and Minimisation for Q-weighted Automata . Logical Methods in Computer Science , 9(1), 2013. https://doi.org/10.2168/LMCS-9(1:8)2013 doi:10.2168/LMCS-9(1:8)2013

    work page doi:10.2168/lmcs-9(1:8)2013 2013

  26. [26]

    Efficiently Computing the Minimum Rank of a Matrix in a Monoid of Zero-One Matrices

    Stefan Kiefer and Andrew Ryzhikov. Efficiently Computing the Minimum Rank of a Matrix in a Monoid of Zero-One Matrices . In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) , volume 327, pages 61:1--61:22, 2025. https://doi.org/10.4230/LIPIcs.STACS.2025.61 doi:10.4230/LIPIcs.STACS.2025.61

    work page doi:10.4230/lipics.stacs.2025.61 2025

  27. [27]

    The equality problem for rational series with multiplicities in the tropical semiring is undecidable

    Daniel Krob. The equality problem for rational series with multiplicities in the tropical semiring is undecidable. International Journal of Algebra and Computation , 4:405--425, 1994. https://doi.org/10.1142/S0218196794000063 doi:10.1142/S0218196794000063

    work page doi:10.1142/s0218196794000063 1994

  28. [28]

    On nondeterministic derandomization of Freivalds' algorithm: Consequences, avenues and algorithmic progress

    Marvin K \" u nnemann. On nondeterministic derandomization of Freivalds' algorithm: Consequences, avenues and algorithmic progress. In 26th Annual European Symposium on Algorithms, ESA 2018 , volume 112 of LIPIcs , pages 56:1--56:16. https://doi.org/10.4230/LIPIcs.ESA.2018.56 doi:10.4230/LIPIcs.ESA.2018.56

    work page doi:10.4230/lipics.esa.2018.56 2018

  29. [29]

    Ryan Williams

    Kasper Green Larsen and R. Ryan Williams. Faster online matrix-vector multiplication. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017 , pages 2182--2189. https://doi.org/10.1137/1.9781611974782.142 doi:10.1137/1.9781611974782.142

    work page doi:10.1137/1.9781611974782.142 2017

  30. [30]

    Meyer and Larry J

    Albert R. Meyer and Larry J. Stockmeyer. The equivalence problem for regular expressions with squaring requires exponential space. In 13th Annual Symposium on Switching and Automata Theory, 1972 , pages 125--129. https://doi.org/10.1109/SWAT.1972.29 doi:10.1109/SWAT.1972.29

    work page doi:10.1109/swat.1972.29 1972

  31. [31]

    An alternative proof of the Schwartz-Zippel lemma

    Dana Moshkovitz. An alternative proof of the Schwartz-Zippel lemma. Electron. Colloquium Comput. Complex. , TR10-096 , 2010. URL: https://eccc.weizmann.ac.il/report/2010/096

    2010

  32. [32]

    Introduction to Probabilistic Automata

    Azaria Paz. Introduction to Probabilistic Automata . Computer Science and Applied Mathematics. Academic Press, New York, 1971

    1971

  33. [33]

    Aaron Potechin and Jeffrey O. Shallit. Lengths of words accepted by nondeterministic finite automata. Inf. Process. Lett. , 162:105993, 2020. https://doi.org/10.1016/J.IPL.2020.105993 doi:10.1016/J.IPL.2020.105993

    work page doi:10.1016/j.ipl.2020.105993 2020

  34. [34]

    On the definition of a family of automata

    Marcel Paul Sch \" u tzenberger. On the definition of a family of automata. Information and Control , 4(2-3):245--270, 1961. https://doi.org/10.1016/S0019-9958(61)80020-X doi:10.1016/S0019-9958(61)80020-X

    work page doi:10.1016/s0019-9958(61)80020-x 1961

  35. [35]

    Schwartz

    Jacob T. Schwartz. Fast probabilistic algorithms for verification of polynomial identities. J. ACM , 27(4):701--717, 1980. https://doi.org/10.1145/322217.322225 doi:10.1145/322217.322225

    work page doi:10.1145/322217.322225 1980

  36. [36]

    Fast construction of irreducible polynomials over finite fields

    Victor Shoup. Fast construction of irreducible polynomials over finite fields. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms , SODA '93, page 484–492, 1993. https://doi.org/10.1006/jsco.1994.1025 doi:10.1006/jsco.1994.1025

    work page doi:10.1006/jsco.1994.1025 1993

  37. [37]

    A polynomial-time algorithm for the equivalence of probabilistic automata

    Wen - Guey Tzeng. A polynomial-time algorithm for the equivalence of probabilistic automata. SIAM J. Comput. , 21(2):216--227, 1992. https://doi.org/10.1137/0221017 doi:10.1137/0221017

    work page doi:10.1137/0221017 1992

  38. [38]

    On path equivalence of nondeterministic finite automata

    Wen - Guey Tzeng. On path equivalence of nondeterministic finite automata. Inf. Process. Lett. , 58(1):43--46, 1996. https://doi.org/10.1016/0020-0190(96)00039-7 doi:10.1016/0020-0190(96)00039-7

    work page doi:10.1016/0020-0190(96)00039-7 1996

  39. [39]

    Minimal DFA for symmetric difference NFA

    Brink van der Merwe, Hellis Tamm, and Lynette van Zijl. Minimal DFA for symmetric difference NFA . In 14th International Workshop on the Descriptional Complexity of Formal Systems, DCFS 2012 , volume 7386 of Lecture Notes in Computer Science , pages 307--318. https://doi.org/10.1007/978-3-642-31623-4_24 doi:10.1007/978-3-642-31623-4_24

    work page doi:10.1007/978-3-642-31623-4_24 2012

  40. [40]

    On binary \( \) - NFAs and succinct descriptions of regular languages

    Lynette van Zijl . On binary \( \) - NFAs and succinct descriptions of regular languages. Theor. Comput. Sci., 2004 , 328(1-2):161--170. https://doi.org/10.1016/J.TCS.2004.07.012 doi:10.1016/J.TCS.2004.07.012

    work page doi:10.1016/j.tcs.2004.07.012 2004

  41. [41]

    Symmetric difference NFA : the state of the art

    Lynette van Zijl and Jaco Geldenhuys. Symmetric difference NFA : the state of the art. In Formal Aspects of Computing: Essays dedicated to Derrick Kourie on the occasion of the 65th birthday , pages 77--92. 2013. URL: http://www.cs.sun.ac.za/\ jaco/PAPERS/vzg13.pdf

    2013

  42. [42]

    Compact normal form for regular languages as xor automata

    Jean Vuillemin and Nicolas Gama. Compact normal form for regular languages as xor automata. In 14th International Conference on Implementation and Application of Automata , CIAA 2009 , volume 5642 of Lecture Notes in Computer Science , pages 24--33. https://doi.org/10.1007/978-3-642-02979-0_6 doi:10.1007/978-3-642-02979-0_6

    work page doi:10.1007/978-3-642-02979-0_6 2009

  43. [43]

    On the degree of ambiguity of finite automata

    Andreas Weber and Helmut Seidl. On the degree of ambiguity of finite automata. Theor. Comput. Sci. , 88(2):325--349, 1991. https://doi.org/10.1016/0304-3975(91)90381-B doi:10.1016/0304-3975(91)90381-B

    work page doi:10.1016/0304-3975(91)90381-b 1991

  44. [44]

    On some fine-grained questions in algorithms and complexity

    Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians (ICM 2018) , pages 3447--3487. Available at https://people.csail.mit.edu/virgi/eccentri.pdf. https://doi.org/10.1142/9789813272880_0188 doi:10.1142/9789813272880_0188

    work page doi:10.1142/9789813272880_0188 2018