The SCEAS System
| |||||||

## Search the dblp DataBase
Toniann Pitassi:
[Publications]
[Author Rank by year]
[Co-authors]
[Prefers]
[Cites]
[Cited by]
## Publications of Author- Shlomo Hoory, Avner Magen, Toniann Pitassi
**Monotone Circuits for the Majority Function.**[Citation Graph (0, 0)][DBLP] APPROX-RANDOM, 2006, pp:410-425 [Conf] - 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] - 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] - 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] - Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks
**Minimizing DNF Formulas and AC**[Citation Graph (0, 0)][DBLP]^{0}_{d}Circuits Given a Truth Table. IEEE Conference on Computational Complexity, 2006, pp:237-251 [Conf] - 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] - 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] - 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] - 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] - Samuel R. Buss, Toniann Pitassi
**Resolution and the Weak Pigeonhole Principle.**[Citation Graph (0, 0)][DBLP] CSL, 1997, pp:149-156 [Conf] - Toniann Pitassi
**Algebraic Propositional Proof Systems.**[Citation Graph (0, 0)][DBLP] Descriptive Complexity and Finite Models, 1996, pp:215-244 [Conf] - 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] - 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] - 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] - 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] - 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] - Paul Beame, Toniann Pitassi
**Simplified and Improved Resolution Lower Bounds.**[Citation Graph (0, 0)][DBLP] FOCS, 1996, pp:274-282 [Conf] - 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] - 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] - Toniann Pitassi, Alasdair Urquhart
**The Complexity of the Hajós Calculus**[Citation Graph (0, 0)][DBLP] FOCS, 1992, pp:187-196 [Conf] - 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] - 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] - 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] - 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] - Josh Buresh-Oppenheim, Toniann Pitassi
**The Complexity of Resolution Refinements.**[Citation Graph (0, 0)][DBLP] LICS, 2003, pp:138-0 [Conf] - 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] - 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] - 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] - Richard S. Zemel, Toniann Pitassi
**A Gradient-Based Boosting Algorithm for Regression Problems.**[Citation Graph (0, 0)][DBLP] NIPS, 2000, pp:696-702 [Conf] - 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] - 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] - 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] - Noriko H. Arai, Toniann Pitassi, Alasdair Urquhart
**The complexity of analytic tableaux.**[Citation Graph (0, 0)][DBLP] STOC, 2001, pp:356-363 [Conf] - 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] - 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] - Paul Beame, Richard M. Karp, Toniann Pitassi, Michael E. Saks
**On the Complexity of Unsatisfiability Proofs for Random**[Citation Graph (0, 0)][DBLP]*k*-CNF Formulas. STOC, 1998, pp:561-571 [Conf] - 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] - 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] - Alexis Maciel, Toniann Pitassi
**On ACC**[Citation Graph (0, 0)][DBLP]^{0}[*p*] Frege Proofs.^{k} STOC, 1997, pp:720-729 [Conf] - 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] - Toniann Pitassi, Ran Raz
**Regular resolution lower bounds for the weak pigeonhole principle.**[Citation Graph (0, 0)][DBLP] STOC, 2001, pp:347-355 [Conf] - Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi
**Value Elimination: Bayesian Interence via Backtracking Search.**[Citation Graph (0, 0)][DBLP] UAI, 2003, pp:20-28 [Conf] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] - 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] **Clause Learning Can Effectively P-Simulate General Propositional Resolution.**[Citation Graph (, )][DBLP]**Improved Separations between Nondeterministic and Randomized Multiparty Communication.**[Citation Graph (, )][DBLP]**Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling.**[Citation Graph (, )][DBLP]**Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy.**[Citation Graph (, )][DBLP]**Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures.**[Citation Graph (, )][DBLP]**Hardness amplification in proof complexity.**[Citation Graph (, )][DBLP]**Differential privacy under continual observation.**[Citation Graph (, )][DBLP]**Effectively Polynomial Simulations.**[Citation Graph (, )][DBLP]**Pan-Private Streaming Algorithms.**[Citation Graph (, )][DBLP]**Separating NOF communication complexity classes RP and NP**[Citation Graph (, )][DBLP]**Hardness Amplification in Proof Complexity**[Citation Graph (, )][DBLP]**Separating NOF communication complexity classes RP and NP.**[Citation Graph (, )][DBLP]**Black-White Pebbling is PSPACE-Complete.**[Citation Graph (, )][DBLP]**An Exponential Time/Space Speedup For Resolution.**[Citation Graph (, )][DBLP]**Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures.**[Citation Graph (, )][DBLP]**Formula Caching in DPLL.**[Citation Graph (, )][DBLP]**Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy.**[Citation Graph (, )][DBLP]
Search in 0.006secs, Finished in 0.010secs | |||||||

| |||||||

| |||||||

System created by asidirop@csd.auth.gr [http://users.auth.gr/~asidirop/] © 2002 for Data Engineering Laboratory, Department of Informatics, Aristotle University © 2002 |