![](https://dblp1.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp1.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp1.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp1.uni-trier.de/img/search.dark.16x16.png)
default search action
Electronic 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.
![](https://dblp1.uni-trier.de/img/cog.dark.24x24.png)
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.