@inbook{Balcazar1992,
    Abstract = {Highly regular combinatorial objects can be represented advantageously by some kind of description shorter than their full standard encoding. For instance, graphs exhibiting enough regularities can be described using encodings substantially shorter than the full adjacency matrix. Anatural scheme for such succinct representations is by means of boolean circuits computing, as a boolean function, the values of individual bits of the binary encoding of the object. The complexity of many algorithmic problems changes drastically when this succinct representation is used to present the input. Two powerful lemmas quantifying exactly this increase of complexity are presented. These are applied to show that previous results in the area can be interpreted assufficient conditions for completeness in the logarithmic time and polynomial time counting hierarchies.},
    Address = {Boston, MA},
    Author = {Balc{\'a}zar, Jos{\'e} L. and Lozano, Antoni and Tor{\'a}n, Jacobo},
    BookTitle = {Computer Science: Research and Applications},
    Editor = {Baeza-Yates, Ricardo and Manber, Udi},
    File = {The complexity of algorithmic problems on succinct instances - succinct.pdf},
    ISBN = {978-1-4615-3422-8},
    Pages = {351--377},
    Publisher = {Springer US},
    Title = {The Complexity of Algorithmic Problems on Succinct Instances},
    URL = {https://doi.org/10.1007/978-1-4615-3422-8\_30},
    Year = {1992},
    bdsk-url-1 = {https://doi.org/10.1007/978-1-4615-3422-8\_30},
    date-added = {2023-09-21 08:31:00 +0200},
    date-modified = {2023-09-21 08:31:00 +0200},
    doi = {10.1007/978-1-4615-3422-8_30}
}

@inbook{Balcazar1992, Abstract = {Highly regular combinatorial objects can be represented advantageously by some kind of description shorter than their full standard encoding. For instance, graphs exhibiting enough regularities can be described using encodings substantially shorter than the full adjacency matrix. Anatural scheme for such succinct representations is by means of boolean circuits computing, as a boolean function, the values of individual bits of the binary encoding of the object. The complexity of many algorithmic problems changes drastically when this succinct representation is used to present the input. Two powerful lemmas quantifying exactly this increase of complexity are presented. These are applied to show that previous results in the area can be interpreted assufficient conditions for completeness in the logarithmic time and polynomial time counting hierarchies.}, Address = {Boston, MA}, Author = {Balc{\'a}zar, Jos{\'e} L. and Lozano, Antoni and Tor{\'a}n, Jacobo}, BookTitle = {Computer Science: Research and Applications}, Editor = {Baeza-Yates, Ricardo and Manber, Udi}, File = {The complexity of algorithmic problems on succinct instances - succinct.pdf}, ISBN = {978-1-4615-3422-8}, Pages = {351--377}, Publisher = {Springer US}, Title = {The Complexity of Algorithmic Problems on Succinct Instances}, URL = {https://doi.org/10.1007/978-1-4615-3422-8_30}, Year = {1992}, bdsk-url-1 = {https://doi.org/10.1007/978-1-4615-3422-8_30}, date-added = {2023-09-21 08:31:00 +0200}, date-modified = {2023-09-21 08:31:00 +0200}, doi = {10.1007/978-1-4615-3422-8_30} }