ID: 1305.3288

A Convex Analysis Approach to Computational Entropy

May 14, 2013

View on ArXiv
Maciej Skórski
Computer Science
Mathematics
Information Theory
Information Theory

This paper studies the notion of computational entropy. Using techniques from convex optimization, we investigate the following problems: (a) Can we derandomize the computational entropy? More precisely, for the computational entropy, what is the real difference in security defined using the three important classes of circuits: deterministic boolean, deterministic real valued, or (the most powerful) randomized ones? (b) How large the difference in the computational entropy for an unbounded versus efficient adversary can be? (c) Can we obtain useful, simpler characterizations for the computational entropy?

Similar papers 1

Thermodynamics of computing with circuits

June 11, 2018

87% Match
David Hilton Wolpert, Artemy Kolchinsky
Statistical Mechanics
Computational Complexity
Computational Physics

Digital computers implement computations using circuits, as do many naturally occurring systems (e.g., gene regulatory networks). The topology of any such circuit restricts which variables may be physically coupled during the operation of a circuit. We investigate how such restrictions on the physical coupling affects the thermodynamic costs of running the circuit. To do this we first calculate the minimal additional entropy production that arises when we run a given gate in ...

Find SimilarView on arXiv

A statistical mechanical interpretation of algorithmic information theory

January 28, 2008

86% Match
Kohtaro Tadaki
Information Theory
Computational Complexity
Information Theory
Probability

We develop a statistical mechanical interpretation of algorithmic information theory by introducing the notion of thermodynamic quantities, such as free energy, energy, statistical mechanical entropy, and specific heat, into algorithmic information theory. We investigate the properties of these quantities by means of program-size complexity from the point of view of algorithmic randomness. It is then discovered that, in the interpretation, the temperature plays a role as the ...

Find SimilarView on arXiv

Information-theoretic lower bounds on the oracle complexity of stochastic convex optimization

September 3, 2010

86% Match
Alekh Agarwal, Peter L. Bartlett, ... , Wainwright Martin J.
Machine Learning
Systems and Control
Optimization and Control

Relative to the large literature on upper bounds on complexity of convex optimization, lesser attention has been paid to the fundamental hardness of these problems. Given the extensive use of convex optimization in machine learning and statistics, gaining an understanding of these complexity-theoretic issues is important. In this paper, we study the complexity of stochastic convex optimization in an oracle model of computation. We improve upon known results and obtain tight m...

Find SimilarView on arXiv

Hardness as randomness: a survey of universal derandomization

April 28, 2003

86% Match
Russell Impagliazzo
Computational Complexity

We survey recent developments in the study of probabilistic complexity classes. While the evidence seems to support the conjecture that probabilism can be deterministically simulated with relatively low overhead, i.e., that $P=BPP$, it also indicates that this may be a difficult question to resolve. In fact, proving that probabilistic algorithms have non-trivial deterministic simulations is basically equivalent to proving circuit lower bounds, either in the algebraic or Boole...

Find SimilarView on arXiv

Overview of Information Theory, Computer Science Theory, and Stochastic Thermodynamics for Thermodynamics of Computation

December 31, 2018

86% Match
David H. Wolpert
Statistical Mechanics

I give a quick overview of some of the theoretical background necessary for using modern non-equilibrium statistical physics to investigate the thermodynamics of computation. I first present some of the necessary concepts from information theory, and then introduce some of the most important types of computational machine considered in computer science theory. After this I present a central result from modern non-equilibrium statistical physics: an exact expression for the ...

Find SimilarView on arXiv

A New Approximate Min-Max Theorem with Applications in Cryptography

June 22, 2015

86% Match
Maciej Skorski
Cryptography and Security
Computational Complexity

We propose a novel proof technique that can be applied to attack a broad class of problems in computational complexity, when switching the order of universal and existential quantifiers is helpful. Our approach combines the standard min-max theorem and convex approximation techniques, offering quantitative improvements over the standard way of using min-max theorems as well as more concise and elegant proofs.

Find SimilarView on arXiv

Lower Bounds on the Oracle Complexity of Nonsmooth Convex Optimization via Information Theory

July 19, 2014

86% Match
Gábor Braun, Cristóbal Guzmán, Sebastian Pokutta
Optimization and Control
Computational Complexity
Information Theory
Information Theory

We present an information-theoretic approach to lower bound the oracle complexity of nonsmooth black box convex optimization, unifying previous lower bounding techniques by identifying a combinatorial problem, namely string guessing, as a single source of hardness. As a measure of complexity we use distributional oracle complexity, which subsumes randomized oracle complexity as well as worst-case oracle complexity. We obtain strong lower bounds on distributional oracle comple...

Find SimilarView on arXiv

Circuit complexity and functionality: a thermodynamic perspective

September 11, 2023

86% Match
Claudio Chamon, Andrei E. Ruckenstein, ... , Canetti Ran
Statistical Mechanics
Cryptography and Security

We explore a link between complexity and physics for circuits of given functionality. Taking advantage of the connection between circuit counting problems and the derivation of ensembles in statistical mechanics, we tie the entropy of circuits of a given functionality and fixed number of gates to circuit complexity. We use thermodynamic relations to connect the quantity analogous to the equilibrium temperature to the exponent describing the exponential growth of the number of...

Find SimilarView on arXiv

Characterising Probability Distributions via Entropies

February 11, 2016

86% Match
Satyajit Thakor, Terence Chan, Alex Grant
Information Theory
Information Theory

Characterising the capacity region for a network can be extremely difficult, especially when the sources are dependent. Most existing computable outer bounds are relaxations of the Linear Programming bound. One main challenge to extend linear program bounds to the case of correlated sources is the difficulty (or impossibility) of characterising arbitrary dependencies via entropy functions. This paper tackles the problem by addressing how to use entropy functions to characteri...

Find SimilarView on arXiv

Entropy, Convex Optimization, and Competitive Quantum Interactions

November 12, 2005

86% Match
Gus Gutoski
Computational Complexity
Computer Science and Game Th...

This paper has been withdrawn by the author due to errors.

Find SimilarView on arXiv