Toniann Pitassi
#52,601
Most Influential Person Now
Mathematician, Computer scientist
Toniann Pitassi's AcademicInfluence.com Rankings
Toniann Pitassimathematics Degrees
Mathematics
#4140
World Rank
#5947
Historical Rank
Measure Theory
#2445
World Rank
#2930
Historical Rank
Download Badge
Computer Science Mathematics
Why Is Toniann Pitassi Influential?
(Suggest an Edit or Addition)According to Wikipedia, Toniann Pitassi is a Canadian-American mathematician and computer scientist specializing in computational complexity theory. She is currently Jeffrey L. and Brenda Bleustein Professor of Engineering at Columbia University and was Bell Research Chair at the University of Toronto.
Toniann Pitassi's Published Works
Number of citations in a given year to any of this author's works
Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author
Published Works
- Fairness through awareness (2011) (2521)
- Learning Fair Representations (2013) (1342)
- Differential privacy under continual observation (2010) (609)
- Learning Adversarially Fair and Transferable Representations (2018) (484)
- Preserving Statistical Validity in Adaptive Data Analysis (2014) (333)
- The reusable holdout: Preserving validity in adaptive data analysis (2015) (300)
- Exponential lower bounds for the pigeonhole principle (1992) (252)
- Combining Component Caching and Clause Learning for Effective Model Counting (2004) (242)
- Lower bounds on Hilbert's Nullstellensatz and propositional proofs (1994) (215)
- Flexibly Fair Representation Learning by Disentanglement (2019) (212)
- Generalization in Adaptive Data Analysis and Holdout Reuse (2015) (198)
- Simplified and improved resolution lower bounds (1996) (196)
- Lower bounds for cutting planes proofs with small coefficients (1995) (190)
- Propositional Proof Complexity: Past, Present and Future (2001) (188)
- The Limits of Two-Party Differential Privacy (2010) (178)
- The relative complexity of NP search problems (1995) (168)
- Stochastic Boolean Satisfiability (2001) (161)
- Algorithms and complexity results for #SAT and Bayesian inference (2003) (160)
- Pan-Private Streaming Algorithms (2010) (158)
- Deterministic Communication vs. Partition Number (2015) (133)
- Rank bounds and integrality gaps for cutting planes procedures (2003) (126)
- An exponential separation between regular and general resolution (2002) (123)
- Linear gaps between degrees for the polynomial calculus modulo distinct primes (1999) (117)
- The Efficiency of Resolution and Davis--Putnam Procedures (2002) (112)
- On Interpolation and Automatization for Frege Systems (2000) (110)
- On the complexity of unsatisfiability proofs for random k-CNF formulas (1998) (107)
- Fairness through Causal Awareness: Learning Causal Latent-Variable Models for Biased Data (2019) (100)
- A Gradient-Based Boosting Algorithm for Regression Problems (2000) (97)
- Predict Responsibly: Improving Fairness and Accuracy by Learning to Defer (2017) (97)
- A new proof of the weak pigeonhole principle (2000) (96)
- Non-Automatizability of Bounded-Depth Frege Proofs (1999) (95)
- Solving #SAT and Bayesian Inference with Backtracking Search (2014) (89)
- Upper and lower bounds for tree-like cutting planes proofs (1994) (89)
- Communication lower bounds via critical block sensitivity (2013) (88)
- Minimum propositional proof length is NP-hard to linearly approximate (1998) (83)
- Resolution and the Weak Pigeonhole Principle (1997) (82)
- Query-to-Communication Lifting for PNP (2017) (75)
- Value Elimination: Bayesian Interence via Backtracking Search (2002) (74)
- A Tight Bound for Set Disjointness in the Message-Passing Model (2013) (74)
- Approximation and small depth Frege proofs (1991) (72)
- Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy (2007) (71)
- Exponential Lower Bounds for Monotone Span Programs (2016) (71)
- Lower Bounds for Lovász-Schrijver Systems and Beyond Follow from Multiparty Communication Complexity (2005) (70)
- On the Representational Efficiency of Restricted Boltzmann Machines (2013) (64)
- Are there Hard Examples for Frege Systems (1995) (63)
- Clause Learning Can Effectively P-Simulate General Propositional Resolution (2008) (61)
- Inapproximability of Treewidth and Related Problems (2014) (60)
- Toward a Model for Backtracking and Dynamic Programming (2005) (58)
- The story of set disjointness (2010) (57)
- The Landscape of Communication Complexity Classes (2018) (56)
- Reducing the complexity of reductions (1997) (53)
- Minimizing Disjunctive Normal Form Formulas and AC0 Circuits Given a Truth Table (2008) (53)
- Exponential Lower Bounds and Integrality Gaps for Tree-Like Lovász-Schrijver Procedures (2009) (53)
- Semialgebraic Proofs and Efficient Algorithm Design (2019) (52)
- A Strong Direct Product Theorem for Corruption and the Multiparty Communication Complexity of Disjointness (2006) (51)
- Algebraic Propositional Proof Systems (1996) (49)
- Regular resolution lower bounds for the weak pigeonhole principle (2001) (49)
- Lifting Nullstellensatz to monotone span programs over any field (2018) (47)
- The complexity of resolution refinements (2003) (46)
- Learnability and automatizability (2004) (46)
- Randomized Communication vs. Partition Number (2015) (45)
- The complexity of properly learning simple concept classes (2008) (45)
- Strongly exponential lower bounds for monotone computation (2017) (44)
- Good degree bounds on Nullstellensatz refutations of the induction principle (1996) (42)
- Circuit Complexity, Proof Complexity, and Polynomial Identity Testing (2014) (41)
- The complexity of analytic tableaux (2001) (41)
- Causal Modeling for Fairness in Dynamical Systems (2019) (41)
- Formula Caching in DPLL (2010) (41)
- Proceedings of the forty-fourth annual ACM symposium on Theory of computing (2012) (40)
- Hardness amplification in proof complexity (2009) (37)
- DPLL with Caching: A new algorithm for #SAT and Bayesian Inference (2003) (37)
- Memoization and DPLL: formula caching proof systems (2003) (37)
- Inapproximability of Treewidth, One-Shot Pebbling, and Related Layout Problems (2011) (34)
- Improved Separations between Nondeterministic and Randomized Multiparty Communication (2008) (32)
- Zero-Information Protocols and Unambiguity in Arthur–Merlin Communication (2015) (31)
- Homogenization and the polynomial calculus (2003) (31)
- The complexity of the Hajos calculus (1992) (31)
- Minimizing DNF Formulas and AC0 Circuits Given a Truth Table (2005) (28)
- No feasible interpolation for TC/sup 0/-Frege proofs (1997) (27)
- An Exponential Separation Between the Parity Principle and the Pigeonhole Principle (1996) (27)
- A direct sum theorem for corruption and the multiparty NOF communication complexity of set disjointness (2005) (26)
- The Hardness of Being Private (2012) (25)
- An exponential separation between the matching principle and the pigeonhole principle (1993) (24)
- Lower Bounds for Lov[a-acute]sz--Schrijver Systems and Beyond Follow from Multiparty Communication Complexity (2007) (24)
- Integrality Gaps of 2-o(1) for Vertex Cover SDPs in the Lov[a-acute]sz--Schrijver Hierarchy (2010) (22)
- Guilt-free data reuse (2017) (22)
- Poly-logarithmic Frege depth lower bounds via an expander switching lemma (2016) (22)
- Automating cutting planes is NP-hard (2020) (21)
- Separating Deterministic from Randomized Multiparty Communication Complexity (2010) (21)
- Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling (2007) (21)
- Lifting with Simple Gadgets and Applications to Circuit and Proof Complexity (2020) (21)
- Monotone Circuits for the Majority Function (2006) (21)
- Improved depth lower bounds for small distance connectivity (1995) (19)
- Stabbing Planes (2017) (19)
- Minimizing DNF formulas and AC/sup 0//sub d/ circuits given a truth table (2006) (19)
- Separating NOF communication complexity classes RP and NP (2008) (18)
- Query-to-Communication Lifting Using Low-Discrepancy Gadgets (2019) (18)
- Effectively Polynomial Simulations (2010) (18)
- Randomized Communication versus Partition Number (2018) (17)
- Random Θ(log n)-CNFs Are Hard for Cutting Planes (2017) (17)
- Separating Deterministic from Nondeterministic NOF Multiparty Communication Complexity (2007) (16)
- The PSPACE-Completeness of Black-White Pebbling (2010) (16)
- Query-to-communication lifting for BPP using inner product (2019) (14)
- A little advice can be very helpful (2012) (14)
- Automating algebraic proof systems is NP-hard (2021) (14)
- Predict Responsibly: Increasing Fairness by Learning To Defer (2017) (14)
- Algebraic proof complexity: progress, frontiers and challenges (2016) (13)
- Exponential Lower Bounds for the Tree-Like Hajós Calculus (1995) (13)
- Average Case Lower Bounds for Monotone Switching Networks (2013) (13)
- Theoretical bounds on estimation error for meta-learning (2020) (13)
- A Feasibly Constructive Lower Bound for Resolution Proofs (1990) (12)
- Reproducibility in learning (2022) (12)
- An Exponential Time/Space Speedup For Resolution (2007) (10)
- Conditional Lower Bound for a System of Constant-Depth Proofs with Modular Connectives (2006) (10)
- Lower bounds for Lov´ asz-Schrijver systems and beyond, using multiparty communication complexity (2005) (10)
- Size and Depth Separation in Approximating Benign Functions with Neural Networks (2021) (10)
- Towards lower bounds for bounded-depth Frege proofs with modular connectives (1996) (10)
- Random CNFs are Hard for Cutting Planes (2017) (9)
- On the power and limitations of branch and cut (2021) (9)
- On the Expressive Power of Restricted Boltzmann Machines (2013) (9)
- Short Proofs Are Hard to Find (2019) (9)
- Automatizability and Simple Stochastic Games (2011) (8)
- Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012 (2012) (8)
- Unsolvable Systems of Equations and Proof Complexity (1998) (7)
- Proof Complexity and Beyond (2018) (7)
- Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds (2011) (7)
- On ACC 0 [ p k ] Frege proofs (1997) (7)
- The power of weak formal systems (1992) (7)
- Semantics for Nondeterministic Asynchronous Broadcast Networks (1987) (7)
- Linear and Negative Resolution are Weaker than Resolution (2001) (7)
- The Surprising Power of Constant Depth Algebraic Proofs (2020) (7)
- KRW Composition Theorems via Lifting (2020) (6)
- Bounded-depth Frege lower bounds for weaker pigeonhole principles (2002) (6)
- Homogenization and the Polynominal Calculus (2000) (6)
- Tight integrality gaps for Vertex Cover SDPs in the Lovasz-Schrijver hierarchy (2006) (5)
- Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity (2021) (5)
- Lower Bounds for Nondeterministic Semantic Read-Once Branching Programs (2016) (5)
- The future of computational complexity theory: part II (1996) (5)
- Size and Depth Separation in Approximating Natural Functions with Neural Networks (2021) (5)
- Black-White Pebbling is PSPACE-Complete (2007) (4)
- Fairness Through Causal Awareness: Learning Latent-Variable Models for Biased Data (2018) (4)
- On the pseudo-deterministic query complexity of NP search problems (2021) (4)
- Towards a Complexity-Theoretic Understanding of Restarts in SAT Solvers (2020) (4)
- Stochastic Boolean Satissability (2000) (3)
- Delay of reinforcement effects with reflective and impulsive children. (1978) (3)
- Upper and Lower Bounds on the Power of Advice (2016) (3)
- Lifting lower bounds for tree-like proofs (2014) (2)
- Lifting: As Easy As 1, 2, 3 (2020) (2)
- The Complexity of the Haj os Calculus (1992) (2)
- Stability is Stable: Connections between Replicability, Privacy, and Adaptive Generalization (2023) (2)
- The Complexity of the Haj6s Calculus (1992) (2)
- Memoization and DPLL (2003) (1)
- Inapproximability of Treewidth and Related Problems (Extended Abstract) (2015) (1)
- The Landscape of Communication Complexity Classes (2018) (1)
- Quantile Risk Control: A Flexible Framework for Bounding the Probability of High-Loss Predictions (2022) (1)
- Hardness of Function Composition for Semantic Read once Branching Programs (2018) (1)
- Propositional Proof Complexity: A Survey on the State of the Art, Including Some Recent Results (2011) (1)
- Lower bounds for Polynomial Calculus with extension variables over finite fields (2022) (1)
- Random \( \Theta (\log n) \) -CNFs are Hard for Cutting Planes (2022) (1)
- Tradeoffs for small-depth Frege proofs (2021) (1)
- The Strength of Equality Oracles in Communication (2022) (1)
- Secret Sharing, Slice Formulas, and Monotone Real Circuits (2022) (1)
- Semantics of Nondeterministic Asynchronous Broadcast Networks (1993) (1)
- Zero-Information Protocols and Unambiguity in Arthur–Merlin Communication (2016) (1)
- Recognizing and Overcoming Frictions to Fairness (2020) (0)
- Progress in Lifting and Applications in Lower Bounds (Invited Talk) (2019) (0)
- Upper and Lower Bounds on the Power of Advice Arkadev Chattopadhyay (2016) (0)
- ) Fall , 2022 Herbrand Theorem , Equality , and Compactness The Herbrand Theorem (2022) (0)
- University of Azores, Ponta Delgada, Azores, Portugal June 30–July 4, 2010 (2011) (0)
- University of California, San Diego, March 20–23, 1999 (1999) (0)
- CSC 2429 – Approaches to the P vs . NP Question and Related Complexity Questions Lecture 2 : Switching Lemma , AC 0 Circuit Lower Bounds Lecturer : Toniann Pitassi Scribe : Robert Robere Winter 2014 1 Switching Lemmas (2014) (0)
- Extremely Deep Proofs (2021) (0)
- CS 2429-Foundations of Communication Complexity Lecture (2012) (0)
- Mathematisches Forschungsinstitut Oberwolfach Proving Hard-core Predicates Using List Decoding Proving Integrality Gaps without Knowing the Linear Program How to Go beyond the Black-box Simulation Barrier Derandomization in Cryptography Formula Caching Proof Systems Algebras of Minimal Rank over Arb (2003) (0)
- Correction to: Query-to-Communication Lifting for PNP (2019) (0)
- Reflections on Proof Complexity and Counting Principles (2021) (0)
- 1 Applications of Communication Complexity : Extended Formulations of Linear Programs (2015) (0)
- Communication Complexity and Information Complexity: Foundations and New Directions (2012) (0)
- On ACC<supscrpt>0</supscrpt>[<italic>p<supscrpt>k</supscrpt></italic>] Frege proofs (1997) (0)
- Causal Modeling for Fairness in Dynamical Systems (Supplemental) (2020) (0)
- Lower Bounds for Cutting Planes ( Extended Abstract ) (2011) (0)
- CS 2429-Foundations of Communication Complexity (2012) (0)
- Explorer Effectively Polynomial Simulations (2009) (0)
- On Learning and Refutation in Noninteractive Local Differential Privacy (2022) (0)
- Proceedings Twenty-Second Annual IEEE Conference on Computational Complexity: Preface (2007) (0)
- Computational Complexity (2018) (0)
- Madison, WI, USA March 31–April 3, 2012 (2013) (0)
- CS 2429-Foundations of Communication Complexity Lecturer : Toniann Pitassi 1 Proof Complexity Lower Bounds (2014) (0)
- Correction to: Query-to-Communication Lifting for PNP (2019) (0)
- Special Issue In Memory of Misha Alekhnovich. Foreword (2011) (0)
- Algebraic Proof Systems (Invited Talk) (2021) (0)
- Learning versus Refutation in Noninteractive Local Differential Privacy (2022) (0)
- CS 2429-Foundations of Communication Complexity Lecturer : (2014) (0)
- Lifting lower bounds for tree-like proofs (2013) (0)
This paper list is powered by the following services:
Other Resources About Toniann Pitassi
What Schools Are Affiliated With Toniann Pitassi?
Toniann Pitassi is affiliated with the following schools:
