default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, 2017
Volume TR17, 2017
- Stephen A. Cook, Bruce M. Kapron:
A Survey of Classes of Primitive Recursive Functions. - Frantisek Duris:
Some notes on two lower bound methods for communication complexity. - Yi Deng:
Magic Adversaries Versus Individual Reduction: Science Wins Either Way. - Scott Aaronson:
P=?NP. - Nir Bitansky:
Verifiable Random Functions from Non-Interactive Witness-Indistinguishable Proofs. - Constantinos Daskalakis, Nishanth Dikkala, Gautam Kamath:
Testing Ising Models. - Michael A. Forbes, Amir Shpilka, Ben Lee Volk:
Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds. - Benny Applebaum, Naama Haramaty, Yuval Ishai, Eyal Kushilevitz, Vinod Vaikuntanathan:
Low-Complexity Cryptographic Hash Functions. - Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf:
Towards an algebraic natural proofs barrier via polynomial identity testing. - Xiaodi Wu, Penghui Yao, Henry S. Yuen:
Raz-McKenzie simulation with the inner product gadget. - Boaz Barak, Pravesh Kothari, David Steurer:
Quantum entanglement, sum of squares, and the log rank conjecture. - Dominik Barth, Moritz Beck, Titus Dose, Christian Glaßer, Larissa Michler, Marc Technau:
Emptiness Problems for Integer Circuits. - Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan:
On polynomial approximations over ℤ/2kℤ. - Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay:
Composition and Simulation Theorems via Pseudo-random Properties. - Ilan Komargodski, Moni Naor, Eylon Yogev:
White-Box vs. Black-Box Complexity of Search Problems: Ramsey and Graph Property Testing. - Vishwas Bhargava, Gábor Ivanyos, Rajat Mittal, Nitin Saxena:
Irreducibility and deterministic r-th root finding over finite fields. - Michal Moshkovitz, Dana Moshkovitz:
Mixing Implies Lower Bounds for Space Bounded Learning. - Oded Goldreich, Guy N. Rothblum:
Simple doubly-efficient interactive proof systems for locally-characterizable sets. - Andreas Krebs, Nutan Limaye, Michael Ludwig:
A Unified Method for Placing Problems in Polylogarithmic Depth. - Ran Raz:
A Time-Space Lower Bound for a Large Class of Learning Problems. - Neeraj Kayal, Vineet Nair, Chandan Saha, Sébastien Tavenas:
Reconstruction of full rank Algebraic Branching Programs. - Benjamin Rossman, Srikanth Srinivasan:
Separation of AC0[⊕] Formulas and Circuits. - Russell Impagliazzo, Valentine Kabanets, Ilya Volkovich:
The Power of Natural Properties as Oracles. - Mika Göös, Pritish Kamath, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for P^NP. - Pooya Hatami, Avishay Tal:
Pseudorandom Generators for Low-Sensitivity Functions. - Valentine Kabanets, Daniel M. Kane, Zhenjian Lu:
A Polynomial Restriction Lemma with Applications. - Avraham Ben-Aroya, Eshan Chattopadhyay, Dean Doron, Xin Li, Amnon Ta-Shma:
A reduction from efficient non-malleable extractors to low-error two-source extractors with arbitrary constant rate. - Mrinal Kumar:
A quadratic lower bound for homogeneous algebraic branching programs. - Clément L. Canonne, Tom Gur:
An Adaptivity Hierarchy Theorem for Property Testing. - Amey Bhangale, Subhash Khot, Devanathan Thiruvenkatachari:
An Improved Dictatorship Test with Perfect Completeness. - Thomas Watson:
Quadratic Simulations of Merlin-Arthur Games. - Olaf Beyersdorff, Joshua Blinkhorn:
Formulas with Large Weight: a New Technique for Genuine QBF Lower Bounds. - Daniel M. Kane, Shachar Lovett, Sankeerth Rao:
Labeling the complete bipartite graph with no zero cycles. - Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam:
On algebraic branching programs of small width. - Manindra Agrawal, Michael A. Forbes, Sumanta Ghosh, Nitin Saxena:
Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good. - Dean Doron, Francois Le Gall, Amnon Ta-Shma:
Probabilistic logarithmic-space algorithms for Laplacian solvers. - Olaf Beyersdorff, Leroy Chew, Meena Mahajan, Anil Shukla:
Understanding Cutting Planes for QBFs. - Benny Applebaum, Barak Arkis, Pavel Raykov, Prashant Nalini Vasudevan:
Conditional Disclosure of Secrets: Amplification, Closure, Amortization, Lower-bounds, and Separations. - Marshall Ball
, Alon Rosen, Manuel Sabin, Prashant Nalini Vasudevan:
Average-Case Fine-Grained Hardness. - Sivaramakrishnan Natarajan Ramamoorthy, Anup Rao:
Non-Adaptive Data Structure Lower Bounds for Median and Predecessor Search from Sunflowers. - Amnon Ta-Shma:
Explicit, almost optimal, epsilon-balanced codes. - Pavel Hrubes, Pavel Pudlák:
Random formulas, monotone circuits, and interpolation. - Alexey Milovanov, Nikolai K. Vereshchagin:
Stochasticity in Algorithmic Statistics for Polynomial Time. - Olaf Beyersdorff, Luke Hinde, Ján Pich:
Reasons for Hardness in QBF Proof Systems. - Noah Fleming, Denis Pankratov, Toniann Pitassi, Robert Robere:
Random CNFs are Hard for Cutting Planes. - Sebastian Berndt, Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
Learning Residual Alternating Automata. - Kasper Green Larsen, Omri Weinstein, Huacheng Yu:
Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds. - Pavel Hrubes, Pavel Pudlák:
A note on monotone real circuits. - Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri:
Optimal Unateness Testers for Real-Valued Functions: Adaptivity Helps. - Joe Boninger, Joshua Brody, Owen Kephart:
Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search. - Mark Bun, Justin Thaler:
A Nearly Optimal Lower Bound on the Approximate Degree of AC0. - Dieter van Melkebeek, Gautam Prakriya:
Derandomizing Isolation in Space-Bounded Settings. - Mika Göös, Toniann Pitassi, Thomas Watson:
Query-to-Communication Lifting for BPP. - Anurag Anshu, Naresh B. Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay:
Lifting randomized query complexity to randomized communication complexity. - Maya Leshkowitz:
Round Complexity Versus Randomness Complexity in Interactive Proofs. - Paul W. Goldberg, Christos H. Papadimitriou:
Towards a Unified Complexity Theory of Total Functions. - Alessandro Chiesa, Michael A. Forbes, Nicholas Spooner:
A Zero Knowledge Sumcheck and its Applications. - Noga Alon, Omri Ben-Eliezer, Eldar Fischer:
Testing hereditary properties of ordered graphs and matrices. - Ola Svensson, Jakub Tarnawski:
The Matching Problem in General Graphs is in Quasi-NC. - Boaz Barak, Zvika Brakerski, Ilan Komargodski, Pravesh Kothari:
Limits on Low-Degree Pseudorandom Generators (Or: Sum-of-Squares Meets Program Obfuscation). - Anat Ganor, Karthik C. S.:
Communication Complexity of Correlated Equilibrium in Two-Player Games. - Arkadev Chattopadhyay, Nikhil S. Mande:
Dual polynomials and communication complexity of XOR functions. - Benny Applebaum:
Exponentially-Hard gap-CSP and local PRG via Local Hardcore Functions. - Venkatesan Guruswami, Chaoping Xing, Chen Yuan:
Subspace Designs based on Algebraic Function Fields. - Boaz Barak:
The Complexity of Public-Key Cryptograph. - Josh Alman, Joshua R. Wang, Huacheng Yu:
Cell-Probe Lower Bounds from Online Communication Complexity. - Benny Applebaum:
Garbled Circuits as Randomized Encodings of Functions: a Primer. - Xi Chen, Rocco A. Servedio, Li-Yang Tan, Erik Waingarten, Jinyu Xie:
Settling the query complexity of non-adaptive junta testing. - Jacob Steinhardt:
Does robustness imply tractability? A lower bound for planted clique in the semi-random model. - Shachar Lovett, Sankeerth Rao, Alexander Vardy:
Probabilistic Existence of Large Sets of Designs. - Young Kun-Ko, Ariel Schvartzman:
Bounds for the Communication Complexity of Two-Player Approximate Correlated Equilibria. - Eric Allender, Andreas Krebs, Pierre McKenzie:
Better Complexity Bounds for Cost Register Machines. - Eric Allender, Shuichi Hirahara:
New Insights on the (Non)-Hardness of Circuit Minimization and Related Problems. - Vikraman Arvind, Rajit Datta, Partha Mukhopadhyay, Raja S:
Efficient Identity Testing and Polynomial Factorization over Non-associative Free Rings. - Clément L. Canonne, Ilias Diakonikolas, Alistair Stewart:
Fourier-Based Testing for Families of Distributions. - Tianren Liu, Vinod Vaikuntanathan, Hoeteck Wee:
New Protocols for Conditional Disclosure of Secrets (and More). - Guillaume Lagarde, Nutan Limaye, Srikanth Srinivasan:
Lower Bounds and PIT for Non-Commutative Arithmetic circuits with Restricted Parse Trees. - Nico Döttling, Jesper Buus Nielsen, Maciej Obremski:
Information Theoretic Continuously Non-Malleable Codes in the Constant Split-State Model. - Alexander A. Sherstov, Pei Wu:
Optimal Interactive Coding for Insertions, Deletions, and Substitutions. - Joshua Brakensiek, Venkatesan Guruswami:
The Quest for Strong Inapproximability Results with Perfect Completeness. - Badih Ghazi, Madhu Sudan:
The Power of Shared Randomness in Uncertain Communication. - Daniel M. Kane, Shachar Lovett, Shay Moran:
Near-optimal linear decision trees for k-SUM and related problems. - Arkadev Chattopadhyay, Nikhil S. Mande:
Weights at the Bottom Matter When the Top is Heavy. - Iftach Haitner, Salil P. Vadhan:
The Many Entropies in One-Way Functions. - Daniel M. Kane, Shachar Lovett, Shay Moran, Jiapeng Zhang:
Active classification with comparison queries. - C. Ramya, B. V. Raghavendra Rao:
Linear Projections of the Vandermonde Polynomial. - Pushkar S. Joglekar, B. V. Raghavendra Rao, Siddharth S. Sivakumar:
On Weak-Space Complexity over Complex Numbers. - Elena Grigorescu, Akash Kumar, Karl Wimmer:
K-Monotonicity is Not Testable on the Hypercube. - Irit Dinur, Tali Kaufman:
High dimensional expanders imply agreement expanders. - Chin Ho Lee, Emanuele Viola:
The coin problem for product tests. - Andrej Bogdanov:
Small bias requires large formulas. - Shuichi Hirahara:
A Duality Between Depth-Three Formulas and Approximation by Depth-Two. - Klim Efremenko, Gillat Kol, Raghuvansh Saxena:
Interactive Coding Over the Noisy Broadcast Channel. - Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra:
On Non-Optimally Expanding Sets in Grassmann Graphs. - Ran Gelles, Yael Tauman Kalai:
Constant-Rate Interactive Coding Is Impossible, Even In Constant-Degree Networks. - Irit Dinur, Inbal Livni Navon:
Exponentially Small Soundness for the Direct Product Z-test. - Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan:
Multi Collision Resistant Hash Functions and their Applications. - Raman Arora, Amitabh Basu, Poorya Mianjy, Anirbit Mukherjee:
Understanding Deep Neural Networks with Rectified Linear Units. - Nir Bitansky, Omer Paneth, Yael Tauman Kalai:
Multi-Collision Resistance: A Paradigm for Keyless Hash Functions. - Dakshita Khurana, Amit Sahai:
How to Achieve Non-Malleability in One or Two Rounds. - Oded Goldreich:
On the doubly-efficient interactive proof systems of GKR. - Oded Goldreich:
Overview of the doubly-efficient interactive proof systems of RRR. - Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, Nithin Varma:
Parameterized Property Testing of Functions. - Brett Hemenway, Noga Ron-Zewi, Mary Wootters:
Local List Recovery of High-rate Tensor Codes & Applications. - Shafi Goldwasser, Ofer Grossman, Dhiraj Holden:
Pseudo-Deterministic Proofs. - Mateus de Oliveira Oliveira, Pavel Pudlák:
Representations of Monotone Boolean Functions by Linear Programs. - Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal:
A Composition Theorem for Randomized Query complexity. - Shafi Goldwasser, Guy N. Rothblum, Yael Tauman Kalai:
Delegating Computation: Interactive Proofs for Muggles. - Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova, Pierre McKenzie, Shadab Romani:
Does Looking Inside a Circuit Help? - Alessandro Chiesa, Peter Manohar, Igor Shinkar:
On Axis-Parallel Tests for Tensor Product Codes. - Roksana Baleshzar, Deeparnab Chakrabarty, Ramesh Krishnan S. Pallavoor, Sofya Raskhodnikova, C. Seshadhri:
A Lower Bound for Nonadaptive, One-Sided Error Testing of Unateness of Boolean Functions over the Hypercube. - Yehuda Lindell:
How To Simulate It - A Tutorial on the Simulation Proof Technique. - Andrej Bogdanov, Alon Rosen:
Pseudorandom Functions: Three Decades Later. - Maciej Liskiewicz, Matthias Lutter, Rüdiger Reischuk:
Proper Learning of k-term DNF Formulas from Satisfying Assignments. - Arnab Bhattacharyya, Suprovat Ghoshal, Rishi Saket:
Hardness of learning noisy halfspaces using polynomial thresholds. - Michal Moshkovitz, Dana Moshkovitz:
Mixing Implies Strong Lower Bounds for Space Bounded Learning. - Dmitry Itsykson, Alexander Knop:
Hard satisfiable formulas for splittings by linear combinations. - Xiaotie Deng, Zhe Feng, Rucha Kulkarni:
Octahedral Tucker is PPA-Complete. - Badih Ghazi, T. S. Jayram:
Resource-Efficient Common Randomness and Secret-Key Schemes. - Paul Beame, Shayan Oveis Gharan, Xin Yang:
Time-Space Tradeoffs for Learning from Small Test Spaces: Learning Low Degree Polynomial Functions. - Sumegha Garg, Ran Raz, Avishay Tal:
Extractor-Based Time-Space Lower Bounds for Learning. - Rohit Gurjar, Ben Lee Volk:
Pseudorandom Bits for Oblivious Branching Programs. - Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs:
Quadratically Tight Relations for Randomized Query Complexity. - Mrinal Kumar, Ben Lee Volk:
An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits. - Badih Ghazi, Pritish Kamath, Prasad Raghavendra:
Dimension Reduction for Polynomials over Gaussian Space and Applications. - Swastik Kopparty, Shubhangi Saraf:
Local Testing and Decoding of High-Rate Error-Correcting Codes. - Rohit Gurjar, Thomas Thierauf, Nisheeth K. Vishnoi:
Isolating a Vertex via Lattices: Polytopes with Totally Unimodular Faces. - Or Meir:
The Direct Sum of Universal Relations. - Or Meir:
An Efficient Randomized Protocol for every Karchmer-Wigderson Relation with Two Rounds. - Oded Goldreich, Guy N. Rothblum:
Worst-case to Average-case reductions for subclasses of P. - Joshua A. Grochow, Cristopher Moore:
Designing Strassen's algorithm. - Ilias Diakonikolas, Daniel M. Kane, Alistair Stewart:
Sharp Bounds for Generalized Uniformity Testing. - Ilias Diakonikolas, Themis Gouleakis, John Peebles, Eric Price:
Sample-Optimal Identity Testing with High Probability. - Eli Ben-Sasson, Iddo Bentov, Yinon Horesh, Michael Riabzev:
Fast Reed-Solomon Interactive Oracle Proofs of Proximity. - Ramprasad Saptharishi, Anamay Tengse:
Quasi-polynomial Hitting Sets for Circuits with Restricted Parse Trees. - Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo:
Complete Classi fication of Generalized Santha-Vazirani Sources. - Olaf Beyersdorff, Joshua Blinkhorn, Luke Hinde:
Size, Cost, and Capacity: A Semantic Technique for Hard Random QBFs. - Srikanth Srinivasan, Madhu Sudan:
Local decoding and testing of polynomials over grids. - Thomas Watson:
A ZPP^NP[1] Lifting Theorem. - Tong Qin, Osamu Watanabe:
An improvement of the algorithm of Hertli for the unique 3SAT problem. - Joshua Brakensiek, Venkatesan Guruswami:
A Family of Dictatorship Tests with Perfect Completeness for 2-to-2 Label Cover. - Johan Håstad:
On small-depth Frege proofs for Tseitin for grids. - Tom Gur, Govind Ramnarayan, Ron Rothblum:
Relaxed Locally Correctable Codes. - Moritz Müller, Ján Pich:
Feasibly constructive proofs of succinct weak circuit lower bounds. - Roei Tell:
Quantified derandomization of linear threshold circuits. - Or Meir:
On Derandomized Composition of Boolean Functions. - Venkatesan Guruswami, Rishi Saket:
Hardness of Rainbow Coloring Hypergraphs. - Or Meir, Avishay Tal:
The Choice and Agreement Problems of a Random Function. - Or Meir, Avi Wigderson:
Prediction from Partial Information and Hindsight, with Application to Circuit Lower Bounds. - Andris Ambainis, Martins Kokainis, Krisjanis Prusis, Jevgenijs Vihrovs:
All Classical Adversary Methods are Equivalent for Total Functions. - Paul Beame, Noah Fleming, Russell Impagliazzo, Antonina Kolokolova, Denis Pankratov, Toniann Pitassi, Robert Robere:
Stabbing Planes. - Swagato Sanyal:
One-way Communication and Non-adaptive Decision Tree. - Pranjal Dutta, Nitin Saxena, Amit Sinhababu:
Discovering the roots: Uniform closure results for algebraic classes under factoring. - Christoph Berkholz:
The Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs. - Alessandro Chiesa, Tom Gur:
Proofs of Proximity for Distribution Testing. - Suryajith Chillara, Nutan Limaye, Srikanth Srinivasan:
Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications. - Monaldo Mastrolilli:
High Degree Sum of Squares Proofs, Bienstock-Zuckerberg hierarchy and Chvatal-Gomory cuts. - Eric Allender, Joshua A. Grochow, Dieter van Melkebeek, Cristopher Moore, Andrew Morgan:
Minimum Circuit Size, Graph Isomorphism, and Related Problems. - Hadley Black, Deeparnab Chakrabarty, C. Seshadhri:
A o(d) · polylog n Monotonicity Tester for Boolean Functions over the Hypergrid [n]d. - Eli Ben-Sasson, Eden Saig:
Collaborative Discovery: A study of Guru-follower dynamics. - Mark Braverman, Gil Cohen, Sumegha Garg:
Hitting Sets with Near-Optimal Error for Read-Once Branching Programs. - Klim Efremenko, Ankit Garg, Rafael Mendes de Oliveira, Avi Wigderson:
Barriers for Rank Methods in Arithmetic Complexity. - Michael A. Forbes, Amir Shpilka:
A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits. - Scott Aaronson:
Shadow Tomography of Quantum States. - Toniann Pitassi, Robert Robere:
Lifting Nullstellensatz to Monotone Span Programs over Any Field. - Emanuele Viola:
A sampling lower bound for permutations. - Chin Ho Lee, Emanuele Viola:
More on bounded independence plus noise: Pseudorandom generators for read-once polynomials. - Amos Beimel, Iftach Haitner, Nikolaos Makriyannis, Eran Omri:
Tighter Bounds on Multi-Party Coin Flipping, via Augmented Weak Martingales and Di erentially Private Sampling. - Mark Bun, Robin Kothari, Justin Thaler:
The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials. - Arkadev Chattopadhyay, Michal Koucký, Bruno Loff, Sagnik Mukhopadhyay:
Simulation Beats Richness: New Data-Structure Lower Bounds. - Eshan Chattopadhyay, Pooya Hatami, Omer Reingold, Avishay Tal:
Improved Pseudorandomness for Unordered Branching Programs through Local Monotonicity. - Itay Berman, Akshay Degwekar, Ron Rothblum, Prashant Nalini Vasudevan:
From Laconic Zero-Knowledge to Public-Key Cryptography. - Igor Carboni Oliveira, Ruiwen Chen, Rahul Santhanam:
An Average-Case Lower Bound against ACC^0. - Christian Engels, Mohit Garg, Kazuhisa Makino, Anup Rao:
On Expressing Majority as a Majority of Majorities. - Ankit Garg, Mika Göös, Pritish Kamath, Dmitry Sokolov:
Monotone Circuit Lower Bounds from Resolution. - Kamil Khadiev, Aliya Khadieva, Alexander Knop:
Exponential Separation between Quantum and Classical Ordered Binary Decision Diagrams, Reordering Method and Hierarchies. - Daniel M. Kane, Roi Livni, Shay Moran, Amir Yehudayoff:
On Communication Complexity of Classification Problems. - Justin Holmgren, Lisa Yang:
(A Counterexample to) Parallel Repetition for Non-Signaling Multi-Player Games. - Alexander Knop:
IPS-like Proof Systems Based on Binary Decision Diagrams. - Irit Dinur, Yuval Filmus, Prahladh Harsha:
Low degree almost Boolean functions are sparse juntas. - Irit Dinur, Yuval Filmus, Prahladh Harsha:
Agreement tests on graphs and hypergraphs. - Mark Braverman, Young Kun-Ko:
Information Value of Two-Prover Games. - Sivakanth Gopi, Venkatesan Guruswami, Sergey Yekhanin:
On Maximally Recoverable Local Reconstruction Codes. - Vladimir V. Podolskii, Alexander A. Sherstov:
Inner Product and Set Disjointness: Beyond Logarithmically Many Parties. - Makrand Sinha:
Lower Bounds for Approximating the Matching Polytope. - Karthik C. S., Bundit Laekhanukit, Pasin Manurangsi:
On the Parameterized Complexity of Approximating Dominating Set. - Roei Tell:
A Note on the Limitations of Two Black-Box Techniques in Quantified Derandomization. - Cody Murray, R. Ryan Williams:
Circuit Lower Bounds for Nondeterministic Quasi-Polytime: An Easy Witness Lemma for NP and NQP. - Benny Applebaum, Barak Arkis:
Conditional Disclosure of Secrets and d-Uniform Secret Sharing with Constant Information Rate. - Anirbit Mukherjee, Amitabh Basu:
Lower bounds over Boolean inputs for deep neural networks with ReLU gates. - Alexander Smal, Navid Talebanfard:
Prediction from Partial Information and Hindsight, an Alternative Proof. - Krishnamoorthy Dinesh, Jayalal Sarma:
Alternation, Sparsity and Sensitivity : Bounds and Exponential Gaps. - Oded Goldreich, Avishay Tal:
On Constant-Depth Canonical Boolean Circuits for Computing Multilinear Functions.
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.
last updated on 2025-01-14 21:04 CET 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:
