default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, 2014
Volume TR14, 2014
- Swastik Kopparty, Shubhangi Saraf, Amir Shpilka:
Equivalence of Polynomial Identity Testing and Deterministic Multivariate Polynomial Factorization. Article TR14-001 - Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar:
Direct Sum Testing. Article TR14-002 - Zeev Dvir, Rafael Oliveira, Amir Shpilka:
Testing Equivalence of Polynomials under Shifts. Article TR14-003 - Hasan Abasi, Nader H. Bshouty, Ariel Gabizon, Elad Haramaty:
On r-Simple k-Path. Article TR14-004 - Neeraj Kayal, Nutan Limaye, Chandan Saha, Srikanth Srinivasan:
An Exponential Lower Bound for Homogeneous Depth Four Arithmetic Formulas. Article TR14-005 - Venkatesan Guruswami, Euiwoong Lee:
Inapproximability of Feedback Vertex Set for Bounded Length Cycles. Article TR14-006 - Mark Braverman, Klim Efremenko:
List and Unique Coding for Interactive Communication in the Presence of Adversarial Noise. Article TR14-007 - N. Variyam Vinodchandran:
Space Complexity of the Directed Reachability Problem over Surface-Embedded Graphs. Article TR14-008 - Alexander A. Sherstov:
Breaking the Minsky-Papert Barrier for Constant-Depth Circuits. Article TR14-009 - Jean Bourgain, Zeev Dvir, Ethan Leeman:
Affine extractors over large fields with exponential error. Article TR14-010 - Dmitry Gavinsky, Pavel Pudlák:
Partition Expanders. Article TR14-011 - Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz:
AM with Multiple Merlins. Article TR14-012 - Mark Braverman, Kanika Pasricha:
The computational hardness of pricing compound options. Article TR14-013 - Olaf Beyersdorff, Leroy Chew:
The Complexity of Theorem Proving in Circumscription and Minimal Entailment. Article TR14-014 - Jack H. Lutz, Neil Lutz:
Lines Missing Every Random Point. Article TR14-015 - H. Gökalp Demirci, A. C. Cem Say, Abuzer Yakaryilmaz:
The Complexity of Debate Checking. Article TR14-016 - Eli Ben-Sasson, Emanuele Viola:
Short PCPs with projection queries. Article TR14-017 - Arnab Bhattacharyya:
Polynomial decompositions in polynomial time. Article TR14-018 - Parikshit Gopalan, Amir Yehudayoff:
Inequalities and tail bounds for elementary symmetric polynomials. Article TR14-019 - Pavel Hrubes, Anup Rao:
Circuits with Medium Fan-In. Article TR14-020 - Clément L. Canonne, Ronitt Rubinfeld:
Testing probability distributions underlying aggregated data. Article TR14-021 - Shay Moran, Makrand Sinha, Amir Yehudayoff:
Fooling Pairs in Randomized Communication Complexity. Article TR14-022 - Gil Cohen, Anat Ganor, Ran Raz:
Two Sides of the Coin Problem. Article TR14-023 - Russell Impagliazzo, Shachar Lovett, Ramamohan Paturi, Stefan Schneider:
0-1 Integer Linear Programming with a Linear Number of Constraints. Article TR14-024 - Oded Goldreich, Tom Gur, Ilan Komargodski:
Strong Locally Testable Codes with Relaxed Local Decoders. Article TR14-025 - Jop Briët, Zeev Dvir, Guangda Hu, Shubhangi Saraf:
Lower Bounds for Approximate LDCs. Article TR14-026 - Andris Ambainis, Krisjanis Prusis:
A Tight Lower Bound on Certificate Complexity in Terms of Block Sensitivity and Sensitivity. Article TR14-027 - Vikraman Arvind, S. Raja:
The Complexity of Two Register and Skew Arithmetic Computation. Article TR14-028 - Oded Goldreich, Dana Ron:
On Learning and Testing Dynamic Environments. Article TR14-029 - Dana Moshkovitz:
An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing. Article TR14-030 - João Marques-Silva, Mikolás Janota:
On the Query Complexity of Selecting Few Minimal Sets. Article TR14-031 - Olaf Beyersdorff, Leroy Chew:
Tableau vs. Sequent Calculi for Minimal Entailment. Article TR14-032 - Adi Akavia, Andrej Bogdanov, Siyao Guo, Akshay Kamath, Alon Rosen:
Candidate weak pseudorandom functions in AC0 ○ MOD2. Article TR14-033 - Gábor Ivanyos, Raghav Kulkarni, Youming Qiao, Miklos Santha, Aarthi Sundaram:
On the complexity of trial and error for constraint satisfaction problems. Article TR14-034 - Diptarka Chakraborty, Aduri Pavan, Raghunath Tewari, N. Variyam Vinodchandran, Lin F. Yang
:
New Time-Space Upperbounds for Directed Reachability in High-genus and H-minor-free Graphs. Article TR14-035 - Mikolas Janota, Leroy Chew, Olaf Beyersdorff:
On Unification of QBF Resolution-Based Calculi. Article TR14-036 - Hamidreza Jahanjou, Eric Miles, Emanuele Viola:
Succinct and explicit circuits for sorting and connectivity. Article TR14-037 - Ilario Bonacina, Nicola Galesi, Neil Thapen:
Total space in resolution. Article TR14-038 - Andrzej Lingas:
Vector convolution in O(n) steps and matrix multiplication in O(n^2) steps : -). Article TR14-039 - Hamed Hatami, Pooya Hatami, Shachar Lovett:
General systems of linear forms: equidistribution and true complexity. Article TR14-040 - Shachar Lovett:
Recent advances on the log-rank conjecture in communication complexity. Article TR14-041 - Deeparnab Chakrabarty, Kashyap Dixit, Madhav Jha, C. Seshadhri:
Property Testing on Product Distributions: Optimal Testers for Bounded Derivative Properties. Article TR14-042 - Venkatesan Guruswami, Euiwoong Lee:
Strong Inapproximability Results on Balanced Rainbow-Colorable Hypergraphs. Article TR14-043 - Daniel Dewey:
Additively efficient universal computers. Article TR14-044 - Mrinal Kumar, Shubhangi Saraf:
On the power of homogeneous depth 4 arithmetic circuits. Article TR14-045 - Gillat Kol, Shay Moran, Amir Shpilka, Amir Yehudayoff:
Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound. Article TR14-046 - Mark Braverman, Omri Weinstein:
An Interactive Information Odometer with Applications. Article TR14-047 - Avishay Tal:
Shrinkage of De Morgan Formulae from Quantum Query Complexity. Article TR14-048 - Anat Ganor, Gillat Kol, Ran Raz:
Exponential Separation of Information and Communication. Article TR14-049 - Edward A. Hirsch, Dmitry Sokolov:
On the probabilistic closure of the loose unambiguous hierarchy. Article TR14-050 - Subhash Khot, Rishi Saket:
Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with 2log nΩ(1) Colors. Article TR14-051 - Joshua A. Grochow, Toniann Pitassi:
Circuit complexity, proof complexity, and polynomial identity testing. Article TR14-052 - Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman:
Computing with a full memory: Catalytic space. Article TR14-053 - Dana Moshkovitz:
Parallel Repetition of Fortified Games. Article TR14-054 - Mika Göös, Thomas Watson:
Communication Complexity of Set-Disjointness for All Probabilities. Article TR14-055 - Zeev Dvir, Rafael Oliveira:
Factors of Sparse Polynomials are Sparse. Article TR14-056 - Manindra Agrawal, Diptarka Chakraborty, Debarati Das, Satyadev Nandakumar:
Measure of Non-pseudorandomness and Deterministic Extraction of Pseudorandomness. Article TR14-057 - Ilya Volkovich:
On Learning, Lower Bounds and (un)Keeping Promises. Article TR14-058 - Boaz Barak, David Steurer:
Sum-of-squares proofs and the quest toward optimal algorithms. Article TR14-059 - Anup Rao, Amir Yehudayoff:
Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness. Article TR14-060 - Raghav Kulkarni, Youming Qiao, Xiaoming Sun:
Any Monotone Property of 3-uniform Hypergraphs is Weakly Evasive. Article TR14-061 - Alexander Kozachinsky:
On the role of private coins in unbounded-round Information Complexity. Article TR14-062 - Adam R. Klivans, Pravesh Kothari:
Embedding Hard Learning Problems into Gaussian Space. Article TR14-063 - Arkadev Chattopadhyay, Michael E. Saks:
The Power of Super-logarithmic Number of Players. Article TR14-064 - Andrzej Dudek, Marek Karpinski, Andrzej Rucinski, Edyta Szymanska:
Approximate Counting of Matchings in (3,3)-Hypergraphs. Article TR14-065 - Suguru Tamaki, Yuichi Yoshida:
Robust Approximation of Temporal CSP. Article TR14-066 - Venkatesan Guruswami, Madhu Sudan, Ameya Velingker, Carol Wang:
Limitations on Testable Affine-Invariant Codes in the High-Rate Regime. Article TR14-067 - Eric Allender, Bireswar Das:
Zero Knowledge and Circuit Minimization. Article TR14-068 - Shashank Agrawal, Divya Gupta, Hemanta K. Maji, Omkant Pandey, Manoj Prabhakaran:
Explicit Non-Malleable Codes Resistant to Permutations. Article TR14-069 - Vikraman Arvind, Gaurav Rattan:
The Complexity of Geometric Graph Isomorphism. Article TR14-070 - Tetsuo Asano, David G. Kirkpatrick, Kotaro Nakagawa, Osamu Watanabe:
O(sqrt(n))-Space and Polynomial-time Algorithm for the Planar Directed Graph Reachability Problem. Article TR14-071 - Sajin Koroth, Jayalal Sarma:
Depth Lower Bounds against Circuits with Sparse Orientation. Article TR14-072 - Shachar Lovett, Cristopher Moore, Alexander Russell:
Group representations that resist random sampling. Article TR14-073 - Arkadev Chattopadhyay, Jaikumar Radhakrishnan, Atri Rudra:
Topology matters in communication. Article TR14-074 - Holger Dell:
A simple proof that AND-compression of NP-complete problems is hard. Article TR14-075 - Thomas Steinke:
Pseudorandomness and Fourier Growth Bounds for Width 3 Branching Programs. Article TR14-076 - Andris Ambainis, Jevgenijs Vihrovs:
Size of Sets with Small Sensitivity: a Generalization of Simon's Lemma. Article TR14-077 - Mika Göös, Toniann Pitassi, Thomas Watson:
Zero-Information Protocols and Unambiguity in Arthur-Merlin Communication. Article TR14-078 - Simon Straub, Thomas Thierauf, Fabian Wagner:
Counting the Number of Perfect Matchings in K5-free Graphs. Article TR14-079 - Stasys Jukna:
Lower Bounds for Tropical Circuits and Dynamic Programs. Article TR14-080 - Yuval Filmus, Massimo Lauria, Mladen Miksa, Jakob Nordström, Marc Vinyals:
From Small Space to Small Width in Resolution. Article TR14-081 - Yu Yu, Dawu Gu, Xiangxue Li:
The Randomized Iterate Revisited - Almost Linear Seed Length PRGs from A Broader Class of One-way Functions. Article TR14-082 - Irit Dinur, Shafi Goldwasser, Huijia Lin:
The Computational Benefit of Correlated Instances. Article TR14-083 - Luke Schaeffer:
A Physically Universal Cellular Automaton. Article TR14-084 - Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena:
Hitting-sets for ROABP and Sum of Set-Multilinear circuits. Article TR14-085 - Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler, Suresh Venkatasubramanian:
Verifiable Stream Computation and Arthur-Merlin Communication. Article TR14-086 - Abhishek Bhowmick, Shachar Lovett:
List decoding Reed-Muller codes over small fields. Article TR14-087 - Swagato Sanyal:
Sub-linear Upper Bounds on Fourier dimension of Boolean Functions in terms of Fourier sparsity. Article TR14-088 - Neeraj Kayal, Chandan Saha:
Lower Bounds for Depth Three Arithmetic Circuits with small bottom fanin. Article TR14-089 - Justin Thaler:
Semi-Streaming Algorithms for Annotated Graph Streams. Article TR14-090 - Ryan O'Donnell, A. C. Cem Say:
One time-travelling bit is as good as logarithmically many. Article TR14-091 - Mark Braverman, Young Kun-Ko, Omri Weinstein:
Approximating the best Nash Equilibrium in no(log n)-time breaks the Exponential Time Hypothesis. Article TR14-092 - Dmitry Itsykson, Mikhail Slabodkin, Dmitry Sokolov:
Resolution complexity of perfect mathcing principles for sparse graphs. Article TR14-093 - Zeev Dvir, Sivakanth Gopi:
2-Server PIR with sub-polynomial communication. Article TR14-094 - Mark Braverman, Ankit Garg:
Small value parallel repetition for general games. Article TR14-095 - Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Jacobo Torán:
Solving Linear Equations Parameterized by Hamming Weight. Article TR14-096 - Oded Goldreich, Liav Teichner:
Super-Perfect Zero-Knowledge Proofs. Article TR14-097 - Amey Bhangale, Swastik Kopparty, Sushant Sachdeva:
Simultaneous Approximation of Constraint Satisfaction Problems. Article TR14-098 - Gil Cohen, Igor Shinkar:
The Complexity of DNF of Parities. Article TR14-099 - Salman Beigi, Omid Etesami, Amin Gohari:
The Value of Help Bits in Randomized and Average-Case Complexity. Article TR14-100 - Balthazar Bauer, Shay Moran, Amir Yehudayoff:
Internal compression of protocols to entropy. Article TR14-101 - Eshan Chattopadhyay, David Zuckerman:
Non-Malleable Codes Against Constant Split-State Tampering. Article TR14-102 - Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Brendan Lucier, Vasilis Syrgkanis:
A Unifying Hierarchy of Valuations with Complements and Substitutes. Article TR14-103 - Atri Rudra, Mary Wootters:
It'll probably work out: improved list-decoding through random operations. Article TR14-104 - Craig Gentry:
Noncommutative Determinant is Hard: A Simple Proof Using an Extension of Barrington's Theorem. Article TR14-105 - Craig Gentry:
Computing on the edge of chaos: Structure and randomness in encrypted computation. Article TR14-106 - Or Meir:
Locally Correctable and Testable Codes Approaching the Singleton Bound. Article TR14-107 - Andrej Bogdanov, Christina Brzuska:
On Basing Size-Verifiable One-Way Functions on NP-Hardness. Article TR14-108 - Aran Nayebi, Scott Aaronson, Aleksandrs Belovs, Luca Trevisan:
Quantum lower bound for inverting a permutation with advice. Article TR14-109 - Uriel Feige, Shlomo Jozeph:
Separation between Estimation and Approximation. Article TR14-110 - Vikraman Arvind, Gaurav Rattan:
Faster FPT Algorithm for Graph Isomorphism Parameterized by Eigenvalue Multiplicity. Article TR14-111 - Louay Bazzi:
Entropy of weight distributions of small-bias spaces and pseudobinomiality. Article TR14-112 - Anat Ganor, Gillat Kol, Ran Raz:
Exponential Separation of Information and Communication for Boolean Functions. Article TR14-113 - Roei Tell:
An Alternative Proof of an Ω(k) Lower Bound for Testing k-linear Boolean Functions. Article TR14-114 - Roei Tell:
Deconstructions of Reductions from Communication Complexity to Property Testing using Generalized Parity Decision Trees. Article TR14-115 - Rahul Mehta:
2048 is (PSPACE) Hard, but Sometimes Easy. Article TR14-116 - Shiva Manne, Manjish Pal:
Fast Approximate Matrix Multiplication by Solving Linear Systems. Article TR14-117 - Albert Atserias, Massimo Lauria, Jakob Nordström:
Narrow Proofs May Be Maximally Long. Article TR14-118 - Mark Braverman, Jieming Mao:
Simulating Noisy Channel Interaction. Article TR14-119 - Olaf Beyersdorff, Leroy Chew, Mikolas Janota:
Proof Complexity of Resolution-based QBF Calculi. Article TR14-120 - Sebastian Müller:
Graph Structure and Parity Games. Article TR14-121 - Eric Allender, Anna Gál, Ian Mertz:
Dual VP Classes. Article TR14-122 - Shachar Lovett, Jiapeng Zhang:
Improved noisy population recovery, and reverse Bonami-Beckner inequality for sparse functions. Article TR14-123 - Periklis A. Papakonstantinou:
The Depth Irreducibility Hypothesis. Article TR14-124 - Anindya De:
Beyond the Central Limit Theorem: asymptotic expansions and pseudorandomness for combinatorial sums. Article TR14-125 - Debasis Mandal, Aduri Pavan, Rajeswari Venugopalan:
Separating Cook Completeness from Karp-Levin Completeness under a Worst-Case Hardness Hypothesis. Article TR14-126 - Alexandros G. Dimakis, Anna Gál, Ankit Singh Rawat, Zhao Song:
Batch Codes through Dense Graphs without Short Cycles. Article TR14-127 - Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana, Maciej Obremski:
Non-malleable Reductions and Applications. Article TR14-128 - Divesh Aggarwal, Stefan Dziembowski, Tomasz Kazana, Maciej Obremski:
Leakage-resilient non-malleable codes. Article TR14-129 - Ankit Gupta:
Algebraic Geometric Techniques for Depth-4 PIT & Sylvester-Gallai Conjectures for Varieties. Article TR14-130 - Olaf Beyersdorff, Leroy Chew, Karteek Sreenivasaiah:
A game characterisation of tree-like Q-Resolution size. Article TR14-131 - Diptarka Chakraborty, Elazar Goldenberg, Michal Koucký:
Information Complexity for Multiparty Communication. Article TR14-132 - Adam Case, Jack H. Lutz:
Mutual Dimension. Article TR14-133 - Martin Lück, Arne Meier, Irina Schindler:
Parameterized Complexity of CTL: Courcelle's Theorem For Infinite Vocabularies. Article TR14-134 - Noga Alon, Shay Moran, Amir Yehudayoff:
Sign rank, VC dimension and spectral gaps. Article TR14-135 - Viliam Geffert, Abuzer Yakaryilmaz:
Classical Automata on Promise Problems. Article TR14-136 - Neil Thapen:
A trade-off between length and width in resolution. Article TR14-137 - Nicola Galesi, Pavel Pudlák, Neil Thapen:
The space complexity of cutting planes refutations. Article TR14-138 - Hong Van Le:
Lower bounds for the circuit size of partially homogeneous polynomials. Article TR14-139 - Hong Van Le:
Constructing elusive functions with help of evaluation mappings. Article TR14-140 - Shachar Lovett:
Linear codes cannot approximate the network capacity within any constant factor. Article TR14-141 - Subhash Khot, Dana Moshkovitz:
Candidate Lasserre Integrality Gap For Unique Games. Article TR14-142 - Ronald de Haan, Stefan Szeider:
Compendium of Parameterized Problems at Higher Levels of the Polynomial Hierarchy. Article TR14-143 - Eric Blais, Clément L. Canonne, Igor Carboni Oliveira, Rocco A. Servedio, Li-Yang Tan:
Learning circuits with few negations. Article TR14-144 - Yuan Li, Alexander A. Razborov, Benjamin Rossman:
On the AC0 Complexity of Subgraph Isomorphism. Article TR14-145 - Ilario Bonacina, Nicola Galesi, Tony Huynh, Paul Wollan:
Space proof complexity for random 3-CNFs via a (2-ε)-Hall's Theorem. Article TR14-146 - Mika Göös, Shachar Lovett, Raghu Meka, Thomas Watson, David Zuckerman:
Rectangles Are Nonnegative Juntas. Article TR14-147 - Vitaly Feldman, Will Perkins, Santosh S. Vempala:
On the Complexity of Random Satisfiability Problems with Planted Solutions. Article TR14-148 - Kai-Min Chung, Xin Li, Xiaodi Wu:
Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications. Article TR14-149 - Justin Thaler:
Lower Bounds for the Approximate Degree of Block-Composed Functions. Article TR14-150 - Debajyoti Bera:
Quantum One-Sided Exact Error Algorithms. Article TR14-151 - Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, Song Zuo:
Tighter Relations Between Sensitivity and Other Complexity Measures. Article TR14-152 - Clément L. Canonne, Venkatesan Guruswami, Raghu Meka, Madhu Sudan:
Communication with Imperfectly Shared Randomness. Article TR14-153 - Andris Ambainis, Yuval Filmus, François Le Gall:
Fast Matrix Multiplication: Limitations of the Laser Method. Article TR14-154 - Scott Aaronson, Andris Ambainis:
Forrelation: A Problem that Optimally Separates Quantum from Classical Computing. Article TR14-155 - Jayadev Acharya, Clément L. Canonne, Gautam Kamath:
A Chasm Between Identity and Equivalence Testing with Conditional Queries. Article TR14-156 - Rafael Oliveira, Amir Shpilka, Ben Lee Volk:
Subexponential Size Hitting Sets for Bounded Depth Multilinear Formulas. Article TR14-157 - Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf:
Deterministic Identity Testing for Sum of Read Once ABPs. Article TR14-158 - A. C. Cem Say, Abuzer Yakaryilmaz:
Magic coins are useful for small-space quantum machines. Article TR14-159 - Gil Cohen, Igor Shinkar:
Zero-Fixing Extractors for Sub-Logarithmic Entropy. Article TR14-160 - Rahul Arora, Ashu Gupta, Rohit Gurjar, Raghunath Tewari:
Derandomizing Isolation Lemma for K3,3-free and K5-free Bipartite Graphs. Article TR14-161 - Michael A. Forbes, Venkatesan Guruswami:
Dimension Expanders via Rank Condensers. Article TR14-162 - Arnaud Durand, Meena Mahajan, Guillaume Malod, Nicolas de Rugy-Altherre, Nitin Saurabh:
Homomorphism polynomials complete for VP. Article TR14-163 - Cody Murray, Ryan Williams:
On the (Non) NP-Hardness of Computing Circuit Complexity. Article TR14-164 - Venkatesan Guruswami, Ameya Velingker:
An Entropy Sumset Inequality and Polynomially Fast Convergence to Shannon Capacity Over All Alphabets. Article TR14-165 - Mark Bun, Thomas Steinke:
Weighted Polynomial Approximations: Limits for Learning and Pseudorandomness. Article TR14-166 - Beate Bollig:
On the Minimization of (Complete) Ordered Binary Decision Diagrams. Article TR14-167 - Ilya Volkovich:
Deterministically Factoring Sparse Polynomials into Multilinear Factors. Article TR14-168 - Stasys Jukna:
Lower Bounds for Monotone Counting Circuits. Article TR14-169 - Yael Tauman Kalai, Ran Raz:
On the Space Complexity of Linear Programming with Preprocessing. Article TR14-170 - Lance Fortnow, Rahul Santhanam:
Hierarchies Against Sublinear Advice. Article TR14-171 - Alex Samorodnitsky, Ilya D. Shkredov, Sergey Yekhanin:
Kolmogorov Width of Discrete Linear Spaces: an Approach to Matrix Rigidity. Article TR14-172 - Igor Carboni Oliveira, Rahul Santhanam:
Majority is incompressible by AC0[p] circuits. Article TR14-173 - Avishay Tal:
Tight bounds on The Fourier Spectrum of AC0. Article TR14-174 - Abhishek Bhowmick, Shachar Lovett:
Nonclassical polynomials as a barrier to polynomial lower bounds. Article TR14-175 - Eric Allender, Dhiraj Holden, Valentine Kabanets:
The Minimum Oracle Circuit Size Problem. Article TR14-176 - Andreas Krebs, Klaus-Jörn Lange, Michael Ludwig:
Visibly Counter Languages and Constant Depth Circuits. Article TR14-177 - Dmitry Itsykson, Alexander Knop, Dmitry Sokolov:
Heuristic time hierarchies via hierarchies for sampling distributions. Article TR14-178 - Salman Beigi, Omid Etesami, Amin Gohari:
Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources. Article TR14-179 - Anna Gál, Jing-Tang Jang, Nutan Limaye, Meena Mahajan, Karteek Sreenivasaiah:
Space-Efficient Approximations for Subset Sum. Article TR14-180 - Scott Aaronson, Adam Bouland, Joseph F. Fitzsimons, Mitchell Lee:
The space "just above" BQP. Article TR14-181 - Dana Moshkovitz:
Direct Product Testing With Nearly Identical Sets. Article TR14-182 - Nikhil Balaji, Andreas Krebs, Nutan Limaye:
Skew Circuits of Small Width. Article TR14-183 - Ruiwen Chen, Valentine Kabanets:
Correlation Bounds and #SAT Algorithms for Small Linear-Size Circuits. Article TR14-184
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 2026-08-29 00: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, funded, and maintained by:
Schloss Dagstuhl - Leibniz Center for Informatics is a member of the Leibniz Association and is funded by the federal government of Germany and the states of Germany, especially Saarland and Rhineland‑Palatinate.
