The SCEAS System
Navigation Menu

Search the dblp DataBase

Title:
Author:

Toniann Pitassi: [Publications] [Author Rank by year] [Co-authors] [Prefers] [Cites] [Cited by]

Publications of Author

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

  76. Clause Learning Can Effectively P-Simulate General Propositional Resolution. [Citation Graph (, )][DBLP]


  77. Improved Separations between Nondeterministic and Randomized Multiparty Communication. [Citation Graph (, )][DBLP]


  78. Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling. [Citation Graph (, )][DBLP]


  79. Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy. [Citation Graph (, )][DBLP]


  80. Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures. [Citation Graph (, )][DBLP]


  81. Hardness amplification in proof complexity. [Citation Graph (, )][DBLP]


  82. Differential privacy under continual observation. [Citation Graph (, )][DBLP]


  83. Effectively Polynomial Simulations. [Citation Graph (, )][DBLP]


  84. Pan-Private Streaming Algorithms. [Citation Graph (, )][DBLP]


  85. Separating NOF communication complexity classes RP and NP [Citation Graph (, )][DBLP]


  86. Hardness Amplification in Proof Complexity [Citation Graph (, )][DBLP]


  87. Separating NOF communication complexity classes RP and NP. [Citation Graph (, )][DBLP]


  88. Black-White Pebbling is PSPACE-Complete. [Citation Graph (, )][DBLP]


  89. An Exponential Time/Space Speedup For Resolution. [Citation Graph (, )][DBLP]


  90. Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures. [Citation Graph (, )][DBLP]


  91. Formula Caching in DPLL. [Citation Graph (, )][DBLP]


  92. Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy. [Citation Graph (, )][DBLP]


Search in 0.118secs, Finished in 0.121secs
NOTICE1
System may not be available sometimes or not working properly, since it is still in development with continuous upgrades
NOTICE2
The rankings that are presented on this page should NOT be considered as formal since the citation info is incomplete in DBLP
 
System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002
for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002