More Like this

1. Delta channel networks: 2. Metrics of topologic and dynamic complexity for delta comparison, physical inference, and vulnerability assessment: METRICS OF TOPOLOGIC AND DYNAMIC COMPLEXITY FOR DELTAS

   https://doi.org/10.1002/2014WR016604  

   Tejedor, Alejandro ; Longjas, Anthony ; Zaliapin, Ilya ; Foufoula-Georgiou, Efi ( June 2015 , Water Resources Research)
2. On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1

   https://doi.org/10.3233/COM-220407  

   Allender, Eric ; Balaji, Nikhil ; Datta, Samir ; Pratap, Rameshwar ( June 2023 , Computability)

   We investigate the complexity of languages that correspond to algebraic real numbers, and we present improved upper bounds on the complexity of these languages. Our key technical contribution is the presentation of improved uniform TC 0 circuits for division, matrix powering, and related problems, where the improvement is in terms of “majority depth” (initially studied by Maciel and Thérien). As a corollary, we obtain improved bounds on the complexity of certain problems involving arithmetic circuits, which are known to lie in the counting hierarchy, and we answer a question posed by Yap.

    

   more » « less
3. Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization

   https://doi.org/10.53733/148  

   Allender, Eric ( September 2021 , New Zealand Journal of Mathematics)

   We survey recent developments related to the Minimum Circuit Size Problem and time-bounded Kolmogorov Complexity. 

   more » « less
4. SIGACT News Complexity Theory Column 106: Teaching Models, Computability, and Complexity in Time of COVID-19

   https://doi.org/10.1145/3427361.3427371  

   Hemaspaandra, Lane A. ( September 2020 , ACM SIGACT News)

   As I write this in July 2020, I have no idea what the COVID-19 situation will be like when this September 2020 issue reaches your mailbox or your previewer. My typical advice is to prove exciting theorems. But in these times, all I can share are my hopes: that you'll each be safe and well (and that the medical profes- sion will create an effective vac- cine quickly enough that early in 2021 schools can return to fully in-person teaching); that you'll nd ways to, if a faculty member, help your students thrive even in the hybrid-mode-learning settings they'll probably nd themselves in for the fall semester; and that you'll (while staying careful and safe) nd time to (yes, here it comes) prove exciting theorems. 

   more » « less
5. SIGACT News Complexity Theory Column 117: Thirty Years of Complexity Theory (Columns)

   https://doi.org/10.1145/3586165.3586176  

   Hemaspaandra, Lane A. ( February 2023 , ACM SIGACT News)

   It has been a tremendous treat being the SIGACT News Complexity Theory Column editor for these past thirty years. I thought about what to say here, and realized it is pretty simple: Thank you. 

   more » « less