default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCIDElectronic Colloquium on Computational Complexity, 2012
Volume TR12, 2012
- Arnab Bhattacharyya, Eldar Fischer, Shachar Lovett:
Testing Low Complexity Affine-Invariant Properties. Article TR12-001 - Akinori Kawachi, Benjamin Rossman, Osamu Watanabe:
Query Complexity and Error Tolerance of Witness Finding Algorithms. Article TR12-002 - Pratik Worah:
Rank Bounds for a Hierarchy of Lovász and Schrijver. Article TR12-003 - Marcos Villagra, Masaki Nakanishi, Shigeru Yamashita, Yasuhiko Nakashima:
Tensor Rank and Strong Quantum Nondeterminism in Multiparty Communication. Article TR12-004 - Periklis A. Papakonstantinou, Guang Yang:
A remark on one-wayness versus pseudorandomness. Article TR12-005 - Gregory Valiant:
Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas with Noise. Article TR12-006 - Ruiwen Chen, Valentine Kabanets:
Lower Bounds against Weakly Uniform Circuits. Article TR12-007 - Marek Karpinski, Richard Schmied:
On Approximation Lower Bounds for TSP with Bounded Metrics. Article TR12-008 - Prabhu Manyem, Julien Ugon:
Computational Complexity, NP Completeness and Optimization Duality: A Survey. Article TR12-009 - Shafi Goldwasser, Guy N. Rothblum:
How to Compute in the Presence of Leakage. Article TR12-010 - Nader H. Bshouty:
Testers and their Applications. Article TR12-011 - Oded Goldreich:
On the Effect of the Proximity Parameter on Property Testers. Article TR12-012 - Tomás Feder, Carlos S. Subi:
Packing Edge-Disjoint Triangles in Given Graphs. Article TR12-013 - Johannes Mittmann, Nitin Saxena, Peter Scheiblechner:
Algebraic Independence in Positive Characteristic - A p-Adic Calculus. Article TR12-014 - Albert Atserias, Anuj Dawar:
Degree Lower Bounds of Tower-Type for Approximating Formulas with Parity Quantifiers. Article TR12-015 - Anindya De, Elchanan Mossel:
Explicit Optimal hardness via Gaussian stability results. Article TR12-016 - Venkatesan Guruswami, Srivatsan Narayanan:
Combinatorial limitations of a strong form of list decoding. Article TR12-017 - Jörg Flum, Moritz Müller:
Some definitorial suggestions for parameterized proof complexity. Article TR12-018 - Eric Miles, Emanuele Viola:
On the complexity of constructing pseudorandom functions (especially when they don't exist). Article TR12-019 - Daniele Micciancio:
Inapproximability of the Shortest Vector Problem: Toward a Deterministic Reduction. Article TR12-020 - Oded Goldreich:
Two-Sided Error Proximity Oblivious Testing. Article TR12-021 - Amit Chakrabarti, Graham Cormode, Andrew McGregor, Justin Thaler:
Annotations in Data Streams. Article TR12-022 - Sophie Laplante, Virginie Lerays, Jérémie Roland:
Classical and quantum partition bound and detector inefficiency. Article TR12-023 - Scott Aaronson, Paul F. Christiano:
Quantum Money from Hidden Subspaces. Article TR12-024 - Kord Eickmeyer, Kristoffer Arnsfelt Hansen, Elad Verbin:
Approximating the minmax value of 3-player games within a constant is as hard as detecting planted cliques. Article TR12-025 - Thomas Watson:
Time Hierarchies for Sampling Distributions. Article TR12-026 - Eric Allender, Shiteng Chen, Tiancheng Lou, Periklis A. Papakonstantinou, Bangsheng Tang:
Time-space tradeoffs for width-parameterized SAT: Algorithms and lower bounds. Article TR12-027 - Eric Allender, George Davie, Luke Friedman, Samuel B. Hopkins, Iddo Tzameret:
Kolmogorov Complexity, Circuits, and the Strength of Formal Theories of Arithmetic. Article TR12-028 - Shachar Lovett:
An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem. Article TR12-029 - Deeparnab Chakrabarty, C. Seshadhri:
Optimal bounds for monotonicity and Lipschitz testing over the hypercube. Article TR12-030 - Tom Gur, Omer Tamuz:
Testing Booleanity and the Uncertainty Principle. Article TR12-031 - Sebastian Kuhnert, Johannes Köbler, Osamu Watanabe:
Interval graph representation with given interval and intersection lengths. Article TR12-032 - Ankit Gupta, Neeraj Kayal, Youming Qiao:
Random Arithmetic Formulas can be Reconstructed Efficiently. Article TR12-033 - Abhishek Bhowmick, Zeev Dvir, Shachar Lovett:
New Lower Bounds for Matching Vector Codes. Article TR12-034 - Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler
:
Finding Cycles and Trees in Sublinear Time. Article TR12-035 - Venkatesan Guruswami, Chaoping Xing:
Folded Codes from Function Field Towers and Improved Optimal Rate List Decoding. Article TR12-036 - Alexander A. Sherstov:
Making Polynomials Robust to Noise. Article TR12-037 - Iordanis Kerenidis, Sophie Laplante, Virginie Lerays, Jérémie Roland, David Xiao:
Lower bounds on information complexity via zero-communication protocols and applications. Article TR12-038 - Stasys Jukna:
Clique Problem, Cutting Plane Proofs, and Communication Complexity. Article TR12-039 - Sangxia Huang:
Approximation Resistance on Satisfiable Instances for Predicates Strictly Dominating Parity. Article TR12-040 - Stasys Jukna:
Limitations of Incremental Dynamic Programs. Article TR12-041 - Chris Beck, Russell Impagliazzo, Shachar Lovett:
Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-circuits. Article TR12-042 - Zvika Brakerski, Yael Tauman Kalai:
Efficient Interactive Coding Against Adversarial Noise. Article TR12-043 - Swastik Kopparty:
List-Decoding Multiplicity Codes. Article TR12-044 - Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer:
On the Concrete-Efficiency Threshold of Probabilistically-Checkable Proofs. Article TR12-045 - Madhu Sudan, Noga Zewi:
A new upper bound on the query complexity for testing generalized Reed-Muller codes. Article TR12-046 - Emanuele Viola:
Extractors for Turing-machine sources. Article TR12-047 - Alan Guo, Madhu Sudan:
Some closure features of locally testable affine-invariant properties. Article TR12-048 - Eli Ben-Sasson, Noga Ron-Zewi, Madhu Sudan:
Sparse affine-invariant linear codes are locally testable. Article TR12-049 - Avraham Ben-Aroya, Gil Cohen:
Gradual Small-Bias Sample Spaces. Article TR12-050 - Dmitry Gavinsky, Shachar Lovett, Michael E. Saks, Srikanth Srinivasan:
A Tail Bound for Read-k Families of Functions. Article TR12-051 - Mohammad Mahmoody, David Xiao:
Languages with Efficient Zero-Knowledge PCPs are in SZK. Article TR12-052 - Ankur Moitra:
A Singly-Exponential Time Algorithm for Computing Nonnegative Rank. Article TR12-053 - Eric Allender, Harry Buhrman, Luke Friedman, Bruno Loff:
Reductions to the set of random strings: the resource-bounded case. Article TR12-054 - Reut Levi, Dana Ron, Ronitt Rubinfeld:
Testing Similar Means. Article TR12-055 - Rocco A. Servedio, Li-Yang Tan, Justin Thaler:
Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions. Article TR12-056 - Russell Impagliazzo, Raghu Meka, David Zuckerman:
Pseudorandomness from Shrinkage. Article TR12-057 - Benny Applebaum, Yuval Ishai, Eyal Kushilevitz:
How to Garble Arithmetic Circuits. Article TR12-058 - Rahul Santhanam, Ryan Williams:
Uniform Circuits, Lower Bounds, and QBF Algorithms. Article TR12-059 - Parikshit Gopalan, Raghu Meka, Omer Reingold:
DNF Sparsification and a Faster Deterministic Counting. Article TR12-060 - Pavel Hrubes, Amir Yehudayoff:
Formulas are exponentially stronger than monotone circuits in non-commutative setting. Article TR12-061 - Ilan Komargodski, Ran Raz:
Average-Case Lower Bounds for Formula Size. Article TR12-062 - Raghav Kulkarni, Miklos Santha:
Query complexity of matroids. Article TR12-063 - Vitaly Feldman, Elena Grigorescu, Lev Reyzin, Santosh S. Vempala, Ying Xiao:
Statistical Algorithms and a Lower Bound for Planted Clique. Article TR12-064 - Mohammad Mahmoody, Hemanta K. Maji, Manoj Prabhakaran:
Limits of Random Oracles in Secure Computation. Article TR12-065 - Jinyu Huang:
Parallel Complexity for Matroid Intersection and Matroid Parity Problems. Article TR12-066 - Xiaohui Bei, Ning Chen, Shengyu Zhang:
On the Complexity of Trial and Error. Article TR12-067 - Manuel Arora, Gábor Ivanyos, Marek Karpinski, Nitin Saxena:
Deterministic Polynomial Factoring and Association Schemes. Article TR12-068 - Lakhdar Saïs, Mohand-Said Hacid, François Hantry:
On the complexity of computing minimal unsatisfiable LTL formulas. Article TR12-069 - Thomas Watson:
The Complexity of Estimating Min-Entropy. Article TR12-070 - Kazuhisa Seto, Suguru Tamaki:
A Satisfiability Algorithm and Average-Case Hardness for Formulas over the Full Binary Basis. Article TR12-071 - Anindya De, Ilias Diakonikolas, Vitaly Feldman, Rocco A. Servedio:
Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces. Article TR12-072 - Venkatesan Guruswami, Carol Wang:
Linear-algebraic list decoding for variants of Reed-Solomon codes. Article TR12-073 - Venkatesan Guruswami, Yuan Zhou:
Approximating Bounded Occurrence Ordering CSPs. Article TR12-074 - Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova:
Limitations of Local Filters of Lipschitz and Monotone Functions. Article TR12-075 - Pranjal Awasthi, Madhav Jha, Marco Molinaro, Sofya Raskhodnikova:
Testing Lipschitz Functions on Hypergrid Domains. Article TR12-076 - Chiranjit Chakraborty, Rahul Santhanam:
Instance Compression for the Polynomial Hierarchy and Beyond. Article TR12-077 - Vikraman Arvind, Sebastian Kuhnert, Johannes Köbler, Yadu Vasudev:
Approximate Graph Isomorphism. Article TR12-078 - Olaf Beyersdorff, Samir Datta, Andreas Krebs, Meena Mahajan, Gido Scharfenberger-Fabian, Karteek Sreenivasaiah, Michael Thomas, Heribert Vollmer:
Verifying Proofs in Constant Depth. Article TR12-079 - Baris Aydinlioglu, Dieter van Melkebeek:
Nondeterministic Circuit Lower Bounds from Mildly Derandomizing Arthur-Merlin Games. Article TR12-080 - Neeraj Kayal:
An exponential lower bound for the sum of powers of bounded degree polynomials. Article TR12-081 - Mahdi Cheraghchi, Venkatesan Guruswami, Ameya Velingker:
Restricted Isometry of Fourier Matrices and List Decodability of Random Linear Codes. Article TR12-082 - Thomas Steinke:
Pseudorandomness for Permutation Branching Programs Without the Group Theory. Article TR12-083 - Rahul Santhanam:
Ironic Complicity: Satisfiability Algorithms and Circuit Lower Bounds. Article TR12-084 - Tsuyoshi Ito, Thomas Vidick:
A multi-prover interactive proof for NEXP sound against entangled provers. Article TR12-085 - Shlomi Dolev, Nova Fandina, Dan Gutfreund:
Succinct Permanent is NEXP-hard with Many Hard Instances. Article TR12-086 - Peyman Afshani, Manindra Agrawal, Benjamin Doerr, Carola Winzen, Kasper Green Larsen, Kurt Mehlhorn:
The Deterministic and Randomized Query Complexity of a Simple Guessing Game. Article TR12-087 - Irit Dinur, Gillat Kol:
Covering CSPs. Article TR12-088 - Meena Boppana:
Lattice Variant of the Sensitivity Conjecture. Article TR12-089 - Michael Blondin, Andreas Krebs, Pierre McKenzie:
The Complexity of Intersecting Finite Automata Having Few Final States. Article TR12-090 - Abuzer Yakaryilmaz:
One-counter verifiers for decidable languages. Article TR12-091 - Pavol Duris:
A Note On the Hierarchy of One-way Data-Independent Multi-Head Finite Automata. Article TR12-092 - Charanjit S. Jutla, Vijay Kumar, Atri Rudra:
On the Circuit Complexity of Composite Galois Field Transformations. Article TR12-093 - Sanjeev Arora, Arnab Bhattacharyya, Rajsekar Manokaran, Sushant Sachdeva:
Testing Permanent Oracles - Revisited. Article TR12-094 - Avraham Ben-Aroya, Igor Shinkar:
A Note on Subspace Evasive Sets. Article TR12-095 - Albert Atserias, Sergi Oliva:
Bounded-width QBF is PSPACE-complete. Article TR12-096 - Andrej Bogdanov, Siyao Guo:
Sparse extractor families for all the entropy. Article TR12-097 - Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi:
An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin. Article TR12-098 - Nikos Leonardos:
An improved lower bound for the randomized decision tree complexity of recursive majority. Article TR12-099 - Tomas Jirotka:
NP Search Problems. Article TR12-100 - Oded Goldreich, Shafi Goldwasser, Dana Ron:
On the possibilities and limitations of pseudodeterministic algorithms. Article TR12-101 - Swastik Kopparty, Srikanth Srinivasan:
Certifying Polynomials for AC0[⊕] circuits, with applications. Article TR12-102 - Arnab Bhattacharyya, Yuichi Yoshida:
Testing Assignments of Boolean CSPs. Article TR12-103 - Matthew K. Franklin, Ran Gelles, Rafail Ostrovsky, Leonard J. Schulman:
Optimal Coding for Streaming Authentication and Interactive Communication. Article TR12-104 - Madhur Tulsiani, Pratik Worah:
$LS_+$ Lower Bounds from Pairwise Independence. Article TR12-105 - Alan Guo, Madhu Sudan:
New affine-invariant codes from lifting. Article TR12-106 - Brendan Juba, Ryan Williams:
Massive Online Teaching to Bounded Learners. Article TR12-107 - Arkadev Chattopadhyay, Rahul Santhanam:
Lower Bounds on Interactive Compressibility by Constant-Depth Circuits. Article TR12-108 - Subhash Khot, Muli Safra, Madhur Tulsiani:
Towards An Optimal Query Efficient PCP? Article TR12-109 - Siu On Chan:
Approximation Resistance from Pairwise Independent Subgroups. Article TR12-110 - Venkatesan Guruswami, Ali Kemal Sinop:
Faster SDP hierarchy solvers for local rounding algorithms. Article TR12-111 - Andrew Drucker:
New Limits to Classical and Quantum Instance Compression. Article TR12-112 - Manindra Agrawal, Chandan Saha, Nitin Saxena:
Quasi-polynomial Hitting-set for Set-depth-$\Delta$ Formulas. Article TR12-113 - Mikhail Anokhin:
Constructing a Pseudo-Free Family of Finite Computational Groups under the General Integer Factoring Intractability Assumption. Article TR12-114 - Michael A. Forbes, Amir Shpilka:
Quasipolynomial-time Identity Testing of Non-Commutative and Read-Once Oblivious Algebraic Branching Programs. Article TR12-115 - Luca Trevisan:
A Derandomized Switching Lemma and an Improved Derandomization of AC0. Article TR12-116 - Loïck Magnin, Jérémie Roland:
Explicit relation between all lower bound techniques for quantum query complexity. Article TR12-117 - Avi Wigderson, Amir Yehudayoff:
Population Recovery and Partial Identification. Article TR12-118 - Ilario Bonacina, Nicola Galesi:
Pseudo-partitions, Transversality and Locality: A Combinatorial Characterization for the Space Measure in Algebraic Proof Systems. Article TR12-119 - Boaz Barak:
Proof vs. Truth in Computational Complexity. Article TR12-120 - Pavel Hrubes:
A note on the real $\tau$-conjecture and the distribution of roots. Article TR12-121 - Giorgio Ausiello, Francesco Cristiano, Luigi Laura:
Syntactic Isomorphism of CNF Boolean Formulas is Graph Isomorphism Complete. Article TR12-122 - Parikshit Gopalan, Raghu Meka, Omer Reingold, Luca Trevisan, Salil P. Vadhan:
Better pseudorandom generators from milder pseudorandom restrictions. Article TR12-123 - Massimo Lauria:
A rank lower bound for cutting planes proofs of Ramsey Theorem. Article TR12-124 - Zahra Jafargholi, Hamidreza Jahanjou, Eric Miles, Jaideep Ramachandran, Emanuele Viola:
From RAM to SAT. Article TR12-125 - Shiva Kintali, Sinziana Munteanu:
Computing Bounded Path Decompositions in Logspace. Article TR12-126 - Eshan Chattopadhyay, Adam R. Klivans, Pravesh Kothari:
An Explicit VC-Theorem for Low-Degree Polynomials. Article TR12-127 - Nathanaël François, Frédéric Magniez:
Streaming Complexity of Checking Priority Queues. Article TR12-128 - Iftach Haitner, Eran Omri, Hila Zarosim:
On the Power of Random Oracles. Article TR12-129 - Abuzer Yakaryilmaz:
Public-qubits versus private-coins. Article TR12-130 - Mark Braverman, Ankur Moitra:
An Information Complexity Approach to Extended Formulations. Article TR12-131 - Yuval Filmus, Massimo Lauria, Jakob Nordström, Noga Ron-Zewi, Neil Thapen:
Space Complexity in Polynomial Calculus. Article TR12-132 - Noga Alon, Gil Cohen:
On Rigid Matrices and Subspace Polynomials. Article TR12-133 - Alexander A. Razborov, Emanuele Viola:
Real Advantage. Article TR12-134 - Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf:
Sampling-based proofs of almost-periodicity results and algorithmic applications. Article TR12-135 - Dan Boneh, Mark Zhandry:
Quantum-Secure Message Authentication Codes. Article TR12-136 - Johan Håstad:
On the correlation of parity and small-depth circuits. Article TR12-137 - Zeev Dvir, Shubhangi Saraf, Avi Wigderson:
Improved rank bounds for design matrices and a new proof of Kelly's theorem. Article TR12-138 - Albert Ai, Zeev Dvir, Shubhangi Saraf, Avi Wigderson:
Sylvester-Gallai type theorems for approximate collinearity. Article TR12-139 - Mark Zhandry:
How to Construct Quantum Random Functions. Article TR12-140 - Dmitry Itsykson, Dmitry Sokolov:
Lower bounds for myopic DPLL algorithms with a cut heuristic. Article TR12-141 - Markus Bläser:
Noncommutativity makes determinants hard. Article TR12-142 - Mark Braverman, Anup Rao, Omri Weinstein, Amir Yehudayoff:
Direct Products in Communication Complexity. Article TR12-143 - Rocco A. Servedio, Emanuele Viola:
On a special case of rigidity. Article TR12-144 - Cenny Wenner:
Circumventing d-to-1 for Approximation Resistance of Satisfiable Predicates Strictly Containing Parity of Width at Least Four. Article TR12-145 - Venkatesan Guruswami, Chaoping Xing:
List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound. Article TR12-146 - Xin Li:
New Independent Source Extractors with Exponential Improvement. Article TR12-147 - Eli Ben-Sasson, Ariel Gabizon, Yohay Kaplan, Swastik Kopparty, Shubhangi Saraf:
A new family of locally correctable codes based on degree-lifted algebraic geometry codes. Article TR12-148 - Alan Guo, Swastik Kopparty, Madhu Sudan:
New affine-invariant codes from lifting. Article TR12-149 - Michael Elberfeld, Christoph Stockhusen, Till Tantau:
On the Space Complexity of Parameterized Problems. Article TR12-150 - Subhash Khot, Madhur Tulsiani, Pratik Worah:
The Complexity of Somewhat Approximation Resistant Predicates. Article TR12-151 - Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
Inverse Problems in Approximate Uniform Generation. Article TR12-152 - Joshua Brody, Amit Chakrabarti, Ranganath Kondapally:
Certifying Equality With Limited Interaction. Article TR12-153 - Sourav Chakraborty, Eldar Fischer, Yonatan Goldhirsh, Arie Matsliah:
On the Power of Conditional Samples in Distribution Testing. Article TR12-154 - Clément L. Canonne, Dana Ron, Rocco A. Servedio:
Testing probability distributions using conditional samples. Article TR12-155 - Andrej Bogdanov, Chin Ho Lee:
Limits of provable security for homomorphic encryption. Article TR12-156 - Andrej Bogdanov, Chin Ho Lee:
On the depth complexity of homomorphic encryption schemes. Article TR12-157 - Aditya Bhaskara, Devendra Desai, Srikanth Srinivasan:
Optimal Hitting Sets for Combinatorial Shapes. Article TR12-158 - Eli Ben-Sasson, Michael Viderman:
A Combinatorial Characterization of smooth LTCs and Applications. Article TR12-159 - Frederic Green, Daniel Kreymer, Emanuele Viola:
Block-symmetric polynomials correlate with parity better than symmetric. Article TR12-160 - Olaf Beyersdorff, Nicola Galesi, Massimo Lauria:
A Characterization of Tree-Like Resolution Size. Article TR12-161 - Hans-Joachim Böckenhauer, Juraj Hromkovic, Dennis Komm, Sacha Krug, Jasmin Smula, Andreas Sprock:
The String Guessing Problem as a Method to Prove Lower Bounds on the Advice Complexity. Article TR12-162 - Avishay Tal:
Properties and Applications of Boolean Function Composition. Article TR12-163 - Rafail Ostrovsky, Ivan Visconti:
Simultaneous Resettability from Collision Resistance. Article TR12-164 - Martin R. Albrecht, Pooya Farshim, Jean-Charles Faugère, Gottfried Herold, Ludovic Perret:
Polly Cracker, Revisited. Article TR12-165 - Elad Haramaty, Madhu Sudan:
Deterministic Compression with Uncertain Priors. Article TR12-166 - Periklis A. Papakonstantinou, Charles Rackoff, Yevgeniy Vahlis:
How powerful are the DDH hard groups? Article TR12-167 - Michael Viderman:
Strong LTCs with inverse polylogarithmic rate and soundness. Article TR12-168 - Noga Alon, Santosh S. Vempala:
The Approximate Rank of a Matrix and its Algorithmic Applications. Article TR12-169 - Scott Aaronson, Travis Hance:
Generalizing and Derandomizing Gurvits's Approximation Algorithm for the Permanent. Article TR12-170 - Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein:
From Information to Exact Communication. Article TR12-171 - Mahdi Cheraghchi, Anna Gál, Andrew Mills:
Correctness and Corruption of Locally Decodable Codes. Article TR12-172 - Kfir Barhum, Thomas Holenstein:
A Cookbook for Black-Box Separations and a Recipe for UOWHFs. Article TR12-173 - Anat Ganor, Ilan Komargodski, Ran Raz:
The Spectrum of Small DeMorgan Formulas. Article TR12-174 - James Cook, Omid Etesami, Rachel Miller, Luca Trevisan:
On the One-Way Function Candidate Proposed by Goldreich. Article TR12-175 - Marek Karpinski, Andrzej Lingas, Dzmitry Sledneu:
Optimal Cuts and Partitions in Tree Metrics in Polynomial Time. Article TR12-176 - Mark Braverman, Ankit Garg, Denis Pankratov, Omri Weinstein:
Information lower bounds via self-reducibility. Article TR12-177 - Paul Beame, Raphaël Clifford, Widad Machmouchi:
Sliding Windows With Limited Storage. Article TR12-178 - Joshua Brody, Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman:
Towards a Reverse Newman's Theorem in Interactive Information Complexity. Article TR12-179 - Chaim Even-Zohar, Shachar Lovett:
The Freiman-Ruzsa Theorem in Finite Fields. Article TR12-180 - Anindya De, Ilias Diakonikolas, Rocco A. Servedio:
The Inverse Shapley Value Problem. Article TR12-181 - Itay Berman, Iftach Haitner, Ilan Komargodski, Moni Naor:
Hardness Preserving Reductions via Cuckoo Hashing. Article TR12-182 - András Z. Salamon:
Streaming bounds from difference ramification. Article TR12-183 - Arnab Bhattacharyya, Eldar Fischer, Hamed Hatami, Pooya Hatami, Shachar Lovett:
Every locally characterized affine-invariant property is testable. Article TR12-184 - Siu Man Chan, Aaron Potechin:
Tight Bounds for Monotone Switching Networks via Fourier Analysis. Article TR12-185 - Andreas Krebs, Nutan Limaye:
DLOGTIME-Proof Systems. Article TR12-186
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-03-20 00:30 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:
