More Like this

1. Complexity of Fault Tolerant Query Complexity

   Maharjan, Ramita; Watson, Thomas (January 2022, Proceedings of the 42nd Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Track A)
2. Language Complexity and Speech Recognition Accuracy: Orthographic Complexity Hurts, Phonological Complexity Doesn’t

   Taguchi, Chihiro; Chiang, David (August 2024, ACL Anthology)
3. Proof Complexity Lower Bounds from Algebraic Circuit Complexity

   https://doi.org/10.4086/toc.2021.v017a010  

   Forbes, Michael A.; Shpilka, Amir; Tzameret, Iddo; Wigderson, Avi (January 2021, Theory of Computing)

   Raz, Ran (Ed.)

   We give upper and lower bounds on the power of subsystems of the Ideal Proof System (IPS), the algebraic proof system recently proposed by Grochow and Pitassi, where the circuits comprising the proof come from various restricted algebraic circuit classes. This mimics an established research direction in the boolean setting for subsystems of Extended Frege proofs whose lines are circuits from restricted boolean circuit classes. Essentially all of the subsystems considered in this paper can simulate the well-studied Nullstellensatz proof system, and prior to this work there were no known lower bounds when measuring proof size by the algebraic complexity of the polynomials (except with respect to degree, or to sparsity). Our main contributions are two general methods of converting certain algebraic lower bounds into proof complexity ones. Both require stronger arithmetic lower bounds than common, which should hold not for a specific polynomial but for a whole family defined by it. These may be likened to some of the methods by which Boolean circuit lower bounds are turned into related proof-complexity ones, especially the "feasible interpolation" technique. We establish algebraic lower bounds of these forms for several explicit polynomials, against a variety of classes, and infer the relevant proof complexity bounds. These yield separations between IPS subsystems, which we complement by simulations to create a partial structure theory for IPS systems. Our first method is a functional lower bound, a notion of Grigoriev and Razborov, which is a function f' from n-bit strings to a field, such that any polynomial f agreeing with f' on the boolean cube requires large algebraic circuit complexity. We develop functional lower bounds for a variety of circuit classes (sparse polynomials, depth-3 powering formulas, read-once algebraic branching programs and multilinear formulas) where f'(x) equals 1/p(x) for a constant-degree polynomial p depending on the relevant circuit class. We believe these lower bounds are of independent interest in algebraic complexity, and show that they also imply lower bounds for the size of the corresponding IPS refutations for proving that the relevant polynomial p is non-zero over the boolean cube. In particular, we show super-polynomial lower bounds for refuting variants of the subset-sum axioms in these IPS subsystems. Our second method is to give lower bounds for multiples, that is, to give explicit polynomials whose all (non-zero) multiples require large algebraic circuit complexity. By extending known techniques, we give lower bounds for multiples for various restricted circuit classes such sparse polynomials, sums of powers of low-degree polynomials, and roABPs. These results are of independent interest, as we argue that lower bounds for multiples is the correct notion for instantiating the algebraic hardness versus randomness paradigm of Kabanets and Impagliazzo. Further, we show how such lower bounds for multiples extend to lower bounds for refutations in the corresponding IPS subsystem. 

   more » « less
4. Graph Complexity Measures as Indicators of Verification Complexity

   Jung, Sukhwan; Salado, Alejandro (March 2024, Conference on Systems Engineering Research (CSER))
5. Viral Complexity

   https://doi.org/10.3390/biom12081061  

   Aylward, Frank O.; Moniruzzaman, Mohammad (August 2022, Biomolecules)

   Although traditionally viewed as streamlined and simple, discoveries over the last century have revealed that viruses can exhibit surprisingly complex physical structures, genomic organization, ecological interactions, and evolutionary histories. Viruses can have physical dimensions and genome lengths that exceed many cellular lineages, and their infection strategies can involve a remarkable level of physiological remodeling of their host cells. Virus–virus communication and widespread forms of hyperparasitism have been shown to be common in the virosphere, demonstrating that dynamic ecological interactions often shape their success. And the evolutionary histories of viruses are often fraught with complexities, with chimeric genomes including genes derived from numerous distinct sources or evolved de novo. Here we will discuss many aspects of this viral complexity, with particular emphasis on large DNA viruses, and provide an outlook for future research. 

   more » « less