Browse data: Reference Materials
From Thermodynamics of Computation
Click on one or more items below to narrow your results.
Author:
Showing below up to 128 results in range #1 to #128.
View (previous 250 | next 250) (20 | 50 | 100 | 250 | 500)
- Manoj Gopalkrishnan A Cost / Speed / Reliability Trade-off in Erasing a Bit , (2015)
- A Kilobit Special Number Field Sieve Factorization ,
- A Note on Bennett’s Time-Space Tradeoff for Reversible Computation ,
- A Parallel Repetition Theorem ,
- A complete problem for statistical zero knowledge ,
- A complexity theoretic approach to randomness ,
- Manoj Gopalkrishnan A cost/speed/reliability tradeoff to erasing 9252, 192-201 (2015)
- A fast quantum mechanical algorithm for database search ,
- A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries ,
- A theory of the learnable ,
- Algebraic methods in the theory of lower bounds for Boolean circuit complexity ,
- An O(log n log log n) Space Algorithm for Undirected st-connectivity ,
- An introduction to thermodynamics and statistical mechanics ,
- Application of Boolean Algebra to Switching Circuit Design and to Error Detection ,
- Alistair Sinclair, Mark Jerrum Approximate counting, uniform generation and rapidly mixing Markov chains Information and Computation 82, 93-133 (1989)
- Wolfgang Maass Are Recursion Theoretic Arguments Useful in Complexity Theory? Studies in Logic and the Foundations of Mathematics 114, 141-158 (1986)
- Saed G Younis, Jr. Thomas F Knight Asymptotically Zero Energy Computing Split-Level Charge Recovery Logic International Workshop on Low Power Design , 177-182 (1994)
- Average Case Complete Problems ,
- Clemens Lautemann BPP and the polynomial hierarchy Information Processing Letters 17, 215-217 (1983)
- CREW PRAMs and Decision Trees ,
- K. K. Likharev Classical and quantum limitations on energy consumption in computation International Journal of Theoretical Physics 21, 311-326 (1982)
- Combinatorial Problems and Exercises ,
- Communication lower bounds using directional derivatives ,
- Computational Complexity: A Modern Approach ,
- Farzad Parvaresh, Alexander Vardy Correcting errors beyond the Guruswami-Sudan radius in polynomial time Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005, 285-294 (2005)
- Cryptographic Limitations on Learning Boolean Formulae and Finite Automata ,
- Valentine Kabanets, Russell Impagliazzo Derandomizing polynomial identity tests means proving circuit lower bounds Computational Complexity 13, 1-46 (2004)
- Jia Lee, Rui Long Yang, Kenichi Morita Design of 1-tape 2-symbol reversible Turing machines based on reversible logic elements Theoretical Computer Science 460, 78-88 (2012)
- Digitalized Signatures and Public-Key Functions as Intractable as Factorization ,
- Troy Lee, Adi Shraibman Disjointness is hard in the multiparty number-on-the-forehead model Computational Complexity 18, 309-336 (2009)
- Dropbox Quick Start ,
- Valentine Kabanets Easiness Assumptions and Hardness Tests: Trading Time for Zero Error Journal of Computer and System Sciences 63, 236-252 (2001)
- Richard J. Lipton Efficient checking of computations Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 415 LNCS, 207-215 (1990)
- Efficient randomized pattern-matching algorithms ,
- Thomas M. Cover, Joy A. Thomas Elements of Information Theory Elements of Information Theory , 1-748 (2005)
- W. W. Peterson Encoding and Error-Correction Procedures for the Bose-Chaudhuri Codes IRE Transactions on Information Theory 6, 459-470 (1960)
- Laszlo B. Kish End of Moore's law: Thermal (noise) death of integration in micro and nano electronics Physics Letters, Section A: General, Atomic and Solid State Physics 305, 144-149 (2002)
- Every Prime Has a Succinct Certificate ,
- Michael Sipser Expanders, randomness, or time versus space: Extended abstract Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 223 LNCS, 325-329 (1986)
- Alexei O. Orlov, Ravi K. Kummamuru, Rajagopal Ramasubramaniam, Geza Toth, Craig S. Lent, Gary H. Bernstein, Gregory L. Snider Experimental demonstration of a latch in clocked quantum-dot cellular automata Applied Physics Letters 78, 1625-1627 (2001)
- Explicit Constructions of Concentrators ,
- Extractors and pseudorandom generators ,
- Adi Shamir Factoring numbers in O(logn) arithmetic steps Information Processing Letters 8, 28-31 (1979)
- Fault Tolerant Quantum Computation ,
- Founding Cryptography on Oblivious Transfer ,
- Oded Goldreich, Madhu Sudan, Luca Trevisan From logarithmic advice to single-bit advice Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 6650 LNCS, 109-113 (2011)
- Fully parallelized multi prover protocols for NEXP-time ,
- Christos H. Papadimitriou Games against nature Journal of Computer and System Sciences 31, 288-301 (1985)
- Hard examples for resolution ,
- Noam Nisan, Avi Wigderson Hardness vs randomness Journal of Computer and System Sciences 49, 149-167 (1994)
- Ralph C. Merkle, K. Eric Drexler Helical logic Nanotechnology 7, 325-339 (1996)
- Hierarchies of memory limited computations ,
- How to recycle random bits ,
- Venkatesan Guruswami, Madhu Sudan Improved decoding of reed-solomon and algebraic-geometry codes IEEE Transactions on Information Theory 45, 1757-1767 (1999)
- Inapproximability of Combinatorial Optimization Problems ,
- Information Theory, Inference and Learning Algorithms ,
- Marc Mézard, Andrea Montanari Information, Physics, and Computation Information, Physics, and Computation 9780198570837, 1-584 (2009)
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman Introduction to Automata Theory, Languages, and Computation ACM SIGACT News 32, 60-65 (2001)
- Introduction to the Theory of Computation ,
- Nabil Kahale Large Deviation Bounds for Markov Chains Combinatorics Probability and Computing 6, 465-474 (1997)
- Las Vegas is better than determinism in VLSI and distributed computing ,
- Lattice Based Cryptography ,
- Learning decision trees using the Fourier spectrum ,
- William C. Athas, J. Svensson, Jeffrey G. Koller, Nestoras Tzartzanis, Ying Chin Chou Low-Power Digital Systems Based on Adiabatic-Switching Principles IEEE Transactions on Very Large Scale Integration (VLSI) Systems 2, 398-407 (1994)
- Mic hael Alekhnovich, Alexander A. Razborov Lower bounds for polynomial calculus: Non-binomial case Annual Symposium on Foundations of Computer Science - Proceedings , 190-199 (2001)
- Pavel Pudlák Lower bounds for resolution and cutting plane proofs and monotone computations Journal of Symbolic Logic 62, 981-998 (1997)
- Marc Snir Lower bounds on probabilistic linear decision trees Theoretical Computer Science 38, 69-82 (1985)
- A. A. Razborov Lower bounds on the size of bounded depth circuits over a complete basis with logical addition Mathematical Notes of the Academy of Sciences of the USSR 41, 333-338 (1987)
- Ketan Mulmuley, Umesh V. Vazirani, Vijay V. Vazirani Matching is as easy as matrix inversion Combinatorica 7, 105-113 (1987)
- John Timler, Craig S. Lent Maxwell's demon and quantum-dot cellular automata Journal of Applied Physics 94, 1050-1060 (2003)
- Models of Computation: Exploring the Power of Computing ,
- Mauricio Karchmer, Avi Wigderson Monotone Circuits for Connectivity Require Super-Logarithmic Depth SIAM Journal on Discrete Mathematics 3, 255-265 (1990)
- Alexander A. Razborov, Steven Rudich Natural Proofs Journal of Computer and System Sciences 55, 24-35 (1997)
- Elchanan Mossel, Ryan O'donnell, Krzysztof Oleszkiewicz Noise stability of functions with low influences: Invariance and optimality Annals of Mathematics 171, 295-341 (2010)
- Non-Interactive Zero-Knowledge Proof of Knowledge and Chosen Ciphertext Attack ,
- Notes on the history of reversible computation ,
- On Computable Numbers, With Application to the Entscheidungs Problem ,
- On Extracting Randomness from Weak Random Sources ,
- Noam Nisan, Avi Wigderson On rank vs. communication complexity Combinatorica 15, 557-565 (1995)
- M Pinsker On the Complexity of a Concentrator 7th Annual Teletraffic Conference , 318/1--318/4 (1973)
- On the Structure of Polynomial Time Reducibility ,
- On the complexity of matrix product ,
- Christos H. Papadimitriou On the complexity of the parity argument and other inefficient proofs of existence Journal of Computer and System Sciences 48, 498-532 (1994)
- Noam Nisan, Mario Szegedy On the degree of boolean functions as real polynomials Computational Complexity 4, 301-313 (1994)
- Adi Shamir On the generation of cryptographically strong pseudo-random sequences Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) 115 LNCS, 544-550 (1981)
- On the hardness of approximate reasoning ,
- On the hardness of approximating minimization problems ,
- Leonid A. Levin One way functions and pseudorandom generators Combinatorica 7, 357-363 (1987)
- Optimal inapproximability results for MAX-CUT and other 2-variable CSPs? ,
- Christos H. Papadimitriou, Mihalis Yannakakis Optimization, approximation, and complexity classes Journal of Computer and System Sciences 43, 425-440 (1991)
- Polynomial time algorithms for discrete logarithms and factoring on a quantum computer ,
- Polynomial-Time Approximation Algorithms for the Ising Model ,
- Power- constrained CMOS scaling limits ,
- R Penrose Precis of The Emperor's New Mind Behavioral and Brain Sciences 13, 643-705 (1990)
- Private coins versus public coins in interactive proof systems ,
- Michael O. Rabin Probabilistic algorithm for testing primality Journal of Number Theory 12, 128-138 (1980)
- Christopher Umans Pseudo-random generators for all hardnesses Journal of Computer and System Sciences 67, 419-440 (2003)
- Noam Nisan Pseudorandom generators for space-bounded computation Combinatorica 12, 449-461 (1992)
- Alexander A. Razborov Pseudorandom generators hard for k-DNF resolution and polynomial calculus resolution Annals of Mathematics 181, 415-472 (2015)
- Luca Trevisan, Salil Vadhan Pseudorandomness and average-case complexity via uniform reductions Computational Complexity 16, 331-364 (2007)
- Richard P. Feynman Quantum mechanical computers Foundations of Physics 16, 507-531 (1986)
- A. Lubotzky, R. Phillips, P. Sarnak Ramanujan graphs Combinatorica 8, 261-277 (1988)
- Randomized algorithms ,
- Alexander D. Healy Randomness-efficient sampling within NC1 Computational Complexity 17, 3-37 (2008)
- Richard M. Karp Reducibility among combinatorial problems 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art , 219-241 (2010)
- Reliable Quantum Computers (1997) ,
- Alexander A. Razborov Resolution lower bounds for the weak functional pigeonhole principle Theoretical Computer Science 303, 233-243 (2003)
- Reversibility for efficient computing ,
- R. C. Merkle Reversible electronic logic using switches Nanotechnology 4, 21-40 (1993)
- Klaus Jörn Lange, Pierre McKenzie, Alain Tapp Reversible space equals deterministic space Journal of Computer and System Sciences 60, 354-367 (2000)
- Armin Alaghi, John P. Hayes STRAUSS: Spectral Transform Use in Stochastic Circuit Synthesis IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems 34, 1770-1783 (2015)
- Russell A. Martin, Dana Randall Sampling adsorbing staircase walks using a new Markov chain decomposition method Annual Symposium on Foundations of Computer Science - Proceedings , 492-502 (2000)
- Some optimal inapproximability results ,
- Stephen R. Mahaney Sparse complete sets for NP: Solution of a conjecture of Berman and Hartmanis Journal of Computer and System Sciences 25, 130-143 (1982)
- C. H. Papadimitriou, M. Yannakakis The complexity of facets (and some facets of complexity) Journal of Computer and System Sciences 28, 244-259 (1984)
- The history and status of the P versus NP question ,
- The influence of variables on Boolean functions ,
- Armin Haken The intractability of resolution Theoretical Computer Science 39, 297-308 (1985)
- Salil Vadhan The unified theory of pseudorandomness: guest column ACM SIGACT News 38, 39–54 (2007)
- Subhash A. Khot, Nisheeth K. Vishnoi The unique games conjecture, integrality gap for cut problems and embeddability of negative type metrics into l 1 Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005, 53-62 (2005)
- A. Nilli Tight estimates for eigenvalues of regular graphs Electronic Journal of Combinatorics 11, (2004)
- Harry Buhrman, John Tromp, Paul Vitányi Time and space bounds for reversible simulation Journal of Physics A: Mathematical and General 34, 6821-6830 (2001)
- Oleg Verbitsky Towards the parallel repetition conjecture Theoretical Computer Science 157, 277-282 (1996)
- Venkatesan Guruswami, Christopher Umans, Salil Vadhan Unbalanced expanders and randomness extractors from parvaresh-vardy codes Proceedings of the Annual IEEE Conference on Computational Complexity , 96-108 (2007)
- Undirected ST-connectivity in log-space ,
- LA Levin Universal sequential search problems Problemy Peredachi Informatsii 9, 115–116 (1973)
- Subhash Khot, Oded Regev Vertex cover might be hard to approximate to within 2 - ε Journal of Computer and System Sciences 74, 335-349 (2008)
- Word problems requiring exponential time (Preliminary Report) ,