default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDToniann Pitassi
Person information
- affiliation: Columbia University, NY, USA
- affiliation (former): University of Toronto, Canada
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2025
[c126]Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio:
Relative-Error Testing of Conjunctions and Decision Lists. ICALP 2025: 52:1-52:18- [c125]Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Aleksandar Nikolov, Toniann Pitassi, Morgan Shirley:
A Lower Bound on the Trace Norm of Boolean Matrices and Its Applications. ITCS 2025: 37:1-37:15 - [i90]Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio:
Relative-error testing of conjunctions and decision lists. CoRR abs/2504.08987 (2025) - [i89]Xi Chen, William Pires, Toniann Pitassi, Rocco A. Servedio:
Testing Juntas and Junta Subclasses with Relative Error. CoRR abs/2504.09312 (2025) - [i88]Yasaman Mahdaviyeh, James Lucas, Mengye Ren, Andreas S. Tolias, Richard S. Zemel, Toniann Pitassi:
Replay Can Provably Increase Forgetting. CoRR abs/2506.04377 (2025) - [i87]Oliver Korten, Toniann Pitassi, Russell Impagliazzo:
Stronger Cell Probe Lower Bounds via Local PRGs. Electron. Colloquium Comput. Complex. TR25 (2025) - 2024
- [j64]Susanna F. de Rezende
, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere:
KRW Composition Theorems via Lifting. Comput. Complex. 33(1): 4 (2024) - [j63]Thomas P. Zollo, Zhun Deng, Jake Snell, Toniann Pitassi, Richard S. Zemel:
Improving Predictor Reliability with Selective Recalibration. Trans. Mach. Learn. Res. 2024 (2024) - [c124]Oliver Korten, Toniann Pitassi:
Strong vs. Weak Range Avoidance and the Linear Ordering Principle. FOCS 2024: 1388-1407 - [c123]Kasper Green Larsen, Rasmus Pagh, Giuseppe Persiano, Toniann Pitassi, Kevin Yeo, Or Zamir:
Optimal Non-Adaptive Cell Probe Dictionaries and Hashing. ICALP 2024: 104:1-104:12 - [c122]Thomas P. Zollo, Todd Morrill, Zhun Deng, Jake Snell, Toniann Pitassi, Richard S. Zemel:
Prompt Risk Control: A Rigorous Framework for Responsible Deployment of Large Language Models. ICLR 2024 - [c121]Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, Adi Shraibman:
An Improved Protocol for ExactlyN with More Than 3 Players. ITCS 2024: 58:1-58:23 - [c120]Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere:
Black-Box PPP Is Not Turing-Closed. STOC 2024: 1405-1414 - [i86]Thomas P. Zollo, Zhun Deng, Jake C. Snell, Toniann Pitassi, Richard S. Zemel:
Improving Predictor Reliability with Selective Recalibration. CoRR abs/2410.05407 (2024) - [i85]Tsun-Ming Cheung, Hamed Hatami, Kaave Hosseini, Aleksandar Nikolov, Toniann Pitassi, Morgan Shirley:
A Lower Bound on the Trace Norm of Boolean Matrices and its Applications. Electron. Colloquium Comput. Complex. TR24 (2024) - [i84]Noah Fleming, Stefan Grosser, Toniann Pitassi, Robert Robere:
Black-Box PPP is not Turing-Closed. Electron. Colloquium Comput. Complex. TR24 (2024) - [i83]Oliver Korten, Toniann Pitassi:
Strong vs. Weak Range Avoidance and the Linear Ordering Principle. Electron. Colloquium Comput. Complex. TR24 (2024) - 2023
- [c119]Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, Adrian She:
On the Algebraic Proof Complexity of Tensor Isomorphism. CCC 2023: 4:1-4:40 - [c118]Russell Impagliazzo, Sasank Mouli, Toniann Pitassi:
Lower Bounds for Polynomial Calculus with Extension Variables over Finite Fields. CCC 2023: 7:1-7:24 - [c117]Jake Snell, Thomas P. Zollo, Zhun Deng, Toniann Pitassi, Richard S. Zemel:
Quantile Risk Control: A Flexible Framework for Bounding the Probability of High-Loss Predictions. ICLR 2023 - [c116]Toniann Pitassi, Morgan Shirley, Adi Shraibman:
The Strength of Equality Oracles in Communication. ITCS 2023: 89:1-89:19 - [c115]Zhun Deng, Thomas P. Zollo, Jake Snell, Toniann Pitassi, Richard S. Zemel:
Distribution-Free Statistical Dispersion Control for Societal Applications. NeurIPS 2023 - [c114]Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, Jessica Sorrell:
Stability Is Stable: Connections between Replicability, Privacy, and Adaptive Generalization. STOC 2023: 520-527 - [i82]Mark Bun, Marco Gaboardi, Max Hopkins, Russell Impagliazzo, Rex Lei, Toniann Pitassi, Satchit Sivakumar, Jessica Sorrell:
Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization. CoRR abs/2303.12921 (2023) - [i81]Nicola Galesi, Joshua A. Grochow, Toniann Pitassi, Adrian She:
On the algebraic proof complexity of Tensor Isomorphism. CoRR abs/2305.19320 (2023) - [i80]Kasper Green Larsen, Rasmus Pagh, Toniann Pitassi, Or Zamir:
Optimal Non-Adaptive Cell Probe Dictionaries and Hashing. CoRR abs/2308.16042 (2023) - [i79]Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, Adi Shraibman:
An improved protocol for ExactlyN with more than 3 players. CoRR abs/2309.06554 (2023) - [i78]Zhun Deng, Thomas P. Zollo, Jake C. Snell, Toniann Pitassi, Richard S. Zemel:
Distribution-Free Statistical Dispersion Control for Societal Applications. CoRR abs/2309.13786 (2023) - [i77]Thomas P. Zollo, Todd Morrill, Zhun Deng, Jake C. Snell, Toniann Pitassi, Richard S. Zemel:
Prompt Risk Control: A Rigorous Framework for Responsible Deployment of Large Language Models. CoRR abs/2311.13628 (2023) - [i76]Lianna Hambardzumyan, Toniann Pitassi, Suhail Sherif, Morgan Shirley, Adi Shraibman:
An improved protocol for ExactlyN with more than 3 players. Electron. Colloquium Comput. Complex. TR23 (2023) - 2022
- [j62]Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere:
Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes. J. ACM 69(3): 19:1-19:32 (2022) - [c113]Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi:
Secret Sharing, Slice Formulas, and Monotone Real Circuits. ITCS 2022: 8:1-8:23 - [c112]Noah Fleming, Toniann Pitassi, Robert Robere:
Extremely Deep Proofs. ITCS 2022: 70:1-70:23 - [c111]Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, Jiapeng Zhang:
Lifting with Sunflowers. ITCS 2022: 104:1-104:24 - [c110]Alexander Edmonds, Aleksandar Nikolov, Toniann Pitassi:
On Learning and Refutation in Noninteractive Local Differential Privacy. NeurIPS 2022 - [c109]Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell:
Reproducibility in learning. STOC 2022: 818-831 - [i75]Russell Impagliazzo, Rex Lei, Toniann Pitassi, Jessica Sorrell:
Reproducibility in Learning. CoRR abs/2201.08430 (2022) - [i74]Alexander Edmonds, Aleksandar Nikolov, Toniann Pitassi:
Learning versus Refutation in Noninteractive Local Differential Privacy. CoRR abs/2210.15439 (2022) - [i73]Jake C. Snell, Thomas P. Zollo, Zhun Deng, Toniann Pitassi, Richard S. Zemel:
Quantile Risk Control: A Flexible Framework for Bounding the Probability of High-Loss Predictions. CoRR abs/2212.13629 (2022) - [i72]Benny Applebaum, Amos Beimel, Oded Nir, Naty Peter, Toniann Pitassi:
Secret Sharing, Slice Formulas, and Monotone Real Circuits. Electron. Colloquium Comput. Complex. TR22 (2022) - [i71]Russell Impagliazzo, Sasank Mouli, Toniann Pitassi:
Lower bounds for Polynomial Calculus with extension variables over finite fields. Electron. Colloquium Comput. Complex. TR22 (2022) - [i70]Toniann Pitassi, Morgan Shirley, Adi Shraibman:
The Strength of Equality Oracles in Communication. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [j61]Toniann Pitassi, Morgan Shirley, Thomas Watson:
Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. Comput. Complex. 30(2): 10 (2021) - [j60]Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi:
Query-to-Communication Lifting Using Low-Discrepancy Gadgets. SIAM J. Comput. 50(1): 171-210 (2021) - [c108]Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson:
On the Power and Limitations of Branch and Cut. CCC 2021: 6:1-6:30 - [c107]Shafi Goldwasser, Russell Impagliazzo, Toniann Pitassi, Rahul Santhanam:
On the Pseudo-Deterministic Query Complexity of NP Search Problems. CCC 2021: 36:1-36:22 - [c106]Gal Vardi, Daniel Reichman, Toniann Pitassi, Ohad Shamir:
Size and Depth Separation in Approximating Benign Functions with Neural Networks. COLT 2021: 4195-4223 - [c105]Toniann Pitassi, Prasanna Ramakrishnan, Li-Yang Tan:
Tradeoffs for small-depth Frege proofs. FOCS 2021: 445-456 - [c104]Toniann Pitassi:
Algebraic Proof Systems (Invited Talk). ICALP 2021: 5:1-5:1 - [c103]James Lucas, Mengye Ren, Irene Raissa Kameni, Toniann Pitassi, Richard S. Zemel:
Theoretical bounds on estimation error for meta-learning. ICLR 2021 - [c102]Susanna F. de Rezende, Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov:
Automating algebraic proof systems is NP-hard. STOC 2021: 209-222 - [i69]Gal Vardi, Daniel Reichman, Toniann Pitassi, Ohad Shamir:
Size and Depth Separation in Approximating Natural Functions with Neural Networks. CoRR abs/2102.00314 (2021) - [i68]Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson:
On the Power and Limitations of Branch and Cut. CoRR abs/2102.05019 (2021) - [i67]Toniann Pitassi, Prasanna Ramakrishnan, Li-Yang Tan:
Tradeoffs for small-depth Frege proofs. CoRR abs/2111.07483 (2021) - [i66]Noah Fleming, Mika Göös, Russell Impagliazzo, Toniann Pitassi, Robert Robere, Li-Yang Tan, Avi Wigderson:
On the Power and Limitations of Branch and Cut. Electron. Colloquium Comput. Complex. TR21 (2021) - [i65]Noah Fleming, Toniann Pitassi:
Reflections on Proof Complexity and Counting Principles. Electron. Colloquium Comput. Complex. TR21 (2021) - [i64]Noah Fleming, Toniann Pitassi, Robert Robere:
Extremely Deep Proofs. Electron. Colloquium Comput. Complex. TR21 (2021) - 2020
- [j59]Mika Göös, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for BPP. SIAM J. Comput. 49(4) (2020) - [c101]Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Marc Vinyals:
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. FOCS 2020: 24-30 - [c100]Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere:
KRW Composition Theorems via Lifting. FOCS 2020: 43-49 - [c99]Toniann Pitassi, Morgan Shirley, Thomas Watson:
Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. ICALP 2020: 92:1-92:19 - [c98]Elliot Creager, David Madras, Toniann Pitassi, Richard S. Zemel:
Causal Modeling for Fairness In Dynamical Systems. ICML 2020: 2185-2195 - [c97]Russell Impagliazzo, Sasank Mouli, Toniann Pitassi:
The Surprising Power of Constant Depth Algebraic Proofs. LICS 2020: 591-603 - [c96]Chunxiao Li, Noah Fleming, Marc Vinyals, Toniann Pitassi, Vijay Ganesh:
Towards a Complexity-Theoretic Understanding of Restarts in SAT Solvers. SAT 2020: 233-249 - [c95]Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi:
Automating cutting planes is NP-hard. STOC 2020: 68-77 - [i63]Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Marc Vinyals:
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. CoRR abs/2001.02144 (2020) - [i62]Chunxiao Li, Noah Fleming, Marc Vinyals, Toniann Pitassi, Vijay Ganesh:
Towards a Complexity-theoretic Understanding of Restarts in SAT solvers. CoRR abs/2003.02323 (2020) - [i61]Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi:
Automating Cutting Planes is NP-Hard}. CoRR abs/2004.08037 (2020) - [i60]Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere:
KRW Composition Theorems via Lifting. CoRR abs/2007.02740 (2020) - [i59]James Lucas, Mengye Ren, Irene Kameni, Toniann Pitassi, Richard S. Zemel:
Theoretical bounds on estimation error for meta-learning. CoRR abs/2010.07140 (2020) - [i58]Mika Göös, Sajin Koroth, Ian Mertz, Toniann Pitassi:
Automating Cutting Planes is NP-Hard. Electron. Colloquium Comput. Complex. TR20 (2020) - [i57]Mika Göös, Jakob Nordström, Toniann Pitassi, Robert Robere, Dmitry Sokolov, Susanna F. de Rezende:
Automating Algebraic Proof Systems is NP-Hard. Electron. Colloquium Comput. Complex. TR20 (2020) - [i56]Ian Mertz, Toniann Pitassi:
Lifting: As Easy As 1, 2, 3. Electron. Colloquium Comput. Complex. TR20 (2020) - [i55]Susanna F. de Rezende, Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere:
KRW Composition Theorems via Lifting. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j58]Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for P NP. Comput. Complex. 28(1): 113-144 (2019) - [j57]Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson:
Correction to: Query-to-Communication Lifting for P NP. Comput. Complex. 28(3): 543-544 (2019) - [j56]Noah Fleming, Pravesh Kothari, Toniann Pitassi:
Semialgebraic Proofs and Efficient Algorithm Design. Found. Trends Theor. Comput. Sci. 14(1-2): 1-221 (2019) - [c94]David Madras, Elliot Creager, Toniann Pitassi, Richard S. Zemel:
Fairness through Causal Awareness: Learning Causal Latent-Variable Models for Biased Data. FAT 2019: 349-358 - [c93]Toniann Pitassi:
Progress in Lifting and Applications in Lower Bounds (Invited Talk). FSTTCS 2019: 4:1-4:1 - [c92]Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi:
Query-To-Communication Lifting for BPP Using Inner Product. ICALP 2019: 35:1-35:15 - [c91]Ian Mertz, Toniann Pitassi, Yuanhao Wei:
Short Proofs Are Hard to Find. ICALP 2019: 84:1-84:16 - [c90]Elliot Creager, David Madras, Jörn-Henrik Jacobsen, Marissa A. Weis, Kevin Swersky, Toniann Pitassi, Richard S. Zemel:
Flexibly Fair Representation Learning by Disentanglement. ICML 2019: 1436-1445 - [c89]Nati Linial, Toniann Pitassi, Adi Shraibman:
On the Communication Complexity of High-Dimensional Permutations. ITCS 2019: 54:1-54:20 - [i54]Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi:
Query-to-communication lifting for BPP using inner product. CoRR abs/1904.13056 (2019) - [i53]Elliot Creager, David Madras, Jörn-Henrik Jacobsen, Marissa A. Weis, Kevin Swersky, Toniann Pitassi, Richard S. Zemel:
Flexibly Fair Representation Learning by Disentanglement. CoRR abs/1906.02589 (2019) - [i52]Elliot Creager, David Madras, Toniann Pitassi, Richard S. Zemel:
Causal Modeling for Fairness in Dynamical Systems. CoRR abs/1909.09141 (2019) - [i51]Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, Toniann Pitassi:
Query-to-Communication Lifting Using Low-Discrepancy Gadgets. Electron. Colloquium Comput. Complex. TR19 (2019) - [i50]Noah Fleming, Pravesh Kothari, Toniann Pitassi:
Semialgebraic Proofs and Efficient Algorithm Design. Electron. Colloquium Comput. Complex. TR19 (2019) - [i49]Russell Impagliazzo, Sasank Mouli, Toniann Pitassi:
The Surprising Power of Constant Depth Algebraic Proofs. Electron. Colloquium Comput. Complex. TR19 (2019) - [i48]Or Meir, Jakob Nordström, Toniann Pitassi, Robert Robere, Susanna F. de Rezende:
Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity. Electron. Colloquium Comput. Complex. TR19 (2019) - [i47]Toniann Pitassi, Morgan Shirley, Thomas Watson:
Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j55]Mika Göös, Toniann Pitassi, Thomas Watson:
The Landscape of Communication Complexity Classes. Comput. Complex. 27(2): 245-304 (2018) - [j54]Joshua A. Grochow, Toniann Pitassi:
Circuit Complexity, Proof Complexity, and Polynomial Identity Testing: The Ideal Proof System. J. ACM 65(6): 37:1-37:59 (2018) - [j53]Mika Göös, Toniann Pitassi:
Communication Lower Bounds via Critical Block Sensitivity. SIAM J. Comput. 47(5): 1778-1806 (2018) - [j52]Mika Göös, Toniann Pitassi, Thomas Watson:
Deterministic Communication vs. Partition Number. SIAM J. Comput. 47(6): 2435-2450 (2018) - [j51]Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson:
Randomized Communication versus Partition Number. ACM Trans. Comput. Theory 10(1): 4:1-4:20 (2018) - [c88]Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi:
Hardness of Function Composition for Semantic Read once Branching Programs. CCC 2018: 15:1-15:22 - [c87]David Madras, Toniann Pitassi, Richard S. Zemel:
Predict Responsibly: Increasing Fairness by Learning to Defer. ICLR (Workshop) 2018 - [c86]David Madras, Elliot Creager, Toniann Pitassi, Richard S. Zemel:
Learning Adversarially Fair and Transferable Representations. ICML 2018: 3381-3390 - [c85]Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere:
Stabbing Planes. ITCS 2018: 10:1-10:20 - [c84]David Madras, Toniann Pitassi, Richard S. Zemel:
Predict Responsibly: Improving Fairness and Accuracy by Learning to Defer. NeurIPS 2018: 6150-6160 - [c83]Toniann Pitassi, Robert Robere:
Lifting nullstellensatz to monotone span programs over any field. STOC 2018: 1207-1219 - [i46]David Madras, Elliot Creager, Toniann Pitassi, Richard S. Zemel:
Learning Adversarially Fair and Transferable Representations. CoRR abs/1802.06309 (2018) - [i45]David Madras, Elliot Creager, Toniann Pitassi, Richard S. Zemel:
Fairness Through Causal Awareness: Learning Latent-Variable Models for Biased Data. CoRR abs/1809.02519 (2018) - 2017
- [j50]Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth:
Guilt-free data reuse. Commun. ACM 60(4): 86-93 (2017) - [c82]Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for P^NP. CCC 2017: 12:1-12:16 - [c81]Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere:
Random Θ(log n)-CNFs Are Hard for Cutting Planes. FOCS 2017: 109-120 - [c80]Mika Göös, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for BPP. FOCS 2017: 132-143 - [c79]Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson:
Randomized Communication vs. Partition Number. ICALP 2017: 52:1-52:15 - [c78]Toniann Pitassi, Robert Robere:
Strongly exponential lower bounds for monotone computation. STOC 2017: 1246-1255 - [i44]Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere:
Random CNFs are Hard for Cutting Planes. CoRR abs/1703.02469 (2017) - [i43]Mika Göös, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for BPP. CoRR abs/1703.07666 (2017) - [i42]Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere:
Stabbing Planes. CoRR abs/1710.03219 (2017) - [i41]David Madras, Toniann Pitassi, Richard S. Zemel:
Predict Responsibly: Increasing Fairness by Learning To Defer. CoRR abs/1711.06664 (2017) - [i40]Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere:
Stabbing Planes. Electron. Colloquium Comput. Complex. TR17 (2017) - [i39]Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere:
Random CNFs are Hard for Cutting Planes. Electron. Colloquium Comput. Complex. TR17 (2017) - [i38]Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for P^NP. Electron. Colloquium Comput. Complex. TR17 (2017) - [i37]Mika Göös, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for BPP. Electron. Colloquium Comput. Complex. TR17 (2017) - [i36]Toniann Pitassi, Robert Robere:
Lifting Nullstellensatz to Monotone Span Programs over Any Field. Electron. Colloquium Comput. Complex. TR17 (2017) - 2016
- [j49]Mika Göös, Toniann Pitassi, Thomas Watson:
Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. Algorithmica 76(3): 684-719 (2016) - [j48]Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi:
Upper and Lower Bounds on the Power of Advice. SIAM J. Comput. 45(4): 1412-1432 (2016) - [j47]Toniann Pitassi, Iddo Tzameret:
Algebraic proof complexity: progress, frontiers and challenges. ACM SIGLOG News 3(3): 21-43 (2016) - [c77]Robert Robere, Toniann Pitassi, Benjamin Rossman, Stephen A. Cook:
Exponential Lower Bounds for Monotone Span Programs. FOCS 2016: 406-415 - [c76]Stephen A. Cook, Jeff Edmonds, Venkatesh Medabalimi, Toniann Pitassi:
Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs. ICALP 2016: 36:1-36:13 - [c75]Mika Göös, Toniann Pitassi, Thomas Watson:
The Landscape of Communication Complexity Classes. ICALP 2016: 86:1-86:15 - [c74]Toniann Pitassi, Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan:
Poly-logarithmic Frege depth lower bounds via an expander switching lemma. STOC 2016: 644-657 - [i35]Toniann Pitassi, Iddo Tzameret:
Algebraic Proof Complexity: Progress, Frontiers and Challenges. CoRR abs/1607.00443 (2016) - [i34]Stephen A. Cook, Toniann Pitassi, Robert Robere, Benjamin Rossman:
Exponential Lower Bounds for Monotone Span Programs. Electron. Colloquium Comput. Complex. TR16 (2016) - [i33]Toniann Pitassi, Robert Robere:
Strongly Exponential Lower Bounds for Monotone Computation. Electron. Colloquium Comput. Complex. TR16 (2016) - [i32]Toniann Pitassi, Iddo Tzameret:
Algebraic Proof Complexity: Progress, Frontiers and Challenges. Electron. Colloquium Comput. Complex. TR16 (2016) - 2015
- [j46]Yuval Filmus, Toniann Pitassi, Rahul Santhanam:
Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds. ACM Trans. Comput. Theory 7(2): 5:1-5:16 (2015) - [c73]Mika Göös, Toniann Pitassi, Thomas Watson:
Deterministic Communication vs. Partition Number. FOCS 2015: 1077-1088 - [c72]Yu (Ledell) Wu, Per Austrin, Toniann Pitassi, David Liu:
Inapproximability of Treewidth and Related Problems (Extended Abstract). IJCAI 2015: 4222-4228 - [c71]Mika Göös, Toniann Pitassi, Thomas Watson:
Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. ITCS 2015: 113-122 - [c70]Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth:
Generalization in Adaptive Data Analysis and Holdout Reuse. NIPS 2015: 2350-2358 - [c69]Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Leon Roth:
Preserving Statistical Validity in Adaptive Data Analysis. STOC 2015: 117-126 - [i31]Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth:
Generalization in Adaptive Data Analysis and Holdout Reuse. CoRR abs/1506.02629 (2015) - [i30]Mika Göös, T. S. Jayram, Toniann Pitassi, Thomas Watson:
Randomized Communication vs. Partition Number. Electron. Colloquium Comput. Complex. TR15 (2015) - [i29]Mika Göös, Toniann Pitassi, Thomas Watson:
The Landscape of Communication Complexity Classes. Electron. Colloquium Comput. Complex. TR15 (2015) - [i28]Mika Göös, Toniann Pitassi, Thomas Watson:
Deterministic Communication vs. Partition Number. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j45]Alexis Maciel, Phuong Nguyen, Toniann Pitassi:
Lifting lower bounds for tree-like proofs. Comput. Complex. 23(4): 585-636 (2014) - [j44]Yu (Ledell) Wu, Per Austrin, Toniann Pitassi, David Liu:
Inapproximability of Treewidth and Related Problems. J. Artif. Intell. Res. 49: 569-600 (2014) - [j43]Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi:
The Hardness of Being Private. ACM Trans. Comput. Theory 6(1): 1:1-1:24 (2014) - [c68]Joshua A. Grochow, Toniann Pitassi:
Circuit Complexity, Proof Complexity, and Polynomial Identity Testing. FOCS 2014: 110-119 - [c67]Mika Göös, Toniann Pitassi:
Communication lower bounds via critical block sensitivity. STOC 2014: 847-856 - [i27]Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi:
Solving #SAT and Bayesian Inference with Backtracking Search. CoRR abs/1401.3458 (2014) - [i26]Joshua A. Grochow, Toniann Pitassi:
Circuit complexity, proof complexity, and polynomial identity testing. CoRR abs/1404.3820 (2014) - [i25]Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, Aaron Roth:
Preserving Statistical Validity in Adaptive Data Analysis. CoRR abs/1411.2664 (2014) - [i24]Mika Göös, Toniann Pitassi, Thomas Watson:
Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. Electron. Colloquium Comput. Complex. TR14 (2014) - [i23]Joshua A. Grochow, Toniann Pitassi:
Circuit complexity, proof complexity, and polynomial identity testing. Electron. Colloquium Comput. Complex. TR14 (2014) - 2013
- [c66]Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook:
Average Case Lower Bounds for Monotone Switching Networks. FOCS 2013: 598-607 - [c65]Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, Vinod Vaikuntanathan:
A Tight Bound for Set Disjointness in the Message-Passing Model. FOCS 2013: 668-677 - [c64]Richard S. Zemel, Yu Wu, Kevin Swersky, Toniann Pitassi, Cynthia Dwork:
Learning Fair Representations. ICML (3) 2013: 325-333 - [c63]James Martens, Arkadev Chattopadhyay, Toniann Pitassi, Richard S. Zemel:
On the Expressive Power of Restricted Boltzmann Machines. NIPS 2013: 2877-2885 - [i22]Mark Braverman, Faith Ellen, Rotem Oshman, Toniann Pitassi, Vinod Vaikuntanathan:
Tight Bounds for Set Disjointness in the Message Passing Model. CoRR abs/1305.4696 (2013) - [i21]Mika Göös, Toniann Pitassi:
Communication Lower Bounds via Critical Block Sensitivity. CoRR abs/1311.2355 (2013) - [i20]Yuval Filmus, Toniann Pitassi, Robert Robere, Stephen A. Cook:
Average Case Lower Bounds for Monotone Switching Networks. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j42]Toniann Pitassi, Nathan Segerlind:
Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász-Schrijver Procedures. SIAM J. Comput. 41(1): 128-159 (2012) - [c62]Per Austrin, Toniann Pitassi, Yu Wu:
Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems. APPROX-RANDOM 2012: 13-24 - [c61]Toniann Pitassi:
Communication Complexity and Information Complexity: Foundations and New Directions. CCC 2012: 136 - [c60]Anil Ada, Arkadev Chattopadhyay, Stephen A. Cook, Lila Fontes, Michal Koucký, Toniann Pitassi:
The Hardness of Being Private. CCC 2012: 192-202 - [c59]Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, Richard S. Zemel:
Fairness through awareness. ITCS 2012: 214-226 - [c58]Arkadev Chattopadhyay, Jeff Edmonds, Faith Ellen, Toniann Pitassi:
A little advice can be very helpful. SODA 2012: 615-625 - [e1]Howard J. Karloff, Toniann Pitassi:
Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012. ACM 2012, ISBN 978-1-4503-1245-5 [contents] - [i19]Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi:
Value Elimination: Bayesian Inference via Backtracking Search. CoRR abs/1212.2452 (2012) - 2011
- [j41]Allan Borodin, Toniann Pitassi, Alexander A. Razborov:
Special Issue In Memory of Misha Alekhnovich. Foreword. Comput. Complex. 20(4): 579-590 (2011) - [j40]Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi:
Toward a Model for Backtracking and Dynamic Programming. Comput. Complex. 20(4): 679-740 (2011) - [c57]Lei Huang, Toniann Pitassi:
Automatizability and Simple Stochastic Games. ICALP (1) 2011: 605-617 - [c56]Yuval Filmus, Toniann Pitassi, Rahul Santhanam:
Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds. ICALP (1) 2011: 618-629 - [c55]Toniann Pitassi:
Propositional Proof Complexity: A Survey on the State of the Art, Including Some Recent Results. LICS 2011: 119 - [i18]Cynthia Dwork, Moritz Hardt, Toniann Pitassi, Omer Reingold, Richard S. Zemel:
Fairness Through Awareness. CoRR abs/1104.3913 (2011) - [i17]Per Austrin, Toniann Pitassi, Yu Wu:
Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems. CoRR abs/1109.4910 (2011) - [i16]Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil P. Vadhan:
The Limits of Two-Party Differential Privacy. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j39]Philipp Hertel, Toniann Pitassi:
The PSPACE-Completeness of Black-White Pebbling. SIAM J. Comput. 39(6): 2622-2682 (2010) - [j38]Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis:
Integrality Gaps of 2-o(1) for Vertex Cover SDPs in the Lov[a-acute]sz--Schrijver Hierarchy. SIAM J. Comput. 39(8): 3553-3570 (2010) - [j37]Arkadev Chattopadhyay, Toniann Pitassi:
The story of set disjointness. SIGACT News 41(3): 59-85 (2010) - [j36]Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel:
Separating Deterministic from Randomized Multiparty Communication Complexity. Theory Comput. 6(1): 201-225 (2010) - [j35]Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind:
Formula Caching in DPLL. ACM Trans. Comput. Theory 1(3): 9:1-9:33 (2010) - [c54]Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar, Salil P. Vadhan:
The Limits of Two-Party Differential Privacy. FOCS 2010: 81-90 - [c53]Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum, Sergey Yekhanin:
Pan-Private Streaming Algorithms. ICS 2010: 66-80 - [c52]Toniann Pitassi, Rahul Santhanam:
Effectively Polynomial Simulations. ICS 2010: 370-382 - [c51]Paul Beame, Trinh Huynh, Toniann Pitassi:
Hardness amplification in proof complexity. STOC 2010: 87-96 - [c50]Cynthia Dwork, Moni Naor, Toniann Pitassi, Guy N. Rothblum:
Differential privacy under continual observation. STOC 2010: 715-724
2000 – 2009
- 2009
- [j34]Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi:
Solving #SAT and Bayesian Inference with Backtracking Search. J. Artif. Intell. Res. 34: 391-442 (2009) - [j33]Matei David, Toniann Pitassi, Emanuele Viola:
Improved Separations between Nondeterministic and Randomized Multiparty Communication. ACM Trans. Comput. Theory 1(2): 5:1-5:20 (2009) - [c49]Toniann Pitassi, Nathan Segerlind:
Exponential lower bounds and integrality gaps for tree-like Lovász-Schrijver procedures. SODA 2009: 355-364 - [i15]Paul Beame, Trinh Huynh, Toniann Pitassi:
Hardness Amplification in Proof Complexity. CoRR abs/0912.0568 (2009) - 2008
- [j32]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) - [j31]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) - [c48]Philipp Hertel, Fahiem Bacchus, Toniann Pitassi, Allen Van Gelder:
Clause Learning Can Effectively P-Simulate General Propositional Resolution. AAAI 2008: 283-290 - [c47]Matei David, Toniann Pitassi, Emanuele Viola:
Improved Separations between Nondeterministic and Randomized Multiparty Communication. APPROX-RANDOM 2008: 371-384 - [i14]Matei David, Toniann Pitassi:
Separating NOF communication complexity classes RP and NP. CoRR abs/0802.3860 (2008) - [i13]Matei David, Toniann Pitassi:
Separating NOF communication complexity classes RP and NP. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j30]Joshua Buresh-Oppenheim, Toniann Pitassi:
The complexity of resolution refinements. J. Symb. Log. 72(4): 1336-1352 (2007) - [j29]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) - [j28]Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart:
An Exponential Separation between Regular and General Resolution. Theory Comput. 3(1): 81-102 (2007) - [c46]Philipp Hertel, Toniann Pitassi:
Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling. FOCS 2007: 137-149 - [c45]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 - [c44]Paul Beame, Matei David, Toniann Pitassi, Philipp Woelfel:
Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity. ICALP 2007: 134-145 - [i12]Philipp Hertel, Toniann Pitassi:
Black-White Pebbling is PSPACE-Complete. Electron. Colloquium Comput. Complex. TR07 (2007) - [i11]Philipp Hertel, Toniann Pitassi:
An Exponential Time/Space Speedup For Resolution. Electron. Colloquium Comput. Complex. TR07 (2007) - [i10]Nathan Segerlind, Toniann Pitassi:
Exponential lower bounds and integrality gaps for tree-like Lovasz-Schrijver procedures. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [j27]Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson:
A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness. Comput. Complex. 15(4): 391-432 (2006) - [j26]Noriko H. Arai, Toniann Pitassi, Alasdair Urquhart:
The complexity of analytic tableaux. J. Symb. Log. 71(3): 777-790 (2006) - [j25]Joshua Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi:
Rank Bounds and Integrality Gaps for Cutting Planes Procedures. Theory Comput. 2(4): 65-90 (2006) - [c43]Shlomo Hoory, Avner Magen, Toniann Pitassi:
Monotone Circuits for the Majority Function. APPROX-RANDOM 2006: 410-425 - [c42]Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
Minimizing DNF Formulas and AC0d Circuits Given a Truth Table. CCC 2006: 237-251 - [c41]Alexis Maciel, Toniann Pitassi:
Conditional Lower Bound for a System of Constant-Depth Proofs with Modular Connectives. LICS 2006: 189-200 - [i9]Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind:
Formula Caching in DPLL. Electron. Colloquium Comput. Complex. TR06 (2006) - [i8]Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis:
Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [c40]Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson:
A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness. CCC 2005: 52-66 - [c39]Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi:
Toward a Model for Backtracking and Dynamic Programming. CCC 2005: 308-322 - [c38]Paul Beame, Toniann Pitassi, Nathan Segerlind:
Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity. ICALP 2005: 1176-1188 - [i7]Paul Beame, Toniann Pitassi, Nathan Segerlind:
Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty communication complexity. Electron. Colloquium Comput. Complex. TR05 (2005) - [i6]Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks:
Minimizing DNF Formulas and AC0 Circuits Given a Truth Table. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j24]Maria Luisa Bonet, Carlos Domingo, Ricard Gavaldà, Alexis Maciel, Toniann Pitassi:
Non-Automatizability of Bounded-Depth Frege Proofs. Comput. Complex. 13(1-2): 47-68 (2004) - [j23]Toniann Pitassi, Ran Raz:
Regular Resolution Lower Bounds For The Weak Pigeonhole Principle. Comb. 24(3): 503-524 (2004) - [j22]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) - [c37]Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi:
Learnability and Automatizability. FOCS 2004: 621-630 - [c36]Tian Sang, Fahiem Bacchus, Paul Beame, Henry A. Kautz, Toniann Pitassi:
Combining Component Caching and Clause Learning for Effective Model Counting. SAT 2004 - 2003
- [c35]Paul Beame, Russell Impagliazzo, Toniann Pitassi, Nathan Segerlind:
Memoization and DPLL: Formula Caching Proof Systems. CCC 2003: 248- - [c34]Josh Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi:
Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua. FOCS 2003: 318-327 - [c33]Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi:
Algorithms and Complexity Results for #SAT and Bayesian Inference. FOCS 2003: 340-351 - [c32]Josh Buresh-Oppenheim, Toniann Pitassi:
The Complexity of Resolution Refinements. LICS 2003: 138- - [c31]Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi:
Value Elimination: Bayesian Interence via Backtracking Search. UAI 2003: 20-28 - [i5]Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi:
DPLL with Caching: A new algorithm for #SAT and Bayesian Inference. Electron. Colloquium Comput. Complex. TR03 (2003) - 2002
- [j21]Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi:
Homogenization and the polynomial calculus. Comput. Complex. 11(3-4): 91-108 (2002) - [j20]Alexis Maciel, Toniann Pitassi, Alan R. Woods:
A New Proof of the Weak Pigeonhole Principle. J. Comput. Syst. Sci. 64(4): 843-872 (2002) - [j19]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) - [c30]Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal:
Bounded-Depth Frege Lower Bounds for Weaker Pigeonhole Principles. FOCS 2002: 583-592 - [c29]Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart:
An exponential separation between regular and general resolution. STOC 2002: 448-456 - [i4]Josh Buresh-Oppenheim, Paul Beame, Toniann Pitassi, Ran Raz, Ashish Sabharwal:
Bounded-depth Frege lower bounds for weaker pigeonhole principles. Electron. Colloquium Comput. Complex. TR02 (2002) - 2001
- [j18]Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich:
Reducing the complexity of reductions. Comput. Complex. 10(2): 117-138 (2001) - [j17]Michael L. Littman, Stephen M. Majercik, Toniann Pitassi:
Stochastic Boolean Satisfiability. J. Autom. Reason. 27(3): 251-296 (2001) - [j16]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) - [j15]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) - [c28]Toniann Pitassi, Ran Raz:
Regular resolution lower bounds for the weak pigeonhole principle. STOC 2001: 347-355 - [c27]Noriko H. Arai, Toniann Pitassi, Alasdair Urquhart:
The complexity of analytic tableaux. STOC 2001: 356-363 - [p1]Paul Beame, Toniann Pitassi:
Propositional Proof Complexity: Past, Present, and Future. Current Trends in Theoretical Computer Science 2001: 42-70 - [i3]Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart:
An Exponential Separation between Regular and General Resolution. Electron. Colloquium Comput. Complex. TR01 (2001) - [i2]Josh Buresh-Oppenheim, David G. Mitchell, Toniann Pitassi:
Linear and Negative Resolution are Weaker than Resolution. Electron. Colloquium Comput. Complex. TR01 (2001) - 2000
- [j14]Maria Luisa Bonet, Toniann Pitassi, Ran Raz:
On Interpolation and Automatization for Frege Systems. SIAM J. Comput. 29(6): 1939-1967 (2000) - [c26]Josh Buresh-Oppenheim, Matthew Clegg, Russell Impagliazzo, Toniann Pitassi:
Homogenization and the Polynominal Calculus. ICALP 2000: 926-937 - [c25]Richard S. Zemel, Toniann Pitassi:
A Gradient-Based Boosting Algorithm for Regression Problems. NIPS 2000: 696-702 - [c24]Alexis Maciel, Toniann Pitassi, Alan R. Woods:
A new proof of the weak pigeonhole principle. STOC 2000: 368-377
1990 – 1999
- 1999
- [c23]Samuel R. Buss, Dima Grigoriev, Russell Impagliazzo, Toniann Pitassi:
Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes (Abstract). CCC 1999: 5 - [c22]Maria Luisa Bonet, Carlos Domingo, Ricard Gavaldà, Alexis Maciel, Toniann Pitassi:
Non-Automatizability of Bounded-Depth Frege Proofs. CCC 1999: 15-23 - [c21]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
- [j13]Paul Beame, Russell Impagliazzo, Toniann Pitassi:
Improved Depth Lower Bounds for Small Distance Connectivity. Comput. Complex. 7(4): 325-345 (1998) - [j12]Paul Beame, Toniann Pitassi:
Propositional Proof Complexity: Past, Present and Future. Bull. EATCS 65: 66-89 (1998) - [j11]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) - [j10]Samuel R. Buss, Toniann Pitassi:
Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle. J. Comput. Syst. Sci. 57(2): 162-171 (1998) - [c20]Michael Alekhnovich, Samuel R. Buss, Shlomo Moran, Toniann Pitassi:
Minimum Propositional Proof Length is NP-Hard to Linearly Approximate. MFCS 1998: 176-184 - [c19]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 - [i1]Paul Beame, Toniann Pitassi:
Propositional Proof Complexity: Past, Present and Future. Electron. Colloquium Comput. Complex. TR98 (1998) - 1997
- [j9]Maria Luisa Bonet, Toniann Pitassi, Ran Raz:
Lower Bounds for Cutting Planes Proofs with Small Coefficients. J. Symb. Log. 62(3): 708-728 (1997) - [c18]Samuel R. Buss, Toniann Pitassi:
Resolution and the Weak Pigeonhole Principle. CSL 1997: 149-156 - [c17]Maria Luisa Bonet, Toniann Pitassi, Ran Raz:
No Feasible Interpolation for TC0-Frege Proofs. FOCS 1997: 254-263 - [c16]Alexis Maciel, Toniann Pitassi:
On ACC0[pk] Frege Proofs. STOC 1997: 720-729 - [c15]Manindra Agrawal, Eric Allender, Russell Impagliazzo, Toniann Pitassi, Steven Rudich:
Reducing the Complexity of Reductions. STOC 1997: 730-738 - 1996
- [j8]Paul Beame, Toniann Pitassi:
An Exponential Separation Between the Parity Principle and the Pigeonhole Principle. Ann. Pure Appl. Log. 80(3): 195-228 (1996) - [j7]Eric Allender, Joan Feigenbaum, Judy Goldsmith, Toniann Pitassi, Steven Rudich:
The future of computational complexity theory: part II. SIGACT News 27(4): 3-7 (1996) - [c14]Samuel R. Buss, Toniann Pitassi:
Good Degree Bounds on Nullstellensatz Refutations of the Induction Principle. CCC 1996: 233-242 - [c13]Alexis Maciel, Toniann Pitassi:
Towards lower bounds for bounded-depth Frege proofs with modular connectives. Proof Complexity and Feasible Arithmetics 1996: 195-227 - [c12]Toniann Pitassi:
Algebraic Propositional Proof Systems. Descriptive Complexity and Finite Models 1996: 215-244 - [c11]Paul Beame, Toniann Pitassi:
Simplified and Improved Resolution Lower Bounds. FOCS 1996: 274-282 - 1995
- [j6]Kazuo Iwama, Toniann Pitassi:
Exponential Lower Bounds for the Tree-Like Hajós Calculus. Inf. Process. Lett. 54(5): 289-294 (1995) - [j5]Toniann Pitassi, Alasdair Urquhart:
The Complexity of the Hajos Calculus. SIAM J. Discret. Math. 8(3): 464-483 (1995) - [c10]Paul Beame, Russell Impagliazzo, Toniann Pitassi:
Improved Depth Lower Vounds for Small Distance Connectivity. FOCS 1995: 692-701 - [c9]Paul Beame, Stephen A. Cook, Jeff Edmonds, Russell Impagliazzo, Toniann Pitassi:
The relative complexity of NP search problems. STOC 1995: 303-314 - [c8]Maria Luisa Bonet, Toniann Pitassi, Ran Raz:
Lower bounds for cutting planes proofs with small coefficients. STOC 1995: 575-584 - 1994
- [c7]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 - [c6]Russell Impagliazzo, Toniann Pitassi, Alasdair Urquhart:
Upper and Lower Bounds for Tree-Like Cutting Planes Proofs. LICS 1994: 220-228 - 1993
- [j4]Toniann Pitassi, Paul Beame, Russell Impagliazzo:
Exponential Lower Bounds for the Pigeonhole Principle. Comput. Complex. 3: 97-140 (1993) - [j3]R. K. Shyamasundar, K. T. Narayana, Toniann Pitassi:
Semantics of Nondeterministic Asynchronous Broadcast Networks. Inf. Comput. 104(2): 215-252 (1993) - [c5]Paul Beame, Toniann Pitassi:
An Exponential Separation between the Matching Principle and the Pigeonhole Principle. LICS 1993: 308-319 - 1992
- [b1]Toniann Pitassi:
The power of weak formal systems. University of Toronto, Canada, 1992 - [j2]Stephen J. Bellantoni, Toniann Pitassi, Alasdair Urquhart:
Approximation and Small-Depth Frege Proofs. SIAM J. Comput. 21(6): 1161-1179 (1992) - [c4]Toniann Pitassi, Alasdair Urquhart:
The Complexity of the Hajós Calculus. FOCS 1992: 187-196 - [c3]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 - 1991
- [c2]Stephen J. Bellantoni, Toniann Pitassi, Alasdair Urquhart:
Approximation and Small Depth Frege Proofs. SCT 1991: 367-390 - 1990
- [j1]Stephen A. Cook, Toniann Pitassi:
A Feasibly Constructive Lower Bound for Resolution Proofs. Inf. Process. Lett. 34(2): 81-85 (1990)
1980 – 1989
- 1987
- [c1]R. K. Shyamasundar, K. T. Narayana, Toniann Pitassi:
Semantics for Nondeterministic Asynchronous Broadcast Networks. ICALP 1987: 72-83
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from 
to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the 
of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from 
, 
, and 
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from 
.
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2025-07-07 22:17 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by:
