Search results for "polynomial-size"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
52	Ran Raz	Tensor-rank and lower bounds for arithmetic formulas.	STOC	2010	DBLP DOI BibTeX RDF	homogenous circuits, multilinear circuits, tensor rank, lower bounds, arithmetic circuits
50	Sorin Istrail	Constructing Generalized Universal Traversing Sequences of Polynomial Size for Graphs with Small Diameter (Extended Abstract)	FOCS	1990	DBLP DOI BibTeX RDF	polynomial-size, generalized universal traversing sequences, polynomial size for graphs, small diameter, labeled undirected graphs, edge labels, derandomizations, finite automaton, space-bounded computation
35	Zeev Dvir, Amir Shpilka	Locally decodable codes with 2 queries and polynomial identity testing for depth 3 circuits.	STOC	2005	DBLP DOI BibTeX RDF	depth 3 circuits, locally decodable codes, polynomial identity testing
32	Vikraman Arvind, Partha Mukhopadhyay	Derandomizing the Isolation Lemma and Lower Bounds for Circuit Size.	APPROX-RANDOM	2008	DBLP DOI BibTeX RDF
28	Harry Buhrman, Leen Torenvliet, Falk Unger	Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds.	STACS	2006	DBLP DOI BibTeX RDF	Selfreducibility, Computational Complexity, Sparseness
27	Dana Moshkovitz, Ran Raz	Sub-constant error low degree test of almost-linear size.	STOC	2006	DBLP DOI BibTeX RDF	plane vs. point test, probabilistically checkable proofs, locally testable codes, low degree testing
26	Zeev Dvir, Amir Shpilka, Amir Yehudayoff	Hardness-randomness tradeoffs for bounded depth arithmetic circuits.	STOC	2008	DBLP DOI BibTeX RDF	bounded depth circuits, hardness-randomness tradeoffs, identity testing, lower bounds, arithmetic circuits
26	Tomoyuki Yamakami	Nonuniform families of polynomial-size quantum finite automata and quantum logarithmic-space computation with polynomial-size advice.	Inf. Comput.	2022	DBLP DOI BibTeX RDF
26	Tomoyuki Yamakami	Nonuniform Families of Polynomial-Size Quantum Finite Automata and Quantum Logarithmic-Space Computation with Polynomial-Size Advice.	CoRR	2019	DBLP BibTeX RDF
26	Tomoyuki Yamakami	Nonuniform Families of Polynomial-Size Quantum Finite Automata and Quantum Logarithmic-Space Computation with Polynomial-Size Advice.	LATA	2019	DBLP DOI BibTeX RDF
26	Zohar Shay Karnin, Amir Shpilka	Black Box Polynomial Identity Testing of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-In.	CCC	2008	DBLP DOI BibTeX RDF	PIT, depth-3, arithmetic circuit, deterministic, polynomial identity testing
26	Stefan Dziembowski, Marcin Jurdzinski, Igor Walukiewicz	How Much Memory is Needed to Win Infinite Games?	LICS	1997	DBLP DOI BibTeX RDF	finitely coloured graphs, size of memory, latest appearance record, winning strategies, polynomial-size blowup, data structure, graph colouring, reactive programs, I/O automata, infinite games, two-player games, upper and lower bounds
25	Olha Shkaravska, Ron van Kesteren, Marko C. J. D. van Eekelen	Polynomial Size Analysis of First-Order Functions.	TLCA	2007	DBLP DOI BibTeX RDF	Shapely Functions, Size Analysis, Type Checking, Diophantine equations
25	Valentine Kabanets, Russell Impagliazzo	Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds.	Comput. Complex.	2004	DBLP DOI BibTeX RDF	68Q17, 68Q15, Subject classification. 68Q10
25	Valentine Kabanets, Russell Impagliazzo	Derandomizing polynomial identity tests means proving circuit lower bounds.	STOC	2003	DBLP DOI BibTeX RDF	BPP, NEXP, circuit lower bounds, derandomization, polynomial identity testing
25	Chandrajit L. Bajaj, John F. Canny, R. Garrity, Joe D. Warren	Factoring Rational Polynomials over the Complexes.	ISSAC	1989	DBLP DOI BibTeX RDF
24	Philippe Chatalic, Laurent Simon	Multi-resolution on compressed sets of clauses.	ICTAI	2000	DBLP DOI BibTeX RDF	compressed sets, compressed clauses, propositional clauses, compression power, structured instances, specialized operator, clause sets, polynomial size data structures, ZREs system, Davis-Putnam procedure, hard problems, SAT provers, zero-suppressed binary decision diagrams, computational complexity, data structures, data structures, data compression, theorem proving, computability, encodings, directed graphs, binary decision diagrams, set theory, multi-resolution, cut eliminations, ZBDDs
24	Takafumi Hamano, Naofumi Takagi, Shuzo Yajima, Franco P. Preparata	O(n)-depth circuit algorithm for modular exponentiation.	IEEE Symposium on Computer Arithmetic	1995	DBLP DOI BibTeX RDF	O(n)-depth circuit algorithm, polynomial-size combinational circuit algorithm, n-bit modular exponentiation, n-bit binary integers, square-and-multiply method, public key cryptography, combinational circuits, digital arithmetic, modular exponentiation
24	Ran Raz, Iddo Tzameret	The Strength of Multilinear Proofs.	Comput. Complex.	2008	DBLP DOI BibTeX RDF	Subject classification. 03F20, 68Q17, 13P10
24	Lisa Fleischer, Martin Skutella	The Quickest Multicommodity Flow Problem.	IPCO	2002	DBLP DOI BibTeX RDF
23	Manindra Agrawal, Eric Allender, Samir Datta	On TC0, AC0, and Arithmetic Circuits.	CCC	1997	DBLP DOI BibTeX RDF	TC/sup 0/, AC/sup 0/, function classes, constant-depth polynomial-size arithmetic circuits, unbounded fanin addition, multiplication gates, constant-depth arithmetic circuits, computational complexity, normal forms, arithmetic circuits, closure properties
23	Arkadev Chattopadhyay	Discrepancy and the Power of Bottom Fan-in in Depth-three Circuits.	FOCS	2007	DBLP DOI BibTeX RDF
22	Johannes Köbler, Osamu Watanabe 0001	New Collapse Consequences of NP Having Small Circuits.	ICALP	1995	DBLP DOI BibTeX RDF
22	Daniel Král	Polynomial-Size Binary Decision Diagrams for the Exactly Half-d-Hyperclique Problem Reading Each Input Bit Twice.	Theory Comput. Syst.	2009	DBLP DOI BibTeX RDF	Free binary decision diagrams, Binary decision diagrams
22	Miklos Santha, Christopher B. Wilson	Polynomial Size Constant Depth Circuits with a Limited Number of Negations.	STACS	1991	DBLP DOI BibTeX RDF
21	Ran Raz, Amir Yehudayoff	Lower Bounds and Separations for Constant Depth Multilinear Circuits.	Comput. Complex.	2009	DBLP DOI BibTeX RDF	68Q17, Subject classification
21	Ran Raz, Amir Yehudayoff	Lower Bounds and Separations for Constant Depth Multilinear Circuits.	CCC	2008	DBLP DOI BibTeX RDF	Constant Depth, Lower Bounds, Separations, Arithmetic Circuits
21	Michel Cosnard, Martín Matamala	On NC-Real Complexity Classes for Additive Circuits and Their Relations with NC.	MFCS	1994	DBLP DOI BibTeX RDF
20	Adam R. Klivans, Alexander A. Sherstov	Cryptographic Hardness for Learning Intersections of Halfspaces.	FOCS	2006	DBLP DOI BibTeX RDF
20	Boaz Barak, Amit Sahai	How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation.	FOCS	2005	DBLP DOI BibTeX RDF
20	Ramamohan Paturi, Pavel Pudlák	On the complexity of circuit satisfiability.	STOC	2010	DBLP DOI BibTeX RDF	NP-completeness, circuit satisfiability
20	Alberto Del Pia, Aida Khajavirad	The pseudo-Boolean polytope and polynomial-size extended formulations for binary polynomial optimization.	CoRR	2023	DBLP DOI BibTeX RDF
20	D. Castro, Luis Miguel Pardo, Jorge San Martín	Systems of rational polynomial equations have polynomial size approximate zeros on the average.	J. Complex.	2003	DBLP DOI BibTeX RDF
19	Frank K. H. A. Dehne, Masoud T. Omran, Jörg-Rüdiger Sack	Shortest paths in time-dependent FIFO networks using edge load forecasts.	GIS-IWCTS	2009	DBLP DOI BibTeX RDF
19	Boaz Barak, Oded Goldreich 0001	Universal Arguments and their Applications.	CCC	2002	DBLP DOI BibTeX RDF	Probabilistic proof systems, computationally-sound proof systems, zero-knowledge proof systems, probabilistic checkable proofs (PCP), collision-free hashing, witness indistinguishable proof systems, error-correcting codes, proofs of knowledge
19	Søren Riis	A complexity gap for tree resolution.	Comput. Complex.	2001	DBLP DOI BibTeX RDF	Logical aspects of complexity, resolution proofs, propositional proof complexity
19	David W. Juedes, Jack H. Lutz	Completeness and Weak Completeness Under Polynomial-Size Circuits.	STACS	1995	DBLP DOI BibTeX RDF
19	John M. Hitchcock, N. V. Vinodchandran	Dimension, Entropy Rates, and Compression.	CCC	2004	DBLP DOI BibTeX RDF
18	Esko Ukkonen	On Size Bounds for Deterministic Parsers.	ICALP	1981	DBLP DOI BibTeX RDF	size complexity, left parser, right parser, LL(k) parsing, LR(k) parsing
18	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
18	Wolfgang Maass 0001, Georg Schnitger, Eduardo D. Sontag	On the Computational Power of Sigmoid versus Boolean Threshold Circuits	FOCS	1991	DBLP DOI BibTeX RDF	polynomially bounded weights, sigmoid threshold gates, smooth threshold gates, depth 2 circuits, Boolean threshold circuits, constant size circuits, Boolean threshold gates, polynomial size sigmoid threshold circuits, Boolean functions, computational power, constant depth circuits
18	Carl Sturtivant, Zhi-Li Zhang	Efficiently Inverting Bijections Given by Straight Line Programs	FOCS	1990	DBLP DOI BibTeX RDF	Boolean field, inverting bijections, cryptographic considerations, polynomial-size arithmetic circuit, arithmetic operations, automorphism, automorphism, algebraic geometry, straight line programs
18	László Babai, Lajos Rónyai	Computing Irreducible Representations of Finite Groups	FOCS	1989	DBLP DOI BibTeX RDF	deterministic polynomial time, matrices list, randomized polynomial time, Las Vegas polynomial time, generators set, bit complexity, inequivalent irreducible representations, multiplication table, polynomial-size description, absolutely irreducible constituents, polynomial-time algorithm, equivalence class, finite groups, complex numbers, exact computations, algebraic number fields
18	George N. Karystinos, Athanasios P. Liavas	Efficient computation of the binary vector that maximizes a rank-deficient quadratic form.	ICASSP	2008	DBLP DOI BibTeX RDF
18	Detlef Sieling	Lower Bounds for Linear Transformed OBDDs and FBDDs (Extende Abstract).	FSTTCS	1999	DBLP DOI BibTeX RDF
18	V. Vinay	Hierarchies of Circuit Classes that are Closed under Complement.	CCC	1996	DBLP DOI BibTeX RDF	Circuits, Complexity Theory, Complementation
18	Juhani Karhumäki, Wojciech Plandowski, Wojciech Rytter	Polynomial Size Test Sets for Context-Free Languages.	ICALP	1992	DBLP DOI BibTeX RDF
18	Christoph Meinel	The Power of Polynomial Size Omega-Branching Programs.	STACS	1988	DBLP DOI BibTeX RDF
18	Dima Grigoriev, Edward A. Hirsch, Dmitrii V. Pasechnik	Complexity of Semi-algebraic Proofs.	STACS	2002	DBLP DOI BibTeX RDF
16	Dimitris S. Papailiopoulos, George N. Karystinos	Efficient computation of the M-phase vector that maximizes a rank-deficient quadratic form.	CISS	2008	DBLP DOI BibTeX RDF
16	Emanuele Viola	On Constructing Parallel Pseudorandom Generators from One-Way Functions.	CCC	2005	DBLP DOI BibTeX RDF	Pseudorandom generator construction, one-way function, black-box, restriction, constant-depth circuit, noise sensitivity, hardness amplification
16	Amos Beimel, Enav Weinreb	Monotone Circuits for Weighted Threshold Functions.	CCC	2005	DBLP DOI BibTeX RDF
16	Ran Raz	Multilinear-NC neq Multilinear-NC.	FOCS	2004	DBLP DOI BibTeX RDF
16	Zeev Dvir, Ariel Gabizon, Avi Wigderson	Extractors and Rank Extractors for Polynomial Sources.	FOCS	2007	DBLP DOI BibTeX RDF
15	Ran Raz	Quantum Information and the PCP Theorem.	Algorithmica	2009	DBLP DOI BibTeX RDF	Quantum interactive proofs, Quantum advice, Quantum computation, Probabilistically checkable proofs, Quantum information, Low degree test
15	Kei Uchizawa, Rodney J. Douglas, Wolfgang Maass 0001	Energy Complexity and Entropy of Threshold Circuits.	ICALP (1)	2006	DBLP DOI BibTeX RDF
15	Ran Raz	Quantum Information and the PCP Theorem.	FOCS	2005	DBLP DOI BibTeX RDF
15	Farid M. Ablayev, Marek Karpinski	On the Power of Randomized Branching Programs.	ICALP	1996	DBLP DOI BibTeX RDF
15	Lance Fortnow, Adam R. Klivans	Efficient Learning Algorithms Yield Circuit Lower Bounds.	COLT	2006	DBLP DOI BibTeX RDF
15	Mitsuo Wakatsuki, Kiyoshi Teraguchi, Etsuji Tomita	Polynomial Time Identification of Strict Deterministic Restricted One-Counter Automata in Some Class from Positive Data.	ICGI	2004	DBLP DOI BibTeX RDF
15	Wojciech Plandowski	Testing Equivalence of Morphisms on Context-Free Languages.	ESA	1994	DBLP DOI BibTeX RDF
15	Meena Mahajan, V. Vinay	Non-commutative Computation, Depth Reduction, and Skew Circuits (Extended Abstract).	FSTTCS	1994	DBLP DOI BibTeX RDF
15	Erich L. Kaltofen	Greatest common divisors of polynomials given by straight-line programs.	J. ACM	1988	DBLP DOI BibTeX RDF
13	Christoph Fünfzig, Dominique Michelucci, Sebti Foufou	Polytope-based computation of polynomial ranges.	SAC	2010	DBLP DOI BibTeX RDF	polynomial ranges, polytopes, multivariate polynomials, Bernstein polynomials
13	Dana Moshkovitz, Ran Raz	Two Query PCP with Sub-Constant Error.	FOCS	2008	DBLP DOI BibTeX RDF
13	Dana Dachman-Soled, Homin K. Lee, Tal Malkin, Rocco A. Servedio, Andrew Wan, Hoeteck Wee	Optimal Cryptographic Hardness of Learning Monotone Functions.	ICALP (1)	2008	DBLP DOI BibTeX RDF
13	Edith Elkind, Leslie Ann Goldberg, Paul W. Goldberg	Computing good nash equilibria in graphical games.	EC	2007	DBLP DOI BibTeX RDF	approximation scheme, graphical games
13	Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay	Circuits on cylinders.	Comput. Complex.	2006	DBLP DOI BibTeX RDF	Subject classification. 68Q05, 68Q70
13	Kristoffer Arnsfelt Hansen, Peter Bro Miltersen, V. Vinay	Circuits on Cylinders.	FCT	2003	DBLP DOI BibTeX RDF
13	Beate Bollig, Ingo Wegener	Complexity Theoretical Results on Partitioned (Nondeterministic) Binary Decision Diagrams.	Theory Comput. Syst.	1999	DBLP DOI BibTeX RDF
13	Beate Bollig, Ingo Wegener	Complexity Theoretical Results on Partitioned (Nondeterministic) Binary Decision Diagrams.	MFCS	1997	DBLP DOI BibTeX RDF
13	Manfred Scheucher	Many order types on integer grids of polynomial size.	Comput. Geom.	2023	DBLP DOI BibTeX RDF
13	Christoph Buchheim	Bilevel linear optimization belongs to NP and admits polynomial-size KKT-based reformulations.	Oper. Res. Lett.	2023	DBLP DOI BibTeX RDF
13	Zeyu Guo 0001, Zihan Zhang	Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets.	CoRR	2023	DBLP DOI BibTeX RDF
13	Diptapriyo Majumdar	Enumeration Kernels of Polynomial Size for Cuts of Bounded Degree.	CoRR	2023	DBLP DOI BibTeX RDF
13	Tomoyuki Yamakami	Unambiguity and Fewness for Nonuniform Families of Polynomial-Size Nondeterministic Finite Automata.	CoRR	2023	DBLP DOI BibTeX RDF
13	Tomoyuki Yamakami	Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata.	CoRR	2023	DBLP DOI BibTeX RDF
13	Farnaz Farzadnia, Tolga Bektas, Jens Lysgaard	The cumulative school bus routing problem: Polynomial-size formulations.	Networks	2023	DBLP DOI BibTeX RDF
13	Christoph Hertrich, Leon Sering	ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation.	IPCO	2023	DBLP DOI BibTeX RDF
13	Zeyu Guo 0001, Zihan Zhang	Randomly Punctured Reed-Solomon Codes Achieve the List Decoding Capacity over Polynomial-Size Alphabets.	FOCS	2023	DBLP DOI BibTeX RDF
13	Tomoyuki Yamakami	Power of Counting by Nonuniform Families of Polynomial-Size Finite Automata.	FCT	2023	DBLP DOI BibTeX RDF
13	Jesse Mulderij, Karen I. Aardal, Irina Chiscop, Frank Phillipson	A Polynomial Size Model with Implicit SWAP Gate Counting for Exact Qubit Reordering.	ICCS (5)	2023	DBLP DOI BibTeX RDF
13	Masato Tanaka, Tomomi Matsui	Pseudo polynomial size LP formulation for calculating the least core value of weighted voting games.	Math. Soc. Sci.	2022	DBLP DOI BibTeX RDF
13	René Thiemann	Clique is not solvable by monotone circuits of polynomial size.	Arch. Formal Proofs	2022	DBLP BibTeX RDF
13	Tomoyuki Yamakami	Unambiguity and Fewness for Nonuniform Families of Polynomial-Size Nondeterministic Finite Automata.	RP	2022	DBLP DOI BibTeX RDF
13	Michael von Thaden	Polynomial-size vectors are enough for the unimodular triangulation of simplicial cones.	J. Comb. Theory, Ser. A	2021	DBLP DOI BibTeX RDF
13	Masato Tanaka, Tomomi Matsui	Pseudo Polynomial Size LP Formulation for Calculating the Least Core Value of Weighted Voting Games.	CoRR	2021	DBLP BibTeX RDF
13	Laura Galli, Silvano Martello, Carlos Rey 0001, Paolo Toth	Polynomial-size formulations and relaxations for the quadratic multiple knapsack problem.	Eur. J. Oper. Res.	2021	DBLP DOI BibTeX RDF
13	Christopher Hojny	Polynomial size IP formulations of knapsack may require exponentially large coefficients.	Oper. Res. Lett.	2020	DBLP DOI BibTeX RDF
13	Jesse Mulderij, Karen I. Aardal, Irina Chiscop, Frank Phillipson	A polynomial size model with implicit SWAP gate counting for exact qubit reordering.	CoRR	2020	DBLP BibTeX RDF
13	Manfred Scheucher	Many Order Types on Integer Grids of Polynomial Size.	CoRR	2020	DBLP BibTeX RDF
13	Oded Goldreich 0001	On (Valiant's) Polynomial-Size Monotone Formula for Majority.	Computational Complexity and Property Testing	2020	DBLP DOI BibTeX RDF
13	Mikolaj Bojanczyk, Sandra Kiefer, Nathan Lhote	String-to-String Interpretations with Polynomial-Size Output.	CoRR	2019	DBLP BibTeX RDF
13	David Avis, David Bremner, Hans Raj Tiwary, Osamu Watanabe 0001	Polynomial size linear programs for problems in P.	Discret. Appl. Math.	2019	DBLP DOI BibTeX RDF
13	Mikolaj Bojanczyk, Sandra Kiefer, Nathan Lhote	String-to-String Interpretations With Polynomial-Size Output.	ICALP	2019	DBLP DOI BibTeX RDF
13	Yfke Dulek, Christian Schaffner, Florian Speelman	Quantum Homomorphic Encryption for Polynomial-Size Circuits.	Theory Comput.	2018	DBLP DOI BibTeX RDF
13	Lijie Chen 0001	Toward Super-Polynomial Size Lower Bounds for Depth-Two Threshold Circuits.	CoRR	2018	DBLP BibTeX RDF
13	Amitava Datta	Construction of Polynomial-Size Optical Priority Queues Using Linear Switches and Fiber Delay Lines.	IEEE/ACM Trans. Netw.	2017	DBLP DOI BibTeX RDF
13	Valeria Leggieri, Mohamed Haouari	Lifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems.	Eur. J. Oper. Res.	2017	DBLP DOI BibTeX RDF
13	Erik D. Demaine, André Schulz 0001	Embedding Stacked Polytopes on a Polynomial-Size Grid.	Discret. Comput. Geom.	2017	DBLP DOI BibTeX RDF