| 2009 |
|---|
| 92 | EE | Toniann Pitassi,
Nathan Segerlind:
Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures.
SODA 2009: 355-364 |
| 2008 |
|---|
| 91 | | Philipp Hertel,
Fahiem Bacchus,
Toniann Pitassi,
Allen Van Gelder:
Clause Learning Can Effectively P-Simulate General Propositional Resolution.
AAAI 2008: 283-290 |
| 90 | EE | Matei David,
Toniann Pitassi,
Emanuele Viola:
Improved Separations between Nondeterministic and Randomized Multiparty Communication.
APPROX-RANDOM 2008: 371-384 |
| 89 | EE | Matei David,
Toniann Pitassi:
Separating NOF communication complexity classes RP and NP
CoRR abs/0802.3860: (2008) |
| 88 | EE | Matei David,
Toniann Pitassi:
Separating NOF communication complexity classes RP and NP.
Electronic Colloquium on Computational Complexity (ECCC) 15(014): (2008) |
| 87 | EE | Michael Alekhnovich,
Mark Braverman,
Vitaly Feldman,
Adam R. Klivans,
Toniann Pitassi:
The complexity of properly learning simple concept classes.
J. Comput. Syst. Sci. 74(1): 16-34 (2008) |
| 86 | EE | Eric Allender,
Lisa Hellerstein,
Paul McCabe,
Toniann Pitassi,
Michael E. Saks:
Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table.
SIAM J. Comput. 38(1): 63-84 (2008) |
| 2007 |
|---|
| 85 | EE | Philipp Hertel,
Toniann Pitassi:
Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling.
FOCS 2007: 137-149 |
| 84 | EE | Konstantinos Georgiou,
Avner Magen,
Toniann Pitassi,
Iannis Tourlakis:
Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy.
FOCS 2007: 702-712 |
| 83 | EE | Paul Beame,
Matei David,
Toniann Pitassi,
Philipp Woelfel:
Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity.
ICALP 2007: 134-145 |
| 82 | EE | Philipp Hertel,
Toniann Pitassi:
Black-White Pebbling is PSPACE-Complete.
Electronic Colloquium on Computational Complexity (ECCC) 14(044): (2007) |
| 81 | EE | Philipp Hertel,
Toniann Pitassi:
An Exponential Time/Space Speedup For Resolution.
Electronic Colloquium on Computational Complexity (ECCC) 14(046): (2007) |
| 80 | EE | Nathan Segerlind,
Toniann Pitassi:
Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures.
Electronic Colloquium on Computational Complexity (ECCC) 14(107): (2007) |
| 79 | EE | Paul Beame,
Toniann Pitassi,
Nathan Segerlind:
Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow from Multiparty Communication Complexity.
SIAM J. Comput. 37(3): 845-869 (2007) |
| 78 | EE | Michael Alekhnovich,
Jan Johannsen,
Toniann Pitassi,
Alasdair Urquhart:
An Exponential Separation between Regular and General Resolution.
Theory of Computing 3(1): 81-102 (2007) |
| 2006 |
|---|
| 77 | EE | Shlomo Hoory,
Avner Magen,
Toniann Pitassi:
Monotone Circuits for the Majority Function.
APPROX-RANDOM 2006: 410-425 |
| 76 | EE | Eric Allender,
Lisa Hellerstein,
Paul McCabe,
Toniann Pitassi,
Michael E. Saks:
Minimizing DNF Formulas and AC0d Circuits Given a Truth Table.
IEEE Conference on Computational Complexity 2006: 237-251 |
| 75 | EE | Alexis Maciel,
Toniann Pitassi:
Conditional Lower Bound for a System of Constant-Depth Proofs with Modular Connectives.
LICS 2006: 189-200 |
| 74 | EE | Paul Beame,
Toniann Pitassi,
Nathan Segerlind,
Avi Wigderson:
A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness.
Computational Complexity 15(4): 391-432 (2006) |
| 73 | EE | Paul Beame,
Russell Impagliazzo,
Toniann Pitassi,
Nathan Segerlind:
Formula Caching in DPLL.
Electronic Colloquium on Computational Complexity (ECCC) 13(140): (2006) |
| 72 | EE | Konstantinos Georgiou,
Avner Magen,
Toniann Pitassi,
Iannis Tourlakis:
Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy.
Electronic Colloquium on Computational Complexity (ECCC) 13(152): (2006) |
| 71 | EE | Joshua Buresh-Oppenheim,
Nicola Galesi,
Shlomo Hoory,
Avner Magen,
Toniann Pitassi:
Rank Bounds and Integrality Gaps for Cutting Planes Procedures.
Theory of Computing 2(1): 65-90 (2006) |
| 2005 |
|---|
| 70 | EE | Paul Beame,
Toniann Pitassi,
Nathan Segerlind:
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity.
ICALP 2005: 1176-1188 |
| 69 | EE | Michael Alekhnovich,
Allan Borodin,
Joshua Buresh-Oppenheim,
Russell Impagliazzo,
Avner Magen,
Toniann Pitassi:
Toward a Model for Backtracking and Dynamic Programming.
IEEE Conference on Computational Complexity 2005: 308-322 |
| 68 | EE | Paul Beame,
Toniann Pitassi,
Nathan Segerlind,
Avi Wigderson:
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness.
IEEE Conference on Computational Complexity 2005: 52-66 |
| 67 | EE | Paul Beame,
Toniann Pitassi,
Nathan Segerlind:
Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity
Electronic Colloquium on Computational Complexity (ECCC)(053): (2005) |
| 66 | EE | Eric Allender,
Lisa Hellerstein,
Paul McCabe,
Toniann Pitassi,
Michael E. Saks:
Minimizing DNF Formulas and AC0 Circuits Given a Truth Table
Electronic Colloquium on Computational Complexity (ECCC)(126): (2005) |
| 2004 |
|---|
| 65 | EE | Michael Alekhnovich,
Mark Braverman,
Vitaly Feldman,
Adam R. Klivans,
Toniann Pitassi:
Learnability and Automatizability.
FOCS 2004: 621-630 |
| 64 | EE | Tian Sang,
Fahiem Bacchus,
Paul Beame,
Henry A. Kautz,
Toniann Pitassi:
Combining Component Caching and Clause Learning for Effective Model Counting.
SAT 2004 |
| 63 | EE | Toniann Pitassi,
Ran Raz:
Regular Resolution Lower Bounds For The Weak Pigeonhole Principle.
Combinatorica 24(3): 503-524 (2004) |
| 62 | EE | Maria Luisa Bonet,
Carlos Domingo,
Ricard Gavaldà,
Alexis Maciel,
Toniann Pitassi:
Non-Automatizability of Bounded-Depth Frege Proofs.
Computational Complexity 13(1-2): 47-68 (2004) |
| 61 | EE | Joshua Buresh-Oppenheim,
Paul Beame,
Toniann Pitassi,
Ran Raz,
Ashish Sabharwal:
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.
SIAM J. Comput. 34(2): 261-276 (2004) |
| 2003 |
|---|
| 60 | EE | Josh Buresh-Oppenheim,
Nicola Galesi,
Shlomo Hoory,
Avner Magen,
Toniann Pitassi:
Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua.
FOCS 2003: 318- |
| 59 | EE | Fahiem Bacchus,
Shannon Dalmao,
Toniann Pitassi:
Algorithms and Complexity Results for #SAT and Bayesian Inference.
FOCS 2003: 340-351 |
| 58 | EE | Paul Beame,
Russell Impagliazzo,
Toniann Pitassi,
Nathan Segerlind:
Memoization and DPLL: Formula Caching Proof Systems.
IEEE Conference on Computational Complexity 2003: 248- |
| 57 | EE | Josh Buresh-Oppenheim,
Toniann Pitassi:
The Complexity of Resolution Refinements.
LICS 2003: 138- |
| 56 | | Fahiem Bacchus,
Shannon Dalmao,
Toniann Pitassi:
Value Elimination: Bayesian Interence via Backtracking Search.
UAI 2003: 20-28 |
| 55 | EE | Fahiem Bacchus,
Shannon Dalmao,
Toniann Pitassi:
DPLL with Caching: A new algorithm for #SAT and Bayesian Inference
Electronic Colloquium on Computational Complexity (ECCC) 10(003): (2003) |
| 2002 |
|---|
| 54 | EE | Josh Buresh-Oppenheim,
Paul Beame,
Toniann Pitassi,
Ran Raz,
Ashish Sabharwal:
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles.
FOCS 2002: 583-592 |
| 53 | EE | Michael Alekhnovich,
Jan Johannsen,
Toniann Pitassi,
Alasdair Urquhart:
An exponential separation between regular and general resolution.
STOC 2002: 448-456 |
| 52 | EE | Josh Buresh-Oppenheim,
Matthew Clegg,
Russell Impagliazzo,
Toniann Pitassi:
Homogenization and the polynomial calculus.
Computational Complexity 11(3-4): 91-108 (2002) |
| 51 | EE | Josh Buresh-Oppenheim,
Paul Beame,
Toniann Pitassi,
Ran Raz,
Ashish Sabharwal:
Bounded-depth Frege lower bounds for weaker pigeonhole principles
Electronic Colloquium on Computational Complexity (ECCC)(023): (2002) |
| 50 | EE | Alexis Maciel,
Toniann Pitassi,
Alan R. Woods:
A New Proof of the Weak Pigeonhole Principle.
J. Comput. Syst. Sci. 64(4): 843-872 (2002) |
| 49 | EE | Paul Beame,
Richard M. Karp,
Toniann Pitassi,
Michael E. Saks:
The Efficiency of Resolution and Davis--Putnam Procedures.
SIAM J. Comput. 31(4): 1048-1075 (2002) |
| 2001 |
|---|
| 48 | EE | Toniann Pitassi,
Ran Raz:
Regular resolution lower bounds for the weak pigeonhole principle.
STOC 2001: 347-355 |
| 47 | EE | Noriko H. Arai,
Toniann Pitassi,
Alasdair Urquhart:
The complexity of analytic tableaux.
STOC 2001: 356-363 |
| 46 | | Paul Beame,
Toniann Pitassi:
Propositional Proof Complexity: Past, Present, and Future.
Current Trends in Theoretical Computer Science 2001: 42-70 |
| 45 | EE | Manindra Agrawal,
Eric Allender,
Russell Impagliazzo,
Toniann Pitassi,
Steven Rudich:
Reducing the complexity of reductions.
Computational Complexity 10(2): 117-138 (2001) |
| 44 | EE | Michael Alekhnovich,
Jan Johannsen,
Toniann Pitassi,
Alasdair Urquhart:
An Exponential Separation between Regular and General Resolution
Electronic Colloquium on Computational Complexity (ECCC) 8(056): (2001) |
| 43 | EE | Josh Buresh-Oppenheim,
David G. Mitchell,
Toniann Pitassi:
Linear and Negative Resolution are Weaker than Resolution
Electronic Colloquium on Computational Complexity (ECCC) 8(074): (2001) |
| 42 | | Michael L. Littman,
Stephen M. Majercik,
Toniann Pitassi:
Stochastic Boolean Satisfiability.
J. Autom. Reasoning 27(3): 251-296 (2001) |
| 41 | | Samuel R. Buss,
Dima Grigoriev,
Russell Impagliazzo,
Toniann Pitassi:
Linear Gaps between Degrees for the Polynomial Calculus Modulo Distinct Primes.
J. Comput. Syst. Sci. 62(2): 267-289 (2001) |
| 40 | | Michael Alekhnovich,
Samuel R. Buss,
Shlomo Moran,
Toniann Pitassi:
Minimum Propositional Proof Length Is NP-Hard to Linearly Approximate.
J. Symb. Log. 66(1): 171-191 (2001) |
| 2000 |
|---|
| 39 | EE | Josh Buresh-Oppenheim,
Matthew Clegg,
Russell Impagliazzo,
Toniann Pitassi:
Homogenization and the Polynominal Calculus.
ICALP 2000: 926-937 |
| 38 | | Richard S. Zemel,
Toniann Pitassi:
A Gradient-Based Boosting Algorithm for Regression Problems.
NIPS 2000: 696-702 |
| 37 | EE | Alexis Maciel,
Toniann Pitassi,
Alan R. Woods:
A new proof of the weak pigeonhole principle.
STOC 2000: 368-377 |
| 36 | | Maria Luisa Bonet,
Toniann Pitassi,
Ran Raz:
On Interpolation and Automatization for Frege Systems.
SIAM J. Comput. 29(6): 1939-1967 (2000) |
| 1999 |
|---|
| 35 | EE | Maria Luisa Bonet,
Carlos Domingo,
Ricard Gavaldà,
Alexis Maciel,
Toniann Pitassi:
Non-Automatizability of Bounded-Depth Frege Proofs.
IEEE Conference on Computational Complexity 1999: 15-23 |
| 34 | EE | Samuel R. Buss,
Dima Grigoriev,
Russell Impagliazzo,
Toniann Pitassi:
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract).
IEEE Conference on Computational Complexity 1999: 5 |
| 33 | EE | Samuel R. Buss,
Dima Grigoriev,
Russell Impagliazzo,
Toniann Pitassi:
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes.
STOC 1999: 547-556 |
| 1998 |
|---|
| 32 | EE | Michael Alekhnovich,
Samuel R. Buss,
Shlomo Moran,
Toniann Pitassi:
Minimum Propositional Proof Length is NP-Hard to Linearly Approximate.
MFCS 1998: 176-184 |
| 31 | EE | Paul Beame,
Richard M. Karp,
Toniann Pitassi,
Michael E. Saks:
On the Complexity of Unsatisfiability Proofs for Random k-CNF Formulas.
STOC 1998: 561-571 |
| 30 | | Paul Beame,
Toniann Pitassi:
Propositional Proof Complexity: Past, Present and Future.
Bulletin of the EATCS 65: 66-89 (1998) |
| 29 | EE | Paul Beame,
Russell Impagliazzo,
Toniann Pitassi:
Improved Depth Lower Bounds for Small Distance Connectivity.
Computational Complexity 7(4): 325-345 (1998) |
| 28 | EE | Paul Beame,
Toniann Pitassi:
Propositional Proof Complexity: Past, Present and Future
Electronic Colloquium on Computational Complexity (ECCC) 5(67): (1998) |
| 27 | | Paul Beame,
Stephen A. Cook,
Jeff Edmonds,
Russell Impagliazzo,
Toniann Pitassi:
The Relative Complexity of NP Search Problems.
J. Comput. Syst. Sci. 57(1): 3-19 (1998) |
| 26 | | Samuel R. Buss,
Toniann Pitassi:
Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle.
J. Comput. Syst. Sci. 57(2): 162-171 (1998) |
| 1997 |
|---|
| 25 | | Samuel R. Buss,
Toniann Pitassi:
Resolution and the Weak Pigeonhole Principle.
CSL 1997: 149-156 |
| 24 | EE | Maria Luisa Bonet,
Toniann Pitassi,
Ran Raz:
No Feasible Interpolation for TC0-Frege Proofs.
FOCS 1997: 254-263 |
| 23 | EE | Alexis Maciel,
Toniann Pitassi:
On ACC0[pk] Frege Proofs.
STOC 1997: 720-729 |
| 22 | EE | Manindra Agrawal,
Eric Allender,
Russell Impagliazzo,
Toniann Pitassi,
Steven Rudich:
Reducing the Complexity of Reductions.
STOC 1997: 730-738 |
| 21 | | Maria Luisa Bonet,
Toniann Pitassi,
Ran Raz:
Lower Bounds for Cutting Planes Proofs with Small Coefficients.
J. Symb. Log. 62(3): 708-728 (1997) |
| 1996 |
|---|
| 20 | | Toniann Pitassi:
Algebraic Propositional Proof Systems.
Descriptive Complexity and Finite Models 1996: 215-244 |
| 19 | | Paul Beame,
Toniann Pitassi:
Simplified and Improved Resolution Lower Bounds.
FOCS 1996: 274-282 |
| 18 | EE | Samuel R. Buss,
Toniann Pitassi:
Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle.
IEEE Conference on Computational Complexity 1996: 233-242 |
| 17 | | Paul Beame,
Toniann Pitassi:
An Exponential Separation Between the Parity Principle and the Pigeonhole Principle.
Ann. Pure Appl. Logic 80(3): 195-228 (1996) |
| 1995 |
|---|
| 16 | | Paul Beame,
Russell Impagliazzo,
Toniann Pitassi:
Improved Depth Lower Vounds for Small Distance Connectivity.
FOCS 1995: 692-701 |
| 15 | EE | Paul Beame,
Stephen A. Cook,
Jeff Edmonds,
Russell Impagliazzo,
Toniann Pitassi:
The relative complexity of NP search problems.
STOC 1995: 303-314 |
| 14 | EE | Maria Luisa Bonet,
Toniann Pitassi,
Ran Raz:
Lower bounds for cutting planes proofs with small coefficients.
STOC 1995: 575-584 |
| 13 | EE | Kazuo Iwama,
Toniann Pitassi:
Exponential Lower Bounds for the Tree-Like Hajós Calculus.
Inf. Process. Lett. 54(5): 289-294 (1995) |
| 12 | EE | Toniann Pitassi,
Alasdair Urquhart:
The Complexity of the Hajos Calculus.
SIAM J. Discrete Math. 8(3): 464-483 (1995) |
| 1994 |
|---|
| 11 | | Paul Beame,
Russell Impagliazzo,
Jan Krajícek,
Toniann Pitassi,
Pavel Pudlák:
Lower Bound on Hilbert's Nullstellensatz and propositional proofs
FOCS 1994: 794-806 |
| 10 | | Russell Impagliazzo,
Toniann Pitassi,
Alasdair Urquhart:
Upper and Lower Bounds for Tree-Like Cutting Planes Proofs
LICS 1994: 220-228 |
| 1993 |
|---|
| 9 | | Paul Beame,
Toniann Pitassi:
An Exponential Separation between the Matching Principle and the Pigeonhole Principle
LICS 1993: 308-319 |
| 8 | | Toniann Pitassi,
Paul Beame,
Russell Impagliazzo:
Exponential Lower Bounds for the Pigeonhole Principle.
Computational Complexity 3: 97-140 (1993) |
| 7 | | R. K. Shyamasundar,
K. T. Narayana,
Toniann Pitassi:
Semantics of Nondeterministic Asynchronous Broadcast Networks
Inf. Comput. 104(2): 215-252 (1993) |
| 1992 |
|---|
| 6 | | Toniann Pitassi,
Alasdair Urquhart:
The Complexity of the Hajós Calculus
FOCS 1992: 187-196 |
| 5 | | Paul Beame,
Russell Impagliazzo,
Jan Krajícek,
Toniann Pitassi,
Pavel Pudlák,
Alan R. Woods:
Exponential Lower Bounds for the Pigeonhole Principle
STOC 1992: 200-220 |
| 4 | | Stephen Bellantoni,
Toniann Pitassi,
Alasdair Urquhart:
Approximation and Small-Depth Frege Proofs.
SIAM J. Comput. 21(6): 1161-1179 (1992) |
| 1991 |
|---|
| 3 | | Stephen Bellantoni,
Toniann Pitassi,
Alasdair Urquhart:
Approximation and Small Depth Frege Proofs.
Structure in Complexity Theory Conference 1991: 367-390 |
| 1990 |
|---|
| 2 | | Stephen A. Cook,
Toniann Pitassi:
A Feasibly Constructive Lower Bound for Resolution Proofs.
Inf. Process. Lett. 34(2): 81-85 (1990) |
| 1987 |
|---|
| 1 | | R. K. Shyamasundar,
K. T. Narayana,
Toniann Pitassi:
Semantics for Nondeterministic Asynchronous Broadcast Networks.
ICALP 1987: 72-83 |
