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

^{0}[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**. Maciel, A., Thérien, D. In^{0}for free*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. - 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.