Links to co-authors at the bottom of the page.

Refereed articles and articles in reviewed conference proceedings

• Lifting Lower Bounds for Tree-Like Proofs. Maciel, A., Nguyen, P., Pitassi, T. Computational Complexity 23:585-636, 2014.

• A Conditional Lower Bound for a System of Constant-Depth Proofs with Modular Connectives. Maciel, A., Pitassi, T. In Proceedings of the 21st Annual IEEE Symposium on Logic in Computer Science (LICS 06), pp. 189-200, IEEE Computer Society Press, August 2006.

• Non-automatizability of bounded-depth Frege proofs. Bonet, M., Domingo, C., Gavaldà, R., Maciel, A., Pitassi, T. Computational Complexity 13:47-68, 2004.

  Preliminary version in Proceedings of the 14th Annual IEEE Conference on Computational Complexity (CCC 99), pp. 15-23, IEEE Computer Society Press, May 1999.

• A new proof of the weak pigeonhole principle. Maciel, A., Pitassi, T., Woods, A.R. Journal of Computer and Systems Science 64:843-872, 2002.

  Preliminary version in Proceedings of the 32nd Annual ACM Symposium on the Theory of Computing (STOC 00), pp. 368-377, ACM Press, May 2000.

• Programs over semigroups of dot-depth one. Maciel, A., Péladeau, P., Thérien, D. Theoretical Computer Science 245:135-148, 2000.

  Preliminary version presented at the First International Conference on Semigroups and Algebraic Engineering, Aizu-Wakamatsu City, Japan, March 1997.

• Circuit lower bounds collapse relativized complexity classes. Beigel, R., Maciel, A. In Proceedings of the 14th Annual IEEE Conference on Computational Complexity (CCC 99), pp. 222-226, IEEE Computer Society Press, May 1999.

• Efficient threshold circuits for power series. Maciel, A., Thérien, D. Information and Computation 152:62-73, 1999.

• Threshold circuits of small majority-depth. Maciel, A., Thérien, D. Information and Computation 146:55-83, 1998.

• Towards lower bounds for bounded-depth Frege proofs with modular connectives. Maciel, A., Pitassi, T. In Proof Complexity and Feasible Arithmetics, Paul Beame and Sam Buss, eds., DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 39, pp. 195-227, American Mathematical Society, 1998.

  Preliminary version: On ACC⁰[p^k] Frege proofs. In Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC 97), pp. 720-729, ACM Press, May 1997.

• Upper and lower bounds for some depth-3 circuit classes. Beigel, R., Maciel, A. Computational Complexity 6:235-255, 1997.

  Preliminary version in Proceedings of the 12th Annual IEEE Conference on Computational Complexity (CCC 97), pp. 149-157, IEEE Computer Society Press, June 1997.

• Threshold circuits for iterated multiplication: using AC⁰ for free. Maciel, A., Thérien, D. In Proceedings of the 10th Annual Symposium on Theoretical Aspects of Computer Science (STACS 93), Lecture Notes in Computer Science, v. 665, pp. 545-554, Springer-Verlag, 1993.

Technical reports

• Finding the widest empty corridor through a set of points. Houle, M.E., Maciel, A. In Snapshots of Computational and Discrete Geometry, Godfried Toussaint, ed., Technical Report SOCS-88.11, School of Computer Science, McGill University, 1988.

Ph.D. Thesis

• Threshold Circuits of Small Majority-Depth. Ph.D. Thesis, School of Computer Science, McGill University, February 1995.

Unpublished

• Maciel, A. Introduction to Data Abstraction, Algorithms and Data Structures: With C++ and the STL. Notes for a course taught at Clarkson University (CS142). Last iteration: Spring 2023.

• Maciel, A. Automata and Computability. Notes for a course taught at Clarkson University (CS345/MA345/CS541). Last iteration: Fall 2022.

• Barrington, D.A. Mix, Maciel, A. Computational Complexity. Notes for a series of 30 lectures on computational complexity given at the Clay Mathematics Undergraduate Program of the IAS/Park City Mathematics Institute 2000 Summer Session.

Links to co-authors: Barrington, Beigel, Bonet, Gavaldà, Pitassi, Thérien, Woods.