Search results for "circuit complexity"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
3	Michal Koucký	Circuit Complexity of Regular Languages.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Circuit complexity, Regular languages, Upper and lower bounds
3	George Karakostas	General Pseudo-random Generators from Weaker Models of Computation.	ISAAC	2009	DBLP DOI BibTeX RDF	monotone circuit complexity, circuit complexity, Pseudo-random generators
3	Michal Koucký	Circuit Complexity of Regular Languages.	CiE	2007	DBLP DOI BibTeX RDF	circuit complexity, regular languages
3	Russell Impagliazzo	Can every randomized algorithm be derandomized?	STOC	2006	DBLP DOI BibTeX RDF	algebraic circuit complexity, probabilistic algorithms, derandomization, circuit complexity, complexity classes, pseudo-randomness
3	Larry J. Stockmeyer, Albert R. Meyer	Cosmological lower bound on the circuit complexity of a small problem in logic.	J. ACM	2002	DBLP DOI BibTeX RDF	WS1S, practical undecidability, computational complexity, lower bound, logic, Circuit complexity, decision problem
3	Massimiliano Goldwurm, Beatrice Palano, Massimo Santini	On the Circuit Complexity of Random Generation Problems for Regular and Context-Free Languages.	STACS	2001	DBLP DOI BibTeX RDF	Uniform random generation, ambiguous context-free languages, auxiliary pushdown automata, circuit complexity
2	Ryan Williams	Guest column: a casual tour around a circuit complexity bound.	SIGACT News	2011	DBLP DOI BibTeX RDF
2	Kazuo Iwama, Hiroki Morizumi, Jun Tarui	Negation-Limited Complexity of Parity and Inverters.	Algorithmica	2009	DBLP DOI BibTeX RDF	Negation-limited circuit, Parity function, Inversion complexity, Gate elimination, Circuit complexity, Inverter
2	Kazuyuki Amano, Jun Tarui	A Well-Mixed Function with Circuit Complexity 5n±o(n): Tightness of the Lachish-Raz-Type Bounds.	TAMC	2008	DBLP DOI BibTeX RDF
2	Jatan P. Shah, Rama Sangireddy	Higher Clock Rate at Comparable IPC Through Reduced Circuit Complexity in Instruction Format Based Pipeline Clustering.	ISCAS	2007	DBLP DOI BibTeX RDF
2	Hiroki Morizumi, Jun Tarui	Linear-Size Log-Depth Negation-Limited Inverter for k -Tonic Binary Sequences.	TAMC	2007	DBLP DOI BibTeX RDF	negation-limited circuit, k-tonic, circuit complexity, inverter
2	Kazuyuki Amano, Akira Maruoka	The Monotone Circuit Complexity of Quadratic Boolean Functions.	Algorithmica	2006	DBLP DOI BibTeX RDF
2	Kazuyuki Amano, Akira Maruoka	On the Monotone Circuit Complexity of Quadratic Boolean Functions.	ISAAC	2004	DBLP DOI BibTeX RDF
2	Hubie Chen	Arithmetic Constant-Depth Circuit Complexity Classes.	MFCS	2003	DBLP DOI BibTeX RDF
2	Yuval Ishai, Amit Sahai, David Wagner	Private Circuits: Securing Hardware against Probing Attacks.	CRYPTO	2003	DBLP DOI BibTeX RDF	Cryptanalysis, provable security, side channel attacks, secure multi-party computation, circuit complexity
2	Brian A. Fields, Rastislav Bodík, Mark D. Hill	Slack: Maximizing Performance Under Technological Constraints. (PDF / PS)	ISCA	2002	DBLP DOI BibTeX RDF	microexecution, technological constraints, wire delay, clusters, performance analysis, power, circuit complexity, critical path, program behavior, slack
2	Richard Cleve, John Watrous	Fast parallel circuits for the quantum Fourier transform.	FOCS	2000	DBLP DOI BibTeX RDF	fast parallel circuits, quantum Fourier transform, QFT, circuit depth, constant error, depth bound, polynomial size, classical polynomial-time processing, depth complexity, arbitrary modulus, lower bound, theorem proving, quantum computing, Fourier transforms, upper bound, circuit complexity, circuit complexity, quantum circuits, factoring algorithm
2	Eric Allender, Michael E. Saks, Igor Shparlinski	A Lower Bound for Primality. (PDF / PS)	IEEE Conference on Computational Complexity	1999	DBLP DOI BibTeX RDF	Circuit Complexity Lower Bounds, Primality, Square-Free Numbers, GCD
2	Matthias Ruhl	Counting and Addition Cannot Express Deterministic Transitive Closure.	LICS	1999	DBLP DOI BibTeX RDF	Counting quantifiers, circuit complexity, finite model theory, descriptive complexity theory
2	Christer Berg, Staffan Ulfberg	Symmetric Approximation Arguments for Monotone Lower Bounds Without Sunflowers.	Computational Complexity	1999	DBLP DOI BibTeX RDF	lower bounds, Circuit complexity, monotone circuits
2	Lane A. Hemaspaandra, Jörg Rothe	A Second Step Towards Circuit Complexity-Theoretic Analogs of Rice's Theorem.	MFCS	1998	DBLP DOI BibTeX RDF
2	Liming Cai, Jianer Chen, Johan Håstad	Circuit Bottom Fan-in and Computational Power. (PDF / PS)	IEEE Conference on Computational Complexity	1997	DBLP DOI BibTeX RDF	computational complexity, lower bound, circuit complexity, alternating Turing machine
2	Jin-yi Cai, D. Sivakumar, Martin Strauss	Constant Depth Circuits and the Lutz Hypothesis.	FOCS	1997	DBLP DOI BibTeX RDF	Lutz hypothesis, Exponential Time, constant-depth, nearly exponential-size circuits, circuit complexity theory, computational complexity, pseudorandom generators, complexity classes, NP, constant depth circuits
2	Manindra Agrawal, Eric Allender	An Isomorphism Theorem for Circuit Complexity. (PDF / PS)	IEEE Conference on Computational Complexity	1996	DBLP DOI BibTeX RDF	Complete Sets, Berman-Hartmanis Conjecture, NC1, AC0, NC0, projections, Circuit Complexity, uniformity, Isomorphisms
2	Pascal Koiran	VC Dimension in Circuit Complexity. (PDF / PS)	IEEE Conference on Computational Complexity	1996	DBLP DOI BibTeX RDF	sigmoidal circuits, neural networks, circuit complexity, Vapnik-Chervonenkis dimension
2	Eric Allender	Circuit Complexity before the Dawn of the New Millennium.	FSTTCS	1996	DBLP DOI BibTeX RDF
2	Andreas Jakoby, Rüdiger Reischuk, Christian Schindelhauer	Malign Distributions for Average Case Circuit Complexity.	STACS	1995	DBLP DOI BibTeX RDF	delay, distribution, circuit complexity, average case complexity
2	Chris J. Myers, Tomas Rokicki, Teresa H. Y. Meng	Automatic synthesis of gate-level timed circuits with choice.	ARVLSI	1995	DBLP DOI BibTeX RDF	gate-level timed circuits, C-elements, explicit timing information, textual specification, conditional operation, reachable state space, semi-custom components, timing, logic CAD, asynchronous circuits, asynchronous circuits, circuit CAD, cellular arrays, circuit complexity, logic arrays, graphical representation, standard-cells, CAD tool, automatic synthesis, gate-arrays, state-space methods, AND gates, OR gates
2	Sushil Aryal, James S. Meditch	Design of a large ATM switch with trunk grouping.	ICCCN	1995	DBLP DOI BibTeX RDF	load throughput value, dense VLSI implementation, large ATM switch with trunk grouping, LAST switch, IBSS, ideal bit by bit self routing switch, delay, topology, throughput, interconnections, communication complexity, modules, circuit complexity, cell loss
2	Andrew Chi-Chih Yao	Quantum Circuit Complexity	FOCS	1993	DBLP DOI BibTeX RDF	quantum communication complexity, quantum circuit complexity, Boolean circuit model, quantum Turing machine, polynomial time
2	Howard Straubing	Circuit Complexity and the Expressive Power of Generalized First-Order Formulas.	ICALP	1992	DBLP DOI BibTeX RDF
2	Eddy Mayoraz	On the Power of Networks of Majority Functions.	IWANN	1991	DBLP DOI BibTeX RDF	linear threshold function, synaptic weights quantization, majority functions, neural network, circuit complexity
2	Eric Allender	P-uniform circuit complexity.	J. ACM	1989	DBLP DOI BibTeX RDF
1	Evgeny Demenkov, Alexander S. Kulikov	An Elementary Proof of 3n-o(n) Lower Bound on the Circuit Complexity of Affine Dispersers.	Electronic Colloquium on Computational Complexity (ECCC)	2011	DBLP BibTeX RDF
1	Kazuyuki Amano, Jun Tarui	A well-mixed function with circuit complexity 5n: Tightness of the Lachish-Raz-type bounds.	Theor. Comput. Sci.	2011	DBLP DOI BibTeX RDF
1	Ryan Williams	A Casual Tour Around a Circuit Complexity Bound	CoRR	2011	DBLP BibTeX RDF
1	Oded Goldreich, Avi Wigderson	On the Circuit Complexity of Perfect Hashing.	Studies in Complexity and Cryptography	2011	DBLP DOI BibTeX RDF
1	Evgeny Demenkov, Alexander S. Kulikov	An Elementary Proof of a 3n - o(n) Lower Bound on the Circuit Complexity of Affine Dispersers.	MFCS	2011	DBLP DOI BibTeX RDF
1	Evgeny Demenkov, Arist Kojevnikov, Alexander S. Kulikov, Grigory Yaroslavtsev	New upper bounds on the Boolean circuit complexity of symmetric functions.	Inf. Process. Lett.	2010	DBLP DOI BibTeX RDF
1	Hans Kleine Büning, Anja Remshagen	An upper bound for the circuit complexity of existentially quantified Boolean formulas.	Theor. Comput. Sci.	2010	DBLP DOI BibTeX RDF
1	Andreas Alexander Albrecht, Alexander V. Chaskin, Costas S. Iliopoulos, Oktay M. Kasim-Zade, Georgios Lappas, Kathleen Steinhöfel	A Note on a priori Estimations of Classification Circuit Complexity.	Fundam. Inform.	2010	DBLP DOI BibTeX RDF
1	Arist Kojevnikov, Alexander S. Kulikov	Circuit Complexity and Multiplicative Complexity of Boolean Functions.	CiE	2010	DBLP DOI BibTeX RDF
1	Dan Gutfreund, Akinori Kawachi	Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds.	IEEE Conference on Computational Complexity	2010	DBLP DOI BibTeX RDF	Arthur-Merlin protocols, derandomization, circuit complexity, approximate counting
1	Jagannath Keshava, Nagib Hakim, Chinna Prudvi	Post-silicon validation challenges: how EDA and academia can help.	DAC	2010	DBLP DOI BibTeX RDF	design, verification, test, validation, emulation
1	Scott Aaronson	BQP and the polynomial hierarchy.	STOC	2010	DBLP DOI BibTeX RDF	linial-nisan conjecture, quantum complexity classes, fourier analysis, constant-depth circuits
1	Vikraman Arvind, Srikanth Srinivasan	On the hardness of the noncommutative determinant.	STOC	2010	DBLP DOI BibTeX RDF	noncommutative rings, determinant, arithmetic circuits, permanent
1	P. W. Chandana Prasad, Azam Beg	Investigating data preprocessing methods for circuit complexity models.	Expert Syst. Appl.	2009	DBLP DOI BibTeX RDF
1	Christian Bessiere, George Katsirelos, Nina Narodytska, Toby Walsh	Circuit Complexity and Decompositions of Global Constraints	CoRR	2009	DBLP BibTeX RDF
1	Christian Bessiere, George Katsirelos, Nina Narodytska, Toby Walsh	Circuit Complexity and Decompositions of Global Constraints.	IJCAI	2009	DBLP BibTeX RDF
1	Kristoffer Arnsfelt Hansen, Oded Lachish, Peter Bro Miltersen	Hilbert's Thirteenth Problem and Circuit Complexity.	ISAAC	2009	DBLP DOI BibTeX RDF
1	Ran Raz	Multi-linear formulas for permanent and determinant are of super-polynomial size.	J. ACM	2009	DBLP DOI BibTeX RDF	arithmetic formulas, lower bounds, circuit complexity, algebraic complexity
1	Arkadev Chattopadhyay, Avi Wigderson	Linear Systems over Composite Moduli.	FOCS	2009	DBLP DOI BibTeX RDF	Boolean circuit complexity, modular gates, matrix rigidity, exponential sums, constant-depth circuits
1	Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy	Planar and Grid Graph Reachability Problems.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Logspace, Algorithms, Planar graphs, Reachability, Complexity theory, Circuit complexity, Grid graphs
1	Craig Gentry	Fully homomorphic encryption using ideal lattices.	STOC	2009	DBLP DOI BibTeX RDF	fully homomorphic encryption
1	Russell Impagliazzo, Valentine Kabanets, Avi Wigderson	New direct-product testers and 2-query PCPs.	STOC	2009	DBLP DOI BibTeX RDF	testing, PCP, parallel repetition, direct products
1	Eyal Kushilevitz, Enav Weinreb	On the complexity of communication complexity.	STOC	2009	DBLP DOI BibTeX RDF	protocol tree, lower bounds, communication complexity, hardness of approximation, pseudo random functions
1	Edward A. Hirsch, Sergey I. Nikolenko	A Feebly Secure Trapdoor Function.	CSR	2009	DBLP DOI BibTeX RDF
1	Georg Seelig, David Soloveichik	Time-Complexity of Multilayered DNA Strand Displacement Circuits.	DNA	2009	DBLP DOI BibTeX RDF
1	Cosmin Radu Popa	A New FGMOST Euclidean Distance Computational Circuit Based on Algebraic Mean of the Input Potentials.	ICANN	2009	DBLP DOI BibTeX RDF	Computational circuits, FGMOST, VLSI design
1	Benjamin Rossman	Ehrenfeucht-Fraïssé Games on Random Structures.	WoLLIC	2009	DBLP DOI BibTeX RDF
1	Jean-Camille Birget	Factorizations of the Thompson-higman Groups, and Circuit Complexity.	IJAC	2008	DBLP DOI BibTeX RDF
1	John M. Hitchcock, Aduri Pavan	Hardness Hypotheses, Derandomization, and Circuit Complexity.	Computational Complexity	2008	DBLP DOI BibTeX RDF	68Q30, 68Q17, Subject classification. 68Q15
1	Eric Allender	Circuit Complexity, Kolmogorov Complexity, and Prospects for Lower Bounds.	DCFS	2008	DBLP BibTeX RDF
1	Ran Raz	Elusive functions and lower bounds for arithmetic circuits.	STOC	2008	DBLP DOI BibTeX RDF	bounded depth circuits, lower bounds, arithmetic circuits, circuit complexity
1	Benjamin Rossman	On the constant-depth complexity of k-clique.	STOC	2008	DBLP DOI BibTeX RDF	ac0, bounded variable hierarchy, k-clique, first-order logic, circuit complexity, constant-depth circuits
1	Eric Allender, Michal Koucký	Amplifying Lower Bounds by Means of Self-Reducibility.	IEEE Conference on Computational Complexity	2008	DBLP DOI BibTeX RDF	self-reducibility, lower bounds, circuit complexity
1	Ruei-Rung Lee, Jie-Hong Roland Jiang, Wei-Lun Hung	Bi-decomposing large Boolean functions via interpolation and satisfiability solving.	DAC	2008	DBLP DOI BibTeX RDF	bi-decomposition, satisfiability, logic synthesis, Craig interpolation
1	Pu Liu, Sheldon X.-D. Tan, Wei Wu, Murli Tirumala	FEKIS: a fast architecture-level thermal analyzer for online thermal regulation.	ACM Great Lakes Symposium on VLSI	2008	DBLP DOI BibTeX RDF	architecture, model reduction, thermal simulation
1	Zhuo Feng, Peng Li	Multigrid on GPU: tackling power grid analysis on parallel SIMT platforms.	ICCAD	2008	DBLP DOI BibTeX RDF
1	Ryan O'Donnell, Rocco A. Servedio	The chow parameters problem.	STOC	2008	DBLP DOI BibTeX RDF	chow parameters, boolean function, fourier analysis, threshold function
1	Ryan Williams	Applying practice to theory.	SIGACT News	2008	DBLP DOI BibTeX RDF
1	Rajesh Garg, Gagandeep Mallarapu, Sunil P. Khatri	A Single-supply True Voltage Level Shifter.	DATE	2008	DBLP DOI BibTeX RDF
1	Timothy Y. Chow	Almost-Natural Proofs.	FOCS	2008	DBLP DOI BibTeX RDF
1	Yin-Tsung Hwang, Wei-Da Chen	A low complexity complex QR factorization design for signal detection in MIMO OFDM systems.	ISCAS	2008	DBLP DOI BibTeX RDF
1	Christoph Studer, Peter Luethi, Wolfgang Fichtner	VLSI architecture for data-reduced steering matrix feedback in MIMO systems.	ISCAS	2008	DBLP DOI BibTeX RDF
1	Ping-Ying Wang, Hsiu-Ming Chang	A charge pump-based direct frequency modulator.	ISCAS	2008	DBLP DOI BibTeX RDF
1	Ji-Man Park, Sung-Ik Jun	A resistance deviation-to-time interval converter for resistive sensors.	SoCC	2008	DBLP DOI BibTeX RDF
1	Yong-Sheng Yan, Yuan-Ting Zhang	An Efficient Motion-Resistant Method for Wearable Pulse Oximeter.	IEEE Transactions on Information Technology in Biomedicine	2008	DBLP DOI BibTeX RDF
1	Pierre McKenzie, Michael Thomas, Heribert Vollmer	Extensional Uniformity for Boolean Circuits.	CSL	2008	DBLP DOI BibTeX RDF	descriptive complexity, uniformity, Boolean circuits
1	Michael Elberfeld, Till Tantau	Computational Complexity of Perfect-Phylogeny-Related Haplotyping Problems.	MFCS	2008	DBLP DOI BibTeX RDF	circuit classes, computational complexity, bioinformatics, haplotyping, perfect phylogenies
1	Howard Chen, Scott Neely, Jinjun Xiong, Vladimir Zolotov, Chandu Visweswariah	Statistical Modeling and Analysis of Static Leakage and Dynamic Switching Power.	PATMOS	2008	DBLP DOI BibTeX RDF	Statistical power analysis
1	Jhing-Fa Wang, Jia-Chang Wang, Bo-Wei Chen, Zheng-Wei Sun	A Long-Distance Time Domain Sound Localization.	UIC	2008	DBLP DOI BibTeX RDF
1	F. Javier Díaz, Angel M. Buron, José M. Solana	Haar wavelet based processor scheme for image coding with low circuit complexity.	Computers & Electrical Engineering	2007	DBLP DOI BibTeX RDF
1	Joel Friedman	Linear Transformations in Boolean Complexity Theory.	CiE	2007	DBLP DOI BibTeX RDF	Boolean circuit complexity, linear transformations, cohomology
1	C. Hess, Markus Wenk, Andreas Burg, Peter Luethi, Christoph Studer, Norbert Felber, Wolfgang Fichtner	Reduced-complexity mimo detector with close-to ml error rate performance.	ACM Great Lakes Symposium on VLSI	2007	DBLP DOI BibTeX RDF	FSD, VLSI, MIMO, sphere decoding
1	Jongman Kim, Chrysostomos Nicopoulos, Dongkook Park, Reetuparna Das, Yuan Xie, Narayanan Vijaykrishnan, Mazin S. Yousif, Chita R. Das	A novel dimensionally-decomposed router for on-chip communication in 3D architectures.	ISCA	2007	DBLP DOI BibTeX RDF	3D architecture, 3D integration, network-on-chip (NoC)
1	J. V. R. Ravindra, Srinivas Bala Mandalika	Modeling and analysis of crosstalk for distributed RLC interconnects using difference model approach.	SBCCI	2007	DBLP DOI BibTeX RDF	RC, distributed RLC, interconnect, SPICE, circuit, RL
1	Amit Chakrabarti	Lower Bounds for Multi-Player Pointer Jumping.	IEEE Conference on Computational Complexity	2007	DBLP DOI BibTeX RDF
1	Alexander A. Sherstov	Halfspace Matrices.	IEEE Conference on Computational Complexity	2007	DBLP DOI BibTeX RDF
1	Emanuele Viola	On Approximate Majority and Probabilistic Time.	IEEE Conference on Computational Complexity	2007	DBLP DOI BibTeX RDF
1	Nicola E. L'Insalata, Sergio Saponara, Luca Fanucci, Pierangelo Terreni	Automatic Generation of Low-Complexity FFT/IFFT Cores for Multi-Band OFDM Systems.	DSD	2007	DBLP DOI BibTeX RDF
1	Yin-Tsung Hwang, Jin-Fa Lin, Ming-Hwa Sheu, Chia-Jen Sheu	Low Power Multipliers Using Enhenced Row Bypassing Schemes.	SiPS	2007	DBLP DOI BibTeX RDF
1	Cecília Reis, José António Tenreiro Machado, J. Boaventura Cunha, Eduardo José Solteiro Pires	Evolutionary computation in the design of logic circuits.	SMC	2007	DBLP DOI BibTeX RDF
1	Tsutomu Sasao, Shinobu Nagayama, Jon T. Butler	Numerical Function Generators Using LUT Cascades.	IEEE Trans. Computers	2007	DBLP DOI BibTeX RDF	LUT cascades, numerical function generators (NFGs), nonuniform segmentation, FPGA implementation, automatic synthesis
1	Arkadev Chattopadhyay, Andreas Krebs, Michal Koucký, Mario Szegedy, Pascal Tesson, Denis Thérien	Languages with Bounded Multiparty Communication Complexity.	STACS	2007	DBLP DOI BibTeX RDF
1	John M. Hitchcock, Aduri Pavan	Hardness Hypotheses, Derandomization, and Circuit Complexity.	Electronic Colloquium on Computational Complexity (ECCC)	2006	DBLP BibTeX RDF
1	William Hesse	Some Algebraic Problems with Connections to Circuit Complexity of Dynamic Data Structures.	Circuits, Logic, and Games	2006	DBLP BibTeX RDF
1	Rama Sangireddy	Fast and low-power processor front-end with reduced rename logic circuit complexity.	ISCAS	2006	DBLP DOI BibTeX RDF
1	Takayuki Sato, Kazuyuki Amano, Akira Maruoka	On the Negation-Limited Circuit Complexity of Sorting and Inverting k-tonic Sequences.	COCOON	2006	DBLP DOI BibTeX RDF
1	Sergio Saponara, Pierangelo Terreni	Mixed-signal design of a digital input power amplifier for automotive audio applications.	DATE Designers' Forum	2006	DBLP DOI BibTeX RDF